为什么 MySQL 索引用的是 B+ 树而不是红黑树？
MySQL（特别是 InnoDB 存储引擎）选择B+ 树而不是红黑树（或普通的 B 树）作为索引结构，主要是为了优化磁盘 I/O 性能和适应数据库的存储场景。
数据库索引的核心挑战在于：数据量巨大，无法全部放入内存，必须存储在磁盘上。而磁盘 I/O 的速度远慢于内存访问速度（相差几个数量级）。因此，索引结构的设计目标就是尽量减少磁盘 I/O 次数。
以下是 B+ 树优于红黑树的核心原因：
1. 树的高度更低（减少磁盘 I/O 次数）
这是最根本的原因。
红黑树：是一种二叉树。每个节点只存储一个键值（Key）和一个数据指针。
- 假设每个节点占用 8KB（一个磁盘页），存储一个 8 字节的 Key 和 8 字节的指针，那么一个节点只能存约 500 个键值（实际上因为指针和元数据，可能更少，但为了对比，我们假设是二叉结构）。
- 如果要存储 1000 万条数据，红黑树的高度大约是log2(10,000,000)≈24\log_2(10,000,000) \approx 24log2(10,000,000)≈24层。
- 这意味着查询一条数据，最坏情况下需要24 次磁盘 I/O。
B+ 树：是一种多路平衡查找树。每个节点可以存储成百上千个键值。
- InnoDB 的默认页大小是 16KB。一个非叶子节点可以存储大量的索引键和子节点指针。
- 假设一个节点能存 1000 个键值（实际更多，因为非叶子节点只存 Key 和指针，不存数据）。
- 存储 1000 万条数据，B+ 树的高度大约是log1000(10,000,000)≈3\log_{1000}(10,000,000) \approx 3log1000(10,000,000)≈3层（根节点 + 2 层中间节点 + 叶子节点）。
- 这意味着查询一条数据，通常只需要3 次磁盘 I/O。
结论：B+ 树通过“宽而矮”的结构，极大地降低了树的高度，从而将磁盘 I/O 次数从几十次降低到 3-4 次，性能提升巨大。
2. 更适合范围查询
- 红黑树：范围查询（如
WHERE id > 100 AND id < 200）需要中序遍历整棵树。虽然时间复杂度是O(N)O(N)O(N)，但节点在磁盘上是随机分布的，遍历过程中需要频繁地进行磁盘 I/O 跳跃，效率极低。 - B+ 树：
- 所有数据都存储在叶子节点。
- 叶子节点之间通过双向链表连接。
- 进行范围查询时，只需要找到起始节点，然后沿着链表顺序读取即可。这变成了顺序 I/O，效率极高。
3. 查询性能更稳定
- 红黑树：虽然也是平衡树，但数据可能分布在树的任何层级。查询不同数据所需的 I/O 次数可能不同（虽然差异不大，但存在）。
- B+ 树：
- 所有查询都必须走到叶子节点才能获取数据。
- 这意味着任何查询的 I/O 次数都是固定的（等于树的高度），性能非常稳定，没有“快慢”之分。
4. 节点利用率与缓存友好性
- 红黑树：每个节点只存一个 Key，导致节点空间利用率低，且每个节点都需要加载到内存页中，缓存命中率低。
- B+ 树：
- 非叶子节点：只存 Key 和指针，不存数据。这使得非叶子节点可以容纳更多的 Key，进一步降低树高。
- 叶子节点：存 Key 和完整数据（聚簇索引）或主键（非聚簇索引）。
- 由于 B+ 树节点大小通常设计为与磁盘页（Page）大小一致（如 16KB），一次 I/O 就能加载一个完整的节点，充分利用了磁盘预读（Read-ahead）机制和 CPU 缓存行（Cache Line）。
5. 插入与删除的稳定性
- 红黑树：插入或删除节点后，可能需要大量的旋转操作来维持平衡，虽然时间复杂度是O(logN)O(\log N)O(logN)，但在磁盘环境下，频繁的节点分裂和合并会导致大量的随机 I/O。
- B+ 树：
- 插入和删除主要发生在叶子节点。
- 当节点满时，进行分裂（Split）；当节点空时，进行合并（Merge）。
- 由于 B+ 树节点能容纳大量数据，分裂和合并的频率相对较低，且操作更局部化，对磁盘 I/O 的冲击较小。
总结对比表
| 特性 | 红黑树 (Red-Black Tree) | B+ 树 (B+ Tree) | 对数据库的影响 |
|---|---|---|---|
| 树结构 | 二叉树 | 多路平衡查找树 | B+ 树更矮，I/O 次数少 |
| 树高度 | 高 (随数据量线性增长对数) | 低 (通常 3-4 层) | B+ 树查询更快 |
| 数据存储 | 任意节点 | 仅在叶子节点 | B+ 树范围查询极快 |
| 范围查询 | 需中序遍历，随机 I/O | 链表顺序遍历，顺序 I/O | B+ 树适合BETWEEN,>等 |
| 查询稳定性 | 波动 (取决于节点位置) | 稳定 (固定高度) | B+ 树性能可预测 |
| 磁盘 I/O | 频繁，随机 | 极少，顺序/预读友好 | B+ 树更适合磁盘存储 |
| 缓存友好性 | 差 | 好 (节点大小=页大小) | B+ 树内存利用率高 |
为什么不是 B 树？
既然 B+ 树这么好，那为什么不用B 树（B-Tree）呢？
B 树和 B+ 树很像，但 B 树的非叶子节点也存储数据。
- 缺点：非叶子节点存储数据后，能容纳的 Key 数量就变少了，导致树的高度比 B+ 树略高，I/O 次数略多。
- 范围查询：B 树的范围查询需要中序遍历，不如 B+ 树的链表遍历高效。
- 稳定性：B 树的数据可能分布在任意节点，查询性能不如 B+ 树稳定。
因此，B+ 树是专门为磁盘存储和数据库索引场景优化的数据结构，完美平衡了查询、插入、删除和范围扫描的性能。