为什么 MySQL选择使用 B+树作为索引结构?

B+树的基本结构

B+树是一种多路平衡查找树，它由B树演变而来。在B+树中：

• 所有数据记录都存储在叶子节点上
• 非叶子节点只存储键值和指针，不存储数据
• 所有叶子节点通过指针连接成一个单向链表
• 树的高度通常较低，一般为2-4层

与其他数据结构的比较

相比B树

• B+树所有数据都在叶子节点，非叶子节点不存储数据，更适合磁盘存储
• B+树叶子节点相互链接，更有利于范围查询和全表扫描
• B+树非叶子节点只存键值，在相同内存下可以存储更多索引条目

相比红黑树

• 红黑树是二叉树，树高较高，可能导致更多的磁盘IO
• B+树是多路树，降低树高，减少磁盘IO次数
• 对于大数据量，红黑树的查询效率明显低于B+树

相比哈希表

• 哈希表不支持范围查询和排序操作
• 哈希表在数据量大时性能可能下降(哈希冲突)
• B+树支持范围查询和有序访问

磁盘IO优化

• B+树的高扇出性(一个节点可以有多个子节点)使树的高度较低
• 树高降低意味着查询时磁盘IO次数减少
• MySQL页大小通常为16KB，配合B+树结构可以在一次IO中读取更多索引

顺序访问性能

• B+树叶子节点通过链表相连，顺序访问只需要沿着链表遍历
• 范围查询效率高，只需找到范围起点，然后沿链表顺序访问
• ORDER BY、GROUP BY等操作因此能高效执行

空间利用率

• B+树非叶子节点不存储数据，只存储键值和指针
• 在相同内存条件下，B+树能容纳更多索引条目
• 节点填充率高，空间利用效率好

缓存友好性

• B+树结构符合磁盘预读原理
• 适合局部性原理和磁盘预读，提高缓存命中率
• 结构紧凑，数据页可以有效利用CPU缓存

并发控制

• B+树结构便于实现锁粒度优化
• 非叶子节点修改概率低，减少锁冲突
• 适合InnoDB的MVCC(多版本并发控制)机制

实际性能表现

• 在常见数据量(千万级以上)下查询复杂度稳定在O(log n)
• 单次查询通常只需2-4次磁盘IO
• 范围查询性能优异，适合OLTP业务场景

总结

特性维度	B+树优势	对比其他数据结构
磁盘IO效率	树高低(2-4层)，减少IO次数	远优于红黑树，AVL树等二叉树结构
范围查询支持	叶子节点链表结构，支持高效范围访问	优于B树和哈希索引
空间利用率	非叶节点不存数据，相同空间存储更多索引	优于B树
缓存友好性	符合磁盘预读原理，提高缓存命中率	优于随机访问的结构
并发控制	便于实现锁粒度优化，减少锁冲突	更适合数据库事务处理
插入删除效率	平衡树结构，插入删除后仍保持平衡	优于不平衡的树结构
有序性	天然保持键值有序	优于哈希表等无序结构
查询稳定性	最坏情况性能有保障，O(log n)复杂度	优于哈希表(最坏O(n))

MySQL选择B+树作为索引结构是综合考虑了上述多方面因素的结果。这种数据结构在磁盘环境下能够提供出色的查询性能、良好的空间利用率以及对范围查询的支持，使其成为关系型数据库索引的理想选择。