B+ 树页面分裂与合并：存储引擎写操作的底层机制

B+ 树页面分裂与合并：存储引擎写操作的底层机制

一、写入的"隐形成本"：页面分裂如何拖慢写入性能

B+ 树是关系型数据库最核心的索引结构，其查询性能的对数复杂度（O(log n)）广为人知。但写入性能的代价常被忽视——每次 INSERT 可能触发页面分裂（Page Split），将一个满页拆分为两个半满页；每次 DELETE 可能触发页面合并（Page Merge），将两个稀疏页合并为一个。页面分裂不仅涉及数据移动，还需要更新父节点的索引项、写 WAL 日志、维护页面链表。在随机写入场景中，页面分裂频率可达写入操作的 30%-50%，是写入延迟的主要来源。理解页面分裂和合并的底层机制，是优化写入性能和设计高效索引的前提。

二、B+ 树页面操作的底层机制

2.1 页面分裂的触发条件与过程

flowchart TB A[INSERT 操作] --> B[定位目标叶子页] B --> C{页面空间充足?} C -->|是| D[直接插入<br/>无需分裂] C -->|否| E[页面分裂] E --> F{分裂类型} F -->|中间分裂| G[按 50:50 拆分<br/>原页保留前半<br/>新页存储后半] F -->|插入点分裂| H[按插入位置拆分<br/>原页保留 ≤ 插入位<br/>新页存储 > 插入位] G & H --> I[更新父节点索引] I --> J{父节点空间充足?} J -->|是| K[插入新索引项] J -->|否| L[递归分裂父节点] L --> I K --> M[写 WAL 日志] M --> N[更新页面链表] N --> O[分裂完成]

2.2 页面合并的触发条件

class BPlusTreePage: """B+ 树页面模拟""" def __init__(self, max_keys: int = 100): self.max_keys = max_keys self.min_keys = max_keys // 2 # 最小填充率 50% self.keys = [] self.values = [] self.children = [] # 内部节点的子页面指针 @property def fill_factor(self) -> float: """当前填充率""" return len(self.keys) / self.max_keys def needs_merge(self) -> bool: """是否需要合并：键数低于最小值""" return len(self.keys) < self.min_keys def needs_split(self) -> bool: """是否需要分裂：键数达到最大值""" return len(self.keys) >= self.max_keys

三、页面分裂与合并的详细实现

3.1 叶子页分裂

from dataclasses import dataclass from typing import List, Optional @dataclass class IndexEntry: """索引条目""" key: int value: int # 行指针或数据 @dataclass class LeafPage: """B+ 树叶子页""" page_id: int entries: List[IndexEntry] next_page: Optional[int] = None # 叶子页链表 prev_page: Optional[int] = None max_entries: int = 100 def insert(self, key: int, value: int) -> Optional['SplitResult']: """插入键值对，必要时触发分裂""" if len(self.entries) >= self.max_entries: return self._split_and_insert(key, value) # 有序插入 pos = self._find_position(key) self.entries.insert(pos, IndexEntry(key=key, value=value)) return None def _split_and_insert(self, key: int, value: int) -> 'SplitResult': """分裂页面并插入新条目""" # 先插入新条目到临时列表 all_entries = self.entries.copy() pos = self._find_position(key) all_entries.insert(pos, IndexEntry(key=key, value=value)) # 中间分裂点 mid = len(all_entries) // 2 # 原页面保留前半部分 self.entries = all_entries[:mid] # 新页面存储后半部分 new_page = LeafPage( page_id=-1, # 待分配 entries=all_entries[mid:], next_page=self.next_page, prev_page=self.page_id, ) # 更新链表指针 self.next_page = new_page.page_id # 返回分裂结果：新页面的最小键作为父节点的索引项 return SplitResult( split_key=new_page.entries[0].key, new_page=new_page, ) def _find_position(self, key: int) -> int: """二分查找插入位置""" low, high = 0, len(self.entries) while low < high: mid = (low + high) // 2 if self.entries[mid].key < key: low = mid + 1 else: high = mid return low @dataclass class SplitResult: """页面分裂结果""" split_key: int # 上升至父节点的键 new_page: LeafPage # 新创建的页面

3.2 页面合并

@dataclass class MergeResult: """页面合并结果""" merged_page: LeafPage removed_key: int # 从父节点删除的索引键 class BPlusTreeMerge: """B+ 树页面合并操作""" def try_merge( self, left: LeafPage, right: LeafPage, separator_key: int, ) -> Optional[MergeResult]: """尝试合并相邻的两个叶子页""" # 合并条件：两个页面的总条目数 ≤ 最大容量 total_entries = len(left.entries) + len(right.entries) if total_entries > left.max_entries: return None # 无法合并，条目太多 # 合并：将右页的条目追加到左页 merged = LeafPage( page_id=left.page_id, entries=left.entries + right.entries, next_page=right.next_page, prev_page=left.prev_page, max_entries=left.max_entries, ) # 更新链表 if right.next_page is not None: # 下一个页面的 prev 指向合并后的页面 pass return MergeResult( merged_page=merged, removed_key=separator_key, ) def try_redistribute( self, left: LeafPage, right: LeafPage, ) -> Optional[int]: """尝试重新分配条目（不合并，只平衡）""" total = len(left.entries) + len(right.entries) if total < left.min_keys * 2: return None # 条目太少，应该合并而非重分配 # 将所有条目均匀分配到两个页面 all_entries = left.entries + right.entries mid = len(all_entries) // 2 left.entries = all_entries[:mid] right.entries = all_entries[mid:] # 返回新的分隔键 return right.entries[0].key

