B+ 树是为磁盘/外存优化的平衡多路搜索树，是 MySQL InnoDB、Oracle、PostgreSQL 等数据库索引与多种文件系统的核心结构。相对 B 树，最大特点是叶子节点构成有序双向链表，范围查询极高效。
核心特性（m 阶 B+ 树）
- 多路平衡：每个节点最多
m个子节点，所有叶子在同一层 - 数据分离：内部节点只存 key + 子节点指针，叶子节点才存数据
- 叶子链表：所有叶子按 key 序由双向链表串联，支持 O(n) 范围扫描
- 节点填充：根至少 2 个子节点；非根节点至少 ⌈m/2⌉ 个子节点
基本操作
| 操作 | 流程 |
|---|---|
| 查找 | 根节点二分 → 递归向下 → 叶子节点定位 key |
| 插入 | 找叶子 → 节点未满直接插；满则分裂，中间 key 上升至父节点 |
| 删除 | 删叶子 key → 键数过少时向兄弟借键，否则与兄弟合并 |
百万级数据下树高仅 3-4 层，单次查询 IO 通常 ≤ 4 次。
B+ 树 vs B 树
| 特性 | B+ 树 | B 树 |
|---|---|---|
| 数据存储位置 | 仅叶子节点 | 所有节点 |
| 范围查询 | 极高效（链表遍历） | 低效（中序回溯） |
| IO 效率 | 内部节点更小、树更矮 | 节点更大 |
| 查找路径 | 必查至叶子，性能稳定 | 命中位置不固定 |
为何数据库选 B+ 树
- 极低磁盘 IO：节点对齐磁盘页（4–16 KB），阶数高（100+），树极矮
- 范围查询王者：
BETWEEN/ORDER BY直接遍历叶子链表 - 全表扫描快：顺链表读，无需中序回溯
- 性能可预测：所有操作 O(logₘN)，不存在抖动
典型应用
- 数据库索引：MySQL InnoDB、Oracle、SQL Server、PostgreSQL
- 文件系统：NTFS、HFS+、Ext4
- 键值存储：LevelDB、RocksDB（写路径用 LSM-Tree，读端常配 B+ 树类索引）