B+ Tree 是关系型数据库索引的主流数据结构，MySQL InnoDB、PostgreSQL、etcd（boltdb）均以 B+ Tree 为核心。本文深入 B+ Tree 的节点结构、插入分裂、删除合并等算法细节，并与 B-Tree、LSM Tree 做深度对比。
目录
| 章节 | 说明 |
|---|---|
| 为什么需要 B+ Tree | 磁盘 I/O 模型与树高的关系 |
| B+ Tree vs B-Tree | 关键结构差异 |
| 节点结构 | 内部节点与叶节点的存储布局 |
| 核心操作 | 查找、插入分裂、删除合并 |
| 异常场景 | 并发写、磁盘页损坏、树倾斜 |
| 与 LSM Tree 对比 | 读写性能的根本差异 |
| 实际应用 | MySQL / PostgreSQL / etcd |
为什么需要 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
| 特性 | B-Tree | B+ Tree |
|---|---|---|
| 内部节点 | 存储 key + value | 只存储 key（不存 value） |
| 叶节点 | 存储 key + value | 存储 key + value，且相互链接 |
| 范围查询 | 需要中序遍历（复杂） | ✅ 叶节点链表，直接顺序扫描 |
| 空间利用率 | 低（内部节点占空间） | ✅ 高（内部节点只存 key，更矮） |
| 适用场景 | 文件系统（HFS+） | ✅ 数据库索引（主流选择） |
节点结构
内部节点（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 对比
| 维度 | B+ Tree | LSM Tree |
|---|---|---|
| 随机写 | ❌ 慢（随机 I/O，原地修改页） | ✅ 快（顺序写 WAL + MemTable） |
| 顺序写 | ⚠️ 中（分裂带来额外写入） | ✅ 极快 |
| 点查 | ✅ 快（树高固定，3~4 次 I/O） | ⚠️ 较慢（需查多层） |
| 范围扫描 | ✅ 极快（叶节点链表） | ⚠️ 需合并多个层的迭代器 |
| 空间放大 | ✅ 低（原地更新） | ⚠️ 旧版本延迟清理 |
| 写放大 | 中（WAL + 页修改） | 高（多次 Compaction） |
| 适合场景 | 读写均衡、事务、范围查询 | 写多读少、KV、时序数据 |
实际应用
| 系统 | B+ Tree 的角色 |
|---|---|
| MySQL InnoDB | 聚簇索引（主键）+ 二级索引均用 B+ Tree，页大小 16KB |
| PostgreSQL | 默认索引类型（BTREE），支持多列联合索引 |
| etcd（boltdb） | 底层存储引擎用 B+ Tree，支持 MVCC + 事务 |
| SQLite | 单文件数据库，B+ 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
评论 (0)
发表评论