MySQL为什么选择B+树作为索引结构？（详解）

B树的优势除了树高小，还有对访问局部性原理的利用。所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。

B树在数据库中有一些应用，如mongodb的索引使用了B树结构。但是在很多数据库应用中，使用了是B树的变种B+树。

五、B+树

B+树也是多路平衡查找树，其与B树的区别主要在于：

• B树中每个节点（包括叶节点和非叶节点）都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。在MySQL中，这里所说的真实数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。
• B树中一条记录只会出现一次，不会重复出现，而B+树的键则可能重复重现——一定会在叶节点出现，也可能在非叶节点重复出现。
• B+树的叶节点之间通过双向链表链接。
• B树中的非叶节点，记录数比子节点个数少1；而B+树中记录数与子节点个数相同。

由此，B+树与B树相比，有以下优势：

• 更少的IO次数：B+树的非叶节点只包含键，而不包含真实数据，因此每个节点存储的记录个数比B数多很多（即阶m更大），因此B+树的高度更低，访问时所需要的IO次数更少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。
• 更适于范围查询：在B树中进行范围查询时，首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；而B+树的范围查询，只需要对链表进行遍历即可。
• 更稳定的查询效率：B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)，而B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。

B+树也存在劣势：由于键会重复出现，因此会占用更多的空间。但是与带来的性能优势相比，空间劣势往往可以接受，因此B+树的在数据库中的使用比B树更加广泛。

六、感受B+树的威力

前面说到，B树/B+树与红黑树等二叉树相比，最大的优势在于树高更小。实际上，对于Innodb的B+索引来说，树的高度一般在2-4层。下面来进行一些具体的估算。

树的高度是由阶数决定的，阶数越大树越矮；而阶数的大小又取决于每个节点可以存储多少条记录。Innodb中每个节点使用一个页(page)，页的大小为16KB，其中元数据只占大约128字节左右(包括文件管理头信息、页面头信息等等)，大多数空间都用来存储数据。

• 对于非叶节点，记录只包含索引的键和指向下一层节点的指针。假设每个非叶节点页面存储1000条记录，则每条记录大约占用16字节；当索引是整型或较短的字符串时，这个假设是合理的。延伸一下，我们经常听到建议说索引列长度不应过大，原因就在这里：索引列太长，每个节点包含的记录数太少，会导致树太高，索引的效果会大打折扣，而且索引还会浪费更多的空间。

• 对于叶节点，记录包含了索引的键和值(值可能是行的主键、一行完整数据等，具体见前文)，数据量更大。这里假设每个叶节点页面存储100条记录(实际上，当索引为聚簇索引时，这个数字可能不足100；当索引为辅助索引时，这个数字可能远大于100；可以根据实际情况进行估算)。

对于一颗3层B+树，第一层(根节点)有1个页面，可以存储1000条记录；第二层有1000个页面，可以存储1000*1000条记录；第三层(叶节点)有1000*1000个页面，每个页面可以存储100条记录，因此可以存储1000*1000*100条记录，即1亿条。而对于二叉树，存储1亿条记录则需要26层左右。

七、总结

最后，总结一下各种树解决的问题以及面临的新问题：

1)、二叉查找树(BST)：解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表；

2)、平衡二叉树(AVL)：通过旋转解决了平衡的问题，但是旋转操作效率太低；

3)、红黑树：通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多；

4)、B树：通过将二叉树改为多路平衡查找树，解决了树过高的问题；

5)、B+树：在B树的基础上，将非叶节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查询更加高效。

推荐学习：MySQL教程

以上就是MySQL为什么选择B+树作为索引结构？（详解）的详细内容，更多请关注 第一PHP社区 其它相关文章！