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

MySQLInnoDB 引擎不使用红黑树而使用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×10ms240ms24 \times 10ms 240ms24×10ms240ms。这对于高并发数据库来说太慢了2. B 树矮胖结构特性多路平衡搜索树。一个节点可以包含多个键值Key和多个指针Child Pointer。阶数 (Order)假设一个节点大小为 16KBInnoDB 默认页大小每个键值指针占 100 字节则一个节点可存 ~160 个键值即 160 叉树。高度对于NNN个数据高度h≈log⁡mNh \approx \log_m Nh≈logm​N(mmm为阶数)。场景模拟1000 万条数据。第一层1 个根节点。第二层160 个节点。第三层160×16025,600160 \times 160 25,600160×16025,600个节点。第四层25,600×160≈40025,600 \times 160 \approx 40025,600×160≈400万 个节点足以覆盖千万级数据。结果高度仅为3-4 层。优势查找一条数据只需3-4 次磁盘 I/O。代价3×10ms30ms3 \times 10ms 30ms3×10ms30ms。性能提升近10 倍。 核心洞察在磁盘时代减少树的高度就是减少生命线的长度。B 树用“宽度”换“高度”从而极致压缩 I/O 次数。二、局部性原理预读的胜利1. 磁盘预读 (Read-Ahead)机制磁盘不是按字节读取而是按页 (Page)读取通常 4KB 或 16KB。即使你只请求 1 个字节操作系统也会把整个页加载到内存。红黑树劣势节点小分散在内存/磁盘的不同位置。访问子节点时很可能发生Cache Miss导致新的随机 I/O。无法充分利用预读机制。B 树优势节点大等于页大小。一次 I/O 加载整个节点里面包含了大量键值和子节点指针。空间局部性极好加载一个节点相当于加载了下一层的很多可能性。2. 缓存命中率B 树的非叶子节点只存索引KeyPointer不存数据。这意味着同样大小的内存可以缓存更多层级的索引节点。对于千万级数据根节点和第二层节点很容易常驻内存实际 I/O 往往只有 1-2 次。三、范围查询B 树的杀手锏数据库中大量的查询是范围查询WHERE id 100 AND id 200。1. 红黑树的困境中序遍历虽然红黑树也是有序的二叉搜索树可以进行中序遍历。问题节点在物理存储上是不连续的。过程找到起始节点 - 找后继节点可能需要回溯父节点- 再找后继…代价每次跳转都可能涉及指针跳跃缓存不友好效率低。2. B 树的天然优势链表结构B 树的所有叶子节点通过双向链表连接。过程找到范围起点几次 I/O。沿着叶子节点的链表顺序向后遍历主要在内存中顺序读取极少 I/O。效率范围查询效率极高几乎等同于顺序扫描。四、全表扫描与稳定性1. 全表扫描红黑树必须进行中序遍历递归或栈操作CPU 开销大缓存命中率低。B 树直接遍历叶子节点链表。这是最快的全表扫描方式之一。2. 查询性能稳定性红黑树不同数据的查找路径长度可能不同虽然平衡但仍有差异。B 树所有数据都存在叶子节点任何数据的查找路径长度完全相同。查询性能稳定没有波动。 总结红黑树 vs B 树 全景对比维度红黑树 (Red-Black Tree)B 树 (B Tree)谁胜节点度数2 (二叉)M (多叉通常 100)B 树树的高度高 (log⁡2N\log_2 Nlog2​N)矮 (log⁡MN\log_M NlogM​N)B 树(I/O 少)磁盘 I/O多 (随机 I/O)少 (利用预读)B 树范围查询弱 (需中序遍历)极强(叶子链表)B 树内存缓存节点小缓存率低节点大缓存率高B 树适用场景内存数据结构(STL map, Epoll)磁盘/数据库索引(MySQL, Oracle)各司其职 终极心法红黑树是内存的王者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 树依然是不可动摇的标准。