MySQL为何选中B+树作为索引构造？（详解）

一、二叉查寻树(BST)：不服衡

二叉查寻树(BST，Binary Search Tree)，也叫二叉排序树，在二叉树的根基上需要知足：任意节点的左子树上所有节点值不大于根节点的值，任意节点的右子树上所有节点值不小于根节点的值。如下是一颗BST(图片来源)。

当需要快速查寻时，将数据储备在BST是一种常见的选中，由于此时查询时间取决于树高，均匀时间复杂度是O(lgn)。然而，BST大概长歪而变得不服衡，如下图所示(图片来源)，此时BST退化为链表，时间复杂度退化为O(n)。

为理解决这个问题，引入了均衡二叉树。

二、均衡二叉树(AVL)：扭转耗时

AVL树是严厉的均衡二叉树，所有节点的摆布子树高度差不克不及超越1；AVL树查寻、插入和删除在均匀和最坏状况下都是O(lgn)。

AVL实现均衡的关键在于扭转操纵：插入和删除大概毁坏二叉树的均衡，此时需要通过一次或屡次树扭转来从新均衡这个树。当插入数据时，最多只需要1次扭转(单扭转或双扭转)；但是当删除数据时，会致使树失衡，AVL需要保护从被删除节点到根节点这条途径上所有节点的均衡，扭转的量级为O(lgn)。

由于扭转的耗时，AVL树在删除数据时效力很低；在删除操纵较多时，保护均衡所需的代价大概高于其带来的好处，因此AVL实际使用并不广泛。

三、红黑树：树太高

与AVL树比拟，红黑树并不追求严厉的均衡，而是大致的均衡：只是确保从根到叶子的最长的大概途径不多于最短的大概途径的两倍长。从实现来看，红黑树最大的特点是每个节点都属于两种色彩(红色或黑色)之一，且节点色彩的划分需要知足特定的规则(详细规则略)。红黑树示例如下（图片来源）：

与AVL树比拟，红黑树的查询效力会有所下落，这是由于树的均衡性变差，高度更高。但红黑树的删除效力大大提高了，由于红黑树同时引入了色彩，当插入或删除数据时，只需要停止O(1)次数的扭转乃至变色就能包管根本的均衡，不需要像AVL树停止O(lgn)次数的扭转。总的来说，红黑树的统计机能高于AVL。

因此，在实际利用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树储备排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。

关于数据在内存中的状况（如上述的TreeMap和HashMap），红黑树的展现是非常优良的。但是关于数据在磁盘等辅助储备设备中的状况（如MySQL等数据库），红黑树并不擅长，由于红黑树长得还是太高了。当数据在磁盘中时，磁盘IO会成为最大的机能瓶颈，设计的目标应当是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会严峻影响机能。

四、B树：为磁盘而生

B树也称B-树(其中-不是减号)，是为磁盘等辅存设备设计的多路均衡查寻树，与二叉树比拟，B树的每个非叶节点可以有多个子树。因此，当总节点数目雷同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。

定义B树最重要的概念是阶数(Order)，关于一颗m阶B树，需要知足以下前提：

• 每个节点最多包括 m 个子节点。
• 假如根节点包括子节点，则至少包括 2 个子节点；除根节点外，每个非叶节点至少包括 m/2 个子节点。
• 具有 k 个子节点的非叶节点将包括 k - 1 笔记录。
• 所有叶节点都在统一层中。

可以看出，B树的定义，主如果对非叶结点的子节点数目和记载数目的限制。

下图是一个3阶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+树作为索引构造？（详解）的具体内容，更多请关注百分百源码网其它相关文章！