一、问题背景
数据库索引需要同时满足：
- 等值查询：
SELECT * FROM user WHERE id = 1234 - 区间查询：
SELECT * FROM user WHERE id > 1000 AND id < 2000 - 低内存占用：索引可能对应上亿条数据，不可能全部放内存
- 高写入性能：插入/删除时索引维护代价不能太高
为什么散列表、平衡二叉树、跳表都不够好？
| 数据结构 | 等值查询 | 区间查询 | 磁盘友好 |
|---|---|---|---|
| 散列表 | O(1) | ❌ 不支持 | 一般 |
| AVL/红黑树 | O(log n) | 需中序遍历 | ❌ 树高大，IO 多 |
| 跳表 | O(log n) | ✅ 链表遍历 | 一般 |
| B+树 | O(log_m n) | ✅ 叶子链表 | ✅ 矮胖，IO 少 |
二、从二叉树到 B+树的演化
2.1 二叉查找树 + 叶子链表
将 BST 的叶子节点用链表串联 → 支持区间查询。
问题：树高 = log₂n。1 亿数据 → 树高约 27 层 → 27 次磁盘 IO。
2.2 降低树高：m 叉树
将每个节点扩展为 m 个子节点：
| 数据量 | 二叉树高 | 100 叉树高 |
|---|---|---|
| 1 亿 | 27 | 4 |
| 10 亿 | 30 | 5 |
树高 = 磁盘 IO 次数。m 越大，树越矮，IO 越少。
2.3 m 值如何确定？
操作系统按**页（Page）**读取磁盘，通常 4KB/页。
设计原则：让每个节点大小恰好等于一页，读一个节点 = 一次 IO。
PAGE_SIZE = (m-1) × key_size + m × child_pointer_size
例如 key=8B，指针=8B，页=16KB：m ≈ 16384/16 ≈ 1000。
三、B+树结构
3.1 核心特征
Mermaid · 渲染中（下方为源码）
graph TD R[30 | 60] --> A[10|20|30] R --> B[40|50|60] R --> C[70|80|90] A --> A1[data] B --> B1[data] C --> C1[data] A1 -.->|next| B1 B1 -.->|next| C1
| 特征 | 说明 |
|---|---|
| 非叶节点只存索引 | 不存数据，最大化扇出 |
| 叶子节点存数据 | 包含键值 + 数据地址 |
| 叶子节点双向链表 | 支持正/反向区间扫描 |
| 所有叶子同层 | 保证等值查询路径等长 |
| 节点子树数 ∈ [⌈m/2⌉, m] | 保证树不会太"瘦" |
3.2 与 B 树的区别
| 对比项 | B 树 | B+树 |
|---|---|---|
| 数据存储位置 | 所有节点 | 仅叶子节点 |
| 叶子链表 | 无 | 有（双向） |
| 区间查询 | 需中序遍历 | 叶子链表顺序扫描 |
| 非叶节点大小 | 较大（含数据） | 较小（纯索引）→ 扇出更大 |
四、B+树操作
4.1 查找
- 从根节点开始，二分查找确定子树方向
- 逐层下降直到叶子节点
- 在叶子节点中定位目标 key
- 区间查询：定位起点后，沿叶子链表顺序扫描
4.2 插入与分裂
当某节点子节点数超过 m 时触发分裂：
- 将节点一分为二，中间键值上提到父节点
- 父节点若也超限，级联分裂直到根节点
- 根节点分裂时树高 +1
4.3 删除与合并
当某节点子节点数少于 ⌈m/2⌉ 时触发合并：
- 先尝试向兄弟节点"借"一个子节点
- 借不到则与兄弟合并
- 合并后父节点可能也需要合并（级联）
五、代码结构
// 非叶子节点
public class BPlusTreeNode {
public static int m = 5; // m 叉树
public int[] keys = new int[m - 1]; // 键值，划分数据区间
public BPlusTreeNode[] children = new BPlusTreeNode[m];
}
// 叶子节点
public class BPlusTreeLeafNode {
public static int k = 3;
public int[] keys = new int[k]; // 数据键值
public long[] dataAddr = new long[k]; // 数据磁盘地址
public BPlusTreeLeafNode prev; // 双向链表前驱
public BPlusTreeLeafNode next; // 双向链表后继
}六、MySQL InnoDB 中的 B+树
6.1 聚簇索引 vs 二级索引
| 索引类型 | 叶子节点存储 | 说明 |
|---|---|---|
| 聚簇索引（主键） | 完整行数据 | 一张表只有一个 |
| 二级索引（非主键） | 主键值 | 查完整行需"回表" |
6.2 为什么用 B+树而非 Hash？
- Hash 不支持范围查询（
WHERE age BETWEEN 20 AND 30） - Hash 不支持排序（
ORDER BY） - Hash 不支持最左前缀匹配（联合索引）
6.3 为什么用 B+树而非红黑树？
- 红黑树高 ≈ log₂n，1 亿数据约 27 层 → 27 次 IO
- B+树高通常 3
4 层 → 34 次 IO - B+树叶子链表天然支持范围扫描
七、索引的代价
| 代价 | 说明 |
|---|---|
| 写入变慢 | 每次 INSERT/UPDATE/DELETE 都要维护索引 |
| 空间占用 | 每个索引都是一棵独立的 B+树 |
| 优化器选择 | 索引过多时优化器可能选错索引 |
实践建议：单表索引不超过 5~6 个；高频查询字段建索引，低区分度字段（如性别）不建。
八、面试高频题
Q：一棵 B+树能存多少数据？
假设：主键 bigint=8B，指针=6B，页=16KB。
- 非叶节点扇出：16KB / (8+6) ≈ 1170
- 叶子节点：假设每行 1KB，每页存 16 行
- 三层 B+树：1170 × 1170 × 16 ≈ 2190 万行
Q：B+树中叶子链表是单向还是双向？
InnoDB 使用双向链表，支持 ORDER BY ... DESC 反向扫描。
九、总结
B+树是磁盘 IO 友好的多路平衡搜索树，核心设计哲学：
- 矮胖：大扇出 → 少 IO
- 叶子链表：区间查询 O(结果集)
- 非叶纯索引：最大化每页存储的键值数
- 节点 = 页：每次 IO 恰好读一个节点