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

回答重点

B+ 树在数据库系统中具有以下几个显著优势：

1）高效的查找性能：

B+ 树是一种自平衡树，每个叶子节点到根节点的路径长度相同，B+ 树在插入和删除节点时会进行分裂和合并操作，以保持树的平衡，但它又会有一定的冗余节点，使得删除的时候树结构的变化小，更高效。

查找、插入、删除等操作的时间复杂度为 O(log n)，能够保证在大数据量情况下也能有较快的响应时间。

2）树的高度增长不会过快，使得查询磁盘的 I/O 次数减少：

B+ 树不像红黑树，数据越多树的高度增长就越快。它是多叉树，非叶子节点仅保存主键或索引值和页面指针，使得每一页能容纳更多的记录，因此内存中就能存放更多索引，容易命中缓存，使得查询磁盘的 I/O 次数减少。

3）范围查询能力强：

B+ 树特别适合范围查询。因为叶子节点通过链表链接，从根节点定位到叶子节点查找到范围的起点之后，只需要顺序扫描链表即可遍历后续的数据，非常高效。

1）B 树每个节点都存储了完整的数据，而 B+ 树非叶子节点仅存储 key 和指针，完整数据存储在叶子节点。这使得 B+ 树可以在内存中存放更多索引页，减少磁盘查询次数。

2）B+ 树叶子组成了链表，便于区间查找，而 B 树只能每一层遍历查找。

3）B+ 树查询时间更平均、稳定，都需要从根节点扫描到叶子节点。而 B 树则在非叶子节点就可能找到对应的数据返回。