3.3 分裂对写入性能的影响量化

class SplitImpactAnalyzer: """页面分裂对写入性能的影响分析""" def analyze_insert_pattern( self, insert_keys: list, page_capacity: int = 100, ) -> dict: """分析插入模式下的分裂频率""" total_inserts = len(insert_keys) split_count = 0 current_entries = 0 for key in insert_keys: current_entries += 1 if current_entries > page_capacity: # 触发分裂 split_count += 1 # 分裂后原页和新页各约 50% 填充 current_entries = page_capacity // 2 split_rate = split_count / total_inserts if total_inserts > 0 else 0 # 顺序插入 vs 随机插入的分裂频率对比 sorted_keys = sorted(insert_keys) sequential_splits = 0 current_entries = 0 for key in sorted_keys: current_entries += 1 if current_entries > page_capacity: sequential_splits += 1 current_entries = page_capacity // 2 return { 'total_inserts': total_inserts, 'random_insert_splits': split_count, 'sequential_insert_splits': sequential_splits, 'random_split_rate': round(split_rate, 4), 'sequential_split_rate': round(sequential_splits / total_inserts, 4), 'split_overhead_pct': round(split_rate * 30, 1), # 每次分裂约增加 30% 写入延迟 }

3.4 减少分裂的工程策略

-- 策略1：自增主键避免随机分裂 -- 错误：UUID 主键导致随机插入，每次插入都可能分裂 CREATE TABLE orders ( id VARCHAR(36) PRIMARY KEY, -- UUID，随机分布 data TEXT ); -- 正确：自增主键确保顺序插入，分裂只发生在最右页 CREATE TABLE orders ( id BIGINT AUTO_INCREMENT PRIMARY KEY, -- 顺序递增 data TEXT ); -- 策略2：预设填充因子，预留分裂空间 -- InnoDB 默认填充率 15/16 ≈ 93.75% -- 高写入场景可降低填充率 ALTER TABLE orders ENGINE=InnoDB ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=8; -- 策略3：批量加载时关闭索引，加载后重建 -- 适用于大规模数据导入 ALTER TABLE orders DISABLE KEYS; LOAD DATA INFILE 'data.csv' INTO TABLE orders; ALTER TABLE orders ENABLE KEYS; -- 重建索引，顺序构建无分裂

四、边界分析与架构权衡

4.1 分裂导致的页面临时稀疏

50:50 分裂后，两个页面各约 50% 填充，空间利用率从接近 100% 骤降到 50%。在频繁插入删除的表中，平均页面填充率可能只有 60%-70%，导致索引体积膨胀 30%-50%，查询需要遍历更多页面。

4.2 递归分裂的级联影响

叶子页分裂需要更新父节点索引，如果父节点也满了，需要递归分裂。在极端情况下（如批量顺序插入），分裂可能从叶子页一直传播到根页，导致树的高度增加一层。树高增加意味着每次查询多一次磁盘 I/O。

4.3 合并的触发保守性

大多数 B+ 树实现只在页面低于最小填充率时才触发合并，而非在删除后立即合并。这导致删除密集的表中存在大量稀疏页面，浪费存储空间。InnoDB 通过MERGE_THRESHOLD参数控制合并触发条件，默认为页面容量的 50%。

4.4 LSM-Tree 的替代方案

LSM-Tree（如 RocksDB）通过将写入追加到内存表（MemTable），定期合并到磁盘（Compaction），完全避免了页面分裂问题。但 LSM-Tree 的读取需要检查多个层级（MemTable → L0 → L1 → ...），读取放大高于 B+ 树。写入密集型场景优先考虑 LSM-Tree，读取密集型场景优先考虑 B+ 树。

五、总结

B+ 树的页面分裂和合并是写入性能的隐形代价。页面分裂将满页拆分为两个半满页，更新父节点索引并写 WAL 日志，每次分裂约增加 30% 的写入延迟。随机插入的分裂频率远高于顺序插入，使用自增主键可将分裂限制在最右页。页面合并在删除后触发，但大多数实现采用保守策略，只在低于最小填充率时合并。工程优化策略包括：自增主键避免随机分裂、降低填充因子预留空间、批量加载时关闭索引后重建。对于写入密集型场景，LSM-Tree 是 B+ 树的替代方案，但需权衡读取放大的代价。