B+ 树索引：MySQL 的「字典查找术」
你有没有想过这个问题：
MySQL 的 InnoDB 引擎，为什么选择 B+ 树作为默认索引结构，而不是二叉树、红黑树、B 树？
有人说：「因为 B+ 树查询快啊。」
这话对，但太浅了。
今天，我们从磁盘 I/O 的视角出发，彻底理解 MySQL 为什么选 B+ 树。
从一个故事开始
想象你要在一本《新华字典》中查「 MySQL 」这个词。
你会怎么做？
方法一：从第一页开始，一页一页翻，直到找到目标。运气好翻几页，运气差翻几万页。
方法二：先查拼音索引（部首索引），锁定大概范围，然后再翻到具体页码。
显然，方法二是人类的最优选择。
MySQL 选择 B+ 树，就是给数据造了一本「字典」。
为什么不用二叉树或红黑树？
二叉树的特点是每个节点最多有两个子节点，树高 = log₂(n)。
听起来不错，但问题出在哪里？
假设我们有 100 万条数据，二叉树的树高大约是 20。这意味着一次查询最多要 20 次磁盘 I/O。
100 万条数据：
- 二叉搜索树高度：约 20
- 红黑树高度：约 27（因为是平衡二叉树，变种）
- B+ 树高度：约 3-4
100 万条数据用二叉树，树高 20，意味着最坏情况要 20 次磁盘 I/O。
每次磁盘 I/O 的耗时大约是 5-10 毫秒（机械硬盘），20 次就是 100-200 毫秒。这还没算上 CPU 计算的时间。
而 B+ 树高只有 3-4，同样的查询只需要 3-4 次 I/O，耗时不到 50 毫秒。
B+ 树的秘密结构
先回忆一下 B 树的特点：
- 所有节点都存储数据
- 每个节点的子节点数有一个范围（通常是 [m/2, m]）
B+ 树在 B 树的基础上做了两个关键改进：
- 非叶子节点不存储数据，只存储索引
- 叶子节点存储所有数据，且用双向链表连接
B+ 树结构示意（假设每个节点最多 4 个指针）：
[P1| |P2| |P3| |P4] ← 非叶子节点（只存索引）
/ | \
[P1| |P2] [P1| |P2] [P1| |P2] ← 非叶子节点
/ | \ / | \ / | \
数据页 数据页 数据页 数据页 数据页 ← 叶子节点（双向链表）非叶子节点为什么只存索引？
因为这样可以让每个节点「更胖」。
假设一个非叶子节点存 1000 个索引，每个索引占 8 字节，那这个节点最多指向 1000 个子节点。
根节点如果也存 1000 个索引，那么：
- 2 层 B+ 树：1000 × 1000 = 100 万数据
- 3 层 B+ 树：1000 × 1000 × 1000 = 10 亿数据
大多数业务场景，3 层 B+ 树就够用了。
这意味着：查询任何一条数据，最多只需要 3 次磁盘 I/O。
B+ 树的查询过程
假设我们要查找 id=15 的记录：
public class BTreeSearch {
/**
* B+ 树的查询流程
* @param rootPage 根节点
* @param targetId 目标 ID
* @return 查询结果
*/
public BTreeResult search(Page rootPage, long targetId) {
// 从根节点开始
Page current = rootPage;
// 逐层向下查找，直到叶子节点
while (!current.isLeaf()) {
// 在当前节点的有序索引中，二分查找第一个大于 targetId 的位置
int index = binarySearch(current, targetId);
// 沿着对应指针进入子节点
current = current.getChildPage(index);
}
// 到达叶子节点后，在数据页中二分查找目标记录
int index = binarySearch(current, targetId);
if (index >= 0 && current.getRecord(index).getId() == targetId) {
return new BTreeResult(current.getRecord(index), true);
}
return new BTreeResult(null, false);
}
}查询过程图解
查找 id=15 的记录：
Step 1: 读取根节点页（磁盘 I/O 1）
┌────────────────────────────────────┐
│ P1(1) | P2(10) | P3(20) | P4(30) │
└────────────────────────────────────┘
↑
10 < 15 < 20，走 P3 指针
Step 2: 读取中间节点页（磁盘 I/O 2）
┌────────────────────────────────────┐
│ P1(11) | P2(13) | P3(15) | P4(17) │
└────────────────────────────────────┘
↑
查找到 15，就是这个叶子页的指针
Step 3: 读取叶子节点页（磁盘 I/O 3）
┌────────────────────────────────────────────┐
│ 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 │
└────────────────────────────────────────────┘
↑
找到 id=15 的记录！B+ 树 vs 红黑树：为什么 MySQL 不选红黑树？
| 对比项 | B+ 树 | 红黑树 |
|---|---|---|
| 树高 | 3-4 层 | 20-30 层 |
| 单次查询 I/O 次数 | 3-4 次 | 20-30 次 |
| 范围查询 | 链表遍历，O(n) | 需要中序遍历 |
| 插入/删除 | 只需修改局部节点 | 可能触发多次旋转 |
| 磁盘友好性 | 节点大小=页大小(16KB) | 节点大小=指针+数据 |
红黑树的节点大小是一个索引 + 两个指针 + 颜色位，通常只有几十字节。
而 MySQL InnoDB 的页大小是 16KB，一个 B+ 树节点可以容纳数千个索引。
这就是本质区别：B+ 树是针对磁盘 I/O 优化的树结构，红黑树是针对内存操作优化的树结构。
页面（Page）：MySQL 磁盘读写的最小单位
InnoDB 中，磁盘和内存交互的基本单位是页，默认为 16KB。
一个 B+ 树节点（无论是索引节点还是叶子节点）都对应一个页。
// InnoDB Page 结构伪代码
public class Page {
// 页头信息（38 字节）
private PageHeader header; // 页的基本信息
private PageBody body; // 页的实际数据
// 页的默认大小
public static final int SIZE = 16 * 1024; // 16KB
// 一个页能存多少索引？
// 假设主键是 bigint(8字节)，指针是 6 字节，每个索引 = 14 字节
// (16KB - 页头38字节) / 14 ≈ 1170 个索引
}这就解释了为什么 B+ 树可以做到很「矮」——每个节点能存 1000+ 个索引，3 层就能存 10 亿级别数据。
思考题
B+ 树的插入和删除操作如何保持平衡？
A: 和 B 树一样，通过分裂和合并节点来维持平衡 B: 通过旋转来调整结构 C: 删除操作直接删除节点
提示：MySQL 的 B+ 树索引是自平衡的，但和红黑树的旋转不同，B+ 树主要通过节点的分裂和合并来保持平衡。