为什么 B+Tree？

B+Tree 是数据库索引的事实标准。相比 B-Tree：

  • 叶子节点存数据，内部节点只存 Key，树更矮（减少 IO）
  • 叶子节点形成链表，支持高效范围查询
  • 所有数据在同一层，查找性能稳定

节点结构

内部节点 (Internal Node):
┌──────────────────────────────────────────┐
│  [P0] K1 [P1] K2 [P2] ... Kn [Pn]       │
│   ↓       ↓       ↓           ↓          │
│  <K1    K1~K2   K2~K3       >Kn         │
└──────────────────────────────────────────┘

叶子节点 (Leaf Node):
┌─────────────────────────────────────────────┐
│ [K1, Data1] [K2, Data2] ... [Kn, DataN] →  │
│                                          next │→
└─────────────────────────────────────────────┘

核心操作

插入 (Insert)

  1. 定位目标叶子节点
  2. 如果节点有空间 → 直接插入
  3. 如果节点已满 → 分裂 (Split)：
    • 分配新节点
    • 将一半 Key 移动到新节点
    • 在父节点插入分隔 Key
    • 递归向上传播分裂
分裂前:  [10, 20, 30, 40, 50] (order=5, 已满)
         │
分裂后:  [10, 20, 30] → 父节点 [40]
         [40, 50]         [10, 20, 30] [40, 50]

删除 (Delete)

  1. 定位目标叶子节点
  2. 删除 Key
  3. 如果节点小于半满 → 合并 (Merge) 或 借用 (Redistribution)
借用 (从左兄弟):
[10, 20] → [10] (半满)    → 从父节点拉下 30，从右兄弟拉上 35
[30, 35, 40]              → [30, 35] [40]

并发控制

多线程环境下 B+Tree 需要保证一致性：

Latch Crabbing 协议

搜索阶段: 父节点未安全 → 锁住子节点，释放父节点
分裂阶段: 锁住路径上所有节点，向上传播
安全节点: 不分裂的节点 → 可以释放祖先锁

乐观锁方案

  • 假设树结构不变（大部分操作不触发分裂/合并）
  • 搜索时用读锁
  • 如果发现需要修改 → 重新获取写锁
  • MySQL InnoDB 和 PostgreSQL btree 索引均采用此策略

聚簇索引 vs 二级索引

类型 叶子节点存什么 特点
聚簇索引 完整数据行 数据即索引，物理排序
二级索引 主键引用 需要回表查询

MySQL InnoDB 的主键索引是聚簇索引，数据按主键顺序物理存储。PostgreSQL 不使用聚簇索引，所有索引都是二级索引（指向 CTID）。

B+Tree 变体

  • B-link Tree：叶子节点 + 兄弟指针（所有 B+Tree 均支持）
  • B*-Tree：分裂时将数据分到两个兄弟节点，减少分裂频率
  • Fractal Tree：在内部节点缓冲写入，批量应用到叶子

总结

  • B+Tree 通过控制树的高度和节点扇出，实现 O(log n) 查找
  • 分裂/合并操作是写性能的主要影响因素
  • 并发控制需要在正确性和性能间权衡
  • 聚簇索引 vs 非聚簇索引的选择影响业务查询模式

参考