B+树 范围查询_Mysql为什么使用B+树而不是B树？

最初出现的是普通二叉搜索 tree（简称 B 树），后来随着技术的发展与应用需求的增长，在随后的时间里出现了一种改进型的数据结构——即 B⁺ 树（英文全称 Binary Tree of Order n plus leaves）。然而，在数据库领域中，以 MySQL 为代表的数据库系统广泛采用的是基于这种改进型的数据结构——即 B⁺ 树。它们之间的主要区别体现在两个方面：1）在非叶节点中没有存储指向具体数据的指针信息；2）所有的叶节点不仅包含指向具体数据的指针信息，并且这些叶节点是按索引顺序构成一个单向链表（chain）。如图所示

MySQL为何选用B+树而非传统B树作为索引数据结构？其主要原因是三点因素共同作用的结果。在阐述这三个主要原因之前，请先了解 MySQL 在采用 B+ 树时采用了特殊的节点尺寸设计：每个节点的尺寸经过精心规划是为了确保每次获取节点数据时不跨越内存页边界。这种做法不仅保证了查询效率的提升，在后续三个主要原因中将得到详细阐述：首先是空间利用率最大化；其次是减少I/O操作次数；最后是提升并发处理能力。这些因素共同作用下使得 B-Tree 的应用效果得到了显著提升

【原因一】 B+树的叶子节点链在一起增加范围查询的效率

为何仅在叶节点处存储数据指针？这样的做法实际上要求每次查询都必须找到对应的叶节点才能返回数据。背后原因是因为这一做法虽然会增加每次查询所需进行的判断次数, 但若配合采用将叶节点串联起来的方法, 则能够显著提升范围查询的效率.

以图B树为例，在实际应用中为了查找所有大于2的数据，则必须首先定位到数值等于2的节点位置。随后通过中序遍历的方式可以依次访问并获取3、4、5、6和7这些节点对应的数值信息。该操作的时间复杂度为O(n)，然而，在操作过程中需要临时存储一些节点信息。值得注意的是由于空间复杂度也是O(n)在每个节点占用一个内存页大小的情况下这种做法可能会带来额外的资源消耗从而未必是一个理想的选择。

然而B+树通过将叶子节点链起来，在空间复杂度O(1)的方向上实现了范围遍历。

原因二

基于每个节点占据固定内存页大小的原则，在设计上实现了结构上的优化与改进。其内部节点均附带有指向相应数据的指针特性相对较为突出。相比之下，在B+树中仅有终端节点包含指向数据的指针这一特点使得其在存储能力上有所差异。因此，在非终端节点中可容纳更多索引信息从而导致整个树的高度降低进而减少了I/O操作次数并使访问效率显著提升。

【原因三】查询、插入、删除数据的时间稳定

通常情况下，在多数应用场景中，系统性能不必追求最优；然而必须保持稳定。在B+树结构中，所有指向数据元素的指针都被存储在叶子节点位置。因此，在进行查询、插入或删除操作时，则需要依次访问每一层直到最底层的数据节点。这与B树不同之处在于，在B树中可能在任意一层找到数据；而采用这种层级分布方式后，在实际应用中选择使用该结构能显著提升系统的稳定性。