为什么MySQL选择使用B+树作为索引结构
为什么MySQL选择使用B+树作为索引结构
在数据库系统中，索引结构的选择对性能有着至关重要的影响。MySQL作为最流行的开源数据库之一，其选择B+树作为主要的索引结构绝非偶然。本文将深入探讨B+树相较于其他数据结构（如B树和二叉树）的优势，以及为什么这种选择能够显著提升数据库的查询效率。
B+树是MySQL最常见的索引结构，大部分存储引擎都支持 B+ 树索引。
相对于其他竞争力强的数据结构，B+树都有战胜它们成为大多时候MySQL选择使用索引结构的理由：
与B树的对比
存储方式的差异：B树每个节点都存储了完整的数据，而B+树只有叶子节点存储了完整的数据，非叶子节点只存储key和指针。这样B+树的非叶子节点可以存更多的键，从而减少树的高度，减少磁盘I/O次数。
范围查询的效率：经典的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。
- 查询性能的稳定性：相对于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+树的其他优势
高效的查找性能：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效率、范围查询性能、稳定性和存储利用率之间取得了最佳平衡，使其成为数据库索引的理想选择。