面试题：MySQL中B+树索引如何提高范围查询性能

Question

在MySQL的B+树索引结构下，阐述它是如何在范围查询场景中，相比其他数据结构（如哈希表）显著提升查询性能的，请结合B+树的结构特点进行说明。

Answer 1

1. B+树结构特点
   • 节点类型与数据存储：
     • B+树有内部节点（非叶子节点）和叶子节点。内部节点只存储索引键，不存储具体数据记录，而叶子节点存储了索引键及对应的实际数据记录（或数据指针）。所有叶子节点通过双向链表相连。
   • 层级关系与平衡特性：
     • B+树是一种平衡树，每个节点的子节点数量在一定范围内（通常是最小度数t和最大度数2t之间）。这种平衡结构使得从根节点到叶子节点的路径长度基本相同，保证了查询的时间复杂度相对稳定。
2. 范围查询优势
   • 有序性支持：
     • 由于B+树叶子节点按索引键有序排列，在进行范围查询时，可以从满足范围下限的节点开始，沿着叶子节点的双向链表依次遍历，直到范围上限。例如，要查询age在20到30之间的记录，如果age字段建立了B+树索引，数据库可以快速定位到age = 20的叶子节点，然后顺着链表查找，直到找到age = 30的节点，这种有序遍历方式效率较高。
   • 减少I/O操作：
     • B+树的结构设计使得相关数据在磁盘上相对集中存储。在范围查询时，通过树的层级结构，能够快速定位到包含目标数据的叶子节点区域。由于节点存储容量较大（通常与磁盘块大小匹配），一次I/O操作可以读取多个索引项。例如，一个磁盘块可以存储多个叶子节点的索引项，在遍历链表进行范围查询时，相比无序存储结构，I/O操作次数显著减少，从而提升了查询性能。
3. 与哈希表对比
   • 哈希表特性：
     • 哈希表通过哈希函数将键值映射到特定位置，查询单个键值的时间复杂度接近O(1)。然而，哈希表不具备有序性，数据在存储上是无序分布的。
   • 哈希表在范围查询的劣势：
     • 对于范围查询，哈希表需要对整个哈希表进行遍历，逐个检查每个键值是否在范围内。这意味着需要读取大量不必要的数据，I/O操作次数多，时间复杂度接近O(n)，相比B+树在范围查询场景下性能明显较差。