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

B+树是MySQL最常见的索引结构，大部分存储引擎都支持 B+ 树索引。

相对于其他竞争力强的数据结构，B+树都有战胜它们成为大多时候MySQL选择使用索引结构的理由：

第一个强有力的竞争对手是B树：

1. B树每个节点都存储了完整的数据，而B+树只有叶子节点存储了完整的数据，非叶子节点只存储key和指针，这样B+树的非叶子节点可以存更多的键，从而减少树的高度，减少磁盘I/O次数。

2. 经典的B+树叶子节点会形成单链表，MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加一个指向相邻叶子节点的链表指针，使得这棵B+树的叶子节点形成了有序的双向链表。所以相比B树，B+树可以进行更高效的范围查询。

用100 65 169 368 900 556 780 35 215 1200 234 888 158 90 1000 88 120 268 250 分别构建B树和典型B+树、

B树：

B+树：

在进行范围查询时，B+ 树可以先通过索引快速定位到范围的起始值所在的叶子节点。由于叶子节点是通过双向链表相连的，后续可以沿着链表顺序遍历，依次获取满足范围条件的所有数据记录。

但是B树要进行范围查询频繁回溯到父节点查找下一个节点，会造成更多次的磁盘I/O。

3. 相对于B树，B＋树拥有更稳定的查询性能。B+树的所有查询路径等长，每次查询都需要从根节点到叶子节点，路径长度相同，性能稳定（O(logN)）。B树的数据可能分布在任意节点，某些查询可能在中间节点直接命中，查询性能不稳定。

另一个竞争者是二叉树（如红黑树） 相对于二叉树，树高较高（log₂N），存储海量数据时I/O次数远超B+树。这是因为B+树是多叉树，非叶子节点只存储key和指针，内存中能存放更多索引，容易命中缓存，使得磁盘I/O次数减少。

B+树从根节点到叶子节点的路径长度（即树高）直接决定磁盘I/O次数。

• 树高为3 → 最多3次磁盘I/O即可定位数据。

• 树高为4 → 最多4次磁盘I/O。

还有，B+树拥有高效的查找性能，它是多路平衡搜索结构，能减少磁盘 I/O 操作，还可像二分查找一样快速定位数据，数据存储具有冗余与可靠性的特点，能适应动态数据变化，在数据插入和删除时可通过结构调整保持平衡和有序。

而且B+树的节点大小通常设计成和磁盘页的大小一致，这样每次读取一个节点刚好是一个磁盘页，减少I/O次数。

我们反复提到了B+树可以减少磁盘I/O次数，为什么要那么在乎磁盘I/O次数呢？

磁盘I/O（Input/Output）是计算机从磁盘读取数据到内存（读I/O），或将内存数据写入磁盘（写I/O）的过程。

这是因为

• 磁盘访问速度远慢于内存：

  • 内存访问速度：纳秒级（约100ns）。

  • 磁盘访问速度（机械硬盘）：毫秒级（约10ms），比内存慢10万倍！

• 减少磁盘I/O是MySQL性能优化的核心目标之一。

综上，B+树在磁盘I/O效率、范围查询性能、稳定性和存储利用率之间取得了最佳平衡，使其成为数据库索引的理想选择。