为什么 MySQL 不用红黑树做索引？

MySQL（InnoDB 引擎）不使用红黑树，而使用B+ 树，根本原因在于磁盘 I/O 的成本远高于内存计算。红黑树是内存友好型结构，而 B+ 树是磁盘友好型结构。

如果把数据存在内存里，红黑树（或 AVL 树）是非常优秀的选择；但数据库的主要瓶颈在于从磁盘读取数据。B+ 树通过“矮胖”的结构，极大地减少了磁盘 I/O 次数。

一、核心痛点：树的高度决定了 I/O 次数

数据库索引的核心目标是：用最少的磁盘 I/O 找到数据。

1. 红黑树：高瘦结构

• 特性：二叉平衡树，每个节点最多 2 个子节点。
• 高度：对于NNN个数据，高度h≈log⁡2Nh \approx \log_2 Nh≈log2​N。
• 场景模拟：
  • 假设表中有1000 万条数据。
  • 红黑树高度：log⁡2(10,000,000)≈24\log_2(10,000,000) \approx 24log2​(10,000,000)≈24层。
  • 最坏情况：查找一条数据可能需要访问24 个节点。
  • 致命伤：如果这 24 个节点不在内存中，就需要24 次磁盘 I/O。
  • 代价：机械硬盘随机 I/O 约 10ms/次。24×10ms=240ms24 \times 10ms = 240ms24×10ms=240ms。这对于高并发数据库来说太慢了！

2. B+ 树：矮胖结构

• 特性：多路平衡搜索树。一个节点可以包含多个键值（Key）和多个指针（Child Pointer）。
• 阶数 (Order)：假设一个节点大小为 16KB（InnoDB 默认页大小），每个键值+指针占 100 字节，则一个节点可存 ~160 个键值（即 160 叉树）。
• 高度：对于NNN个数据，高度h≈log⁡mNh \approx \log_m Nh≈logm​N(mmm为阶数)。
• 场景模拟：
  • 1000 万条数据。
  • 第一层：1 个根节点。
  • 第二层：160 个节点。
  • 第三层：160×160=25,600160 \times 160 = 25,600160×160=25,600个节点。
  • 第四层：25,600×160≈40025,600 \times 160 \approx 40025,600×160≈400万 个节点（足以覆盖千万级数据）。
  • 结果：高度仅为3-4 层。
  • 优势：查找一条数据只需3-4 次磁盘 I/O。
  • 代价：3×10ms=30ms3 \times 10ms = 30ms3×10ms=30ms。性能提升近10 倍。

💡 核心洞察：在磁盘时代，减少树的高度就是减少生命线的长度。B+ 树用“宽度”换“高度”，从而极致压缩 I/O 次数。

二、局部性原理：预读的胜利

1. 磁盘预读 (Read-Ahead)

• 机制：磁盘不是按字节读取，而是按页 (Page)读取（通常 4KB 或 16KB）。即使你只请求 1 个字节，操作系统也会把整个页加载到内存。
• 红黑树劣势：
  • 节点小，分散在内存/磁盘的不同位置。
  • 访问子节点时，很可能发生Cache Miss，导致新的随机 I/O。
  • 无法充分利用预读机制。
• B+ 树优势：
  • 节点大（等于页大小）。
  • 一次 I/O 加载整个节点，里面包含了大量键值和子节点指针。
  • 空间局部性极好：加载一个节点，相当于加载了下一层的很多可能性。

2. 缓存命中率

• B+ 树的非叶子节点只存索引（Key+Pointer），不存数据。
• 这意味着同样大小的内存，可以缓存更多层级的索引节点。
• 对于千万级数据，根节点和第二层节点很容易常驻内存，实际 I/O 往往只有 1-2 次。

三、范围查询：B+ 树的杀手锏

数据库中大量的查询是范围查询（WHERE id > 100 AND id < 200）。

1. 红黑树的困境

• 中序遍历：虽然红黑树也是有序的二叉搜索树，可以进行中序遍历。
• 问题：节点在物理存储上是不连续的。
• 过程：找到起始节点 -> 找后继节点（可能需要回溯父节点）-> 再找后继…
• 代价：每次跳转都可能涉及指针跳跃，缓存不友好，效率低。

2. B+ 树的天然优势

• 链表结构：B+ 树的所有叶子节点通过双向链表连接。
• 过程：
  1. 找到范围起点（几次 I/O）。
  2. 沿着叶子节点的链表顺序向后遍历（主要在内存中顺序读取，极少 I/O）。
• 效率：范围查询效率极高，几乎等同于顺序扫描。

四、全表扫描与稳定性

1. 全表扫描

• 红黑树：必须进行中序遍历，递归或栈操作，CPU 开销大，缓存命中率低。
• B+ 树：直接遍历叶子节点链表。这是最快的全表扫描方式之一。

2. 查询性能稳定性

• 红黑树：不同数据的查找路径长度可能不同（虽然平衡，但仍有差异）。
• B+ 树：所有数据都存在叶子节点，任何数据的查找路径长度完全相同。查询性能稳定，没有波动。

🚀 总结：红黑树 vs B+ 树 全景对比

💡 终极心法

红黑树是内存的王者，B+ 树是磁盘的霸主。

• 内存中：CPU 快，内存随机访问成本低，红黑树实现简单，旋转开销小，适合频繁增删改的内存集合。
• 磁盘中：I/O 慢如蜗牛，必须减少 I/O 次数。B+ 树通过“多叉”压低高度，通过“叶子链表”优化范围查，是专为磁盘设计的精密仪器。

MySQL 选择 B+ 树，不是因为红黑树不好，而是因为磁盘太慢。

于内存中见灵活，于磁盘中见厚重；以 I/O 为尺，解选型之牛，于数据存储中，求效率之真。

思考延伸：
随着SSD (NVMe)的普及，随机 I/O 速度大幅提升，是否还需要 B+ 树？

• 答案是：依然需要。虽然 SSD 快了 100 倍，但内存比 SSD 还是快 1000 倍以上。减少 I/O 依然是数据库优化的第一原则。而且 B+ 树的范围查询优势在 SSD 上依然存在。
• 未来趋势：LSM-Tree(Log-Structured Merge-tree) 在写密集型场景（如 RocksDB, HBase, Cassandra）中正在挑战 B+ 树的地位，但在通用关系型数据库（OLTP）中，B+ 树依然是不可动摇的标准。