B+ Tree

B+ Tree 是关系型数据库索引的主流数据结构，MySQL InnoDB、PostgreSQL、etcd（boltdb）均以 B+ Tree 为核心。本文深入 B+ Tree 的节点结构、插入分裂、删除合并等算法细节，并与 B-Tree、LSM Tree 做深度对比。

相关文章：LSM Tree · SSTable

目录

为什么需要 B+ Tree

磁盘 I/O 是瓶颈，每次读取一个磁盘页（通常 4KB 或 16KB），树的每一层 = 一次磁盘 I/O。

二叉搜索树（BST）：
  1亿个节点 → 树高 ≈ log₂(1亿) ≈ 27 层
  每次查找 = 27 次磁盘 I/O → 极慢

B+ Tree（阶数 m=100，每个节点存 100 个 key）：
  1亿个节点 → 树高 ≈ log₁₀₀(1亿) ≈ 4 层
  每次查找 = 4 次磁盘 I/O → 可接受

关键：每个节点 = 一个磁盘页，节点越大树越矮

B+ Tree vs B-Tree

节点结构

内部节点（Internal Node）

┌────┬────┬────┬────┬────┬────┬────┐
│ P0 │ K1 │ P1 │ K2 │ P2 │ K3 │ P3 │
└────┴────┴────┴────┴────┴────┴────┘

P0: 指向 key < K1 的子树
P1: 指向 K1 ≤ key < K2 的子树
P2: 指向 K2 ≤ key < K3 的子树
P3: 指向 key ≥ K3 的子树

n 个 key → n+1 个指针（孩子数比 key 多 1）

叶节点（Leaf Node）

┌────┬────┬────┬────┬────┬────┬────┐
│ K1 │ V1 │ K2 │ V2 │ K3 │ V3 │ →  │
└────┴────┴────┴────┴────┴────┴────┘
                                  ↑
                           指向下一个叶节点（链表）

存储实际 key-value 对
最右侧指针指向下一叶节点（支持范围扫描）

核心操作

查找（Search）

查找 key=X：
  从根节点开始
  当前节点为内部节点：
    二分查找确定 key 落在哪个指针范围 → 沿指针下降
  当前节点为叶节点：
    二分查找 key，找到则返回 value，否则不存在

时间复杂度：O(log_m N)，m 为阶数，N 为 key 总数
磁盘 I/O：= 树高次（通常 3~4 次）

插入与节点分裂

插入 key=X, value=V：
1. 查找目标叶节点 L
2. if L 未满（key 数 < m-1）：
     直接插入，保持有序 ✅
3. if L 已满：
     分裂：
       将 L 的 m 个 key 平均分成两半
       左半部分留在 L，右半部分放入新节点 L'
       将 L' 的最小 key 上推到父节点
     if 父节点也满了：
       递归向上分裂，直到根节点

示例（阶数 m=4，叶节点最多 3 个 key）：
  插入 35 到已满节点 [10, 20, 30]：
    分裂为 [10, 20] 和 [30, 35]
    将 30 上推到父节点

删除与节点合并/借用

删除 key=X：
1. 查找并删除叶节点中的 key
2. if 叶节点 key 数 ≥ ceil(m/2)（未下溢）：
     直接删除 ✅
3. if 下溢（key 数 < ceil(m/2)）：
     尝试从相邻兄弟节点借 key：
       if 兄弟节点有多余 key：
         借一个过来（通过父节点中转），更新父节点 key ✅
     if 兄弟节点也紧张（无多余 key）：
       合并：将当前节点与兄弟节点合并为一个节点
             父节点删除对应的分隔 key
             if 父节点也下溢，递归向上处理

最坏情况：级联合并直到根节点（树高减 1）

异常场景

并发写（B-link Tree 方案）

问题：节点分裂是非原子操作，并发读写可能看到中间状态

经典解法（B-link Tree）：
  每个节点增加一个"右指针"指向相邻的右兄弟节点
  分裂时先完成右节点写入，再更新父节点
  读线程：如果发现自己需要的 key 比当前节点的最大 key 还大
          沿右指针横向移动，无需加写锁

MySQL InnoDB 的做法：
  使用 latch（轻量级锁）保护 B+ Tree 节点
  乐观模式：先无锁读，如需分裂则升级为写锁
  悲观模式：从上往下加写锁（代价高，只在必要时用）

WAL 保证崩溃恢复

问题：节点分裂/合并涉及多个磁盘页的写入，崩溃可能破坏树结构

解法：Write-Ahead Log（WAL）
  所有修改先写 WAL（顺序写）
  再修改实际 B+ Tree 页（随机写）
  崩溃后根据 WAL 重放，恢复到一致状态

MySQL InnoDB：redo log 保证 B+ Tree 修改的原子性

树倾斜（顺序插入导致）

问题：按顺序插入（如自增 ID）时，所有分裂都发生在最右侧
     大量空间浪费在"半满"节点上（填充率约 50%）

解法：
  MySQL InnoDB innodb_fill_factor（默认 93%）：
    叶节点不填满，预留空间给后续插入，减少分裂
  或：使用 UUID 主键（但会导致随机 I/O，另一个问题）

与 LSM Tree 对比

实际应用

参考资料

• Comer, D. (1979). The Ubiquitous B-Tree. ACM Computing Surveys.
• MySQL InnoDB B+ Tree 实现：https://dev.mysql.com/doc/refman/8.0/en/innodb-physical-structure.html
• 《Designing Data-Intensive Applications》Ch.3 — B-Trees