为什么Mysql底层采用B+树做索引？

问题

  在MySQL中，无论是Innodb还是MyIsam，都使用了B+树作索引结构。MySQL为什么选择B+树作为索引结构，而不是二叉树、红黑树什么的呢？

一、二叉查找树(BST)：不平衡

  二叉查找树(BST，Binary Search Tree)，也叫二叉排序树：任意节点的左子树上所有节点值不大于根节点的值，任意节点的右子树上所有节点值不小于根节点的值。

  当需要快速查找时，将数据存储在BST是一种常见的选择，因为此时查询时间取决于树高，平均时间复杂度是O(log n)。然而，BST可能长歪而变得不平衡，如下图所示，此时BST退化为链表，时间复杂度退化为O(n)。

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

二、平衡二叉树(AVL)：旋转耗时

  AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(logn)。

  AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(log n)。

  由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

三、红黑树：树太高

  与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

红黑树特性：

1. 根节点始终是黑色的。
2. 所有叶子都是黑色。
3. 每个红色结点的两个子结点都是黑色。
4. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
   
     与AVL树相比，RB-Tree的查询效率会有所下降，这是因为树的平衡性变差，高度更高。但RB-Tree的删除效率大大提高了，当插入或删除数据时，RB-Tree最多只需要旋转3次实现复衡，只需O(1)，不需要像AVL树进行O(log n)次数的旋转。总的来说，红黑树的统计性能高于AVL。

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

四、B树：为磁盘而生

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

一棵m阶的B树特性如下（其中 ceil(x)是一个取上限的函数）：

1. 树中每个结点至多有 m 个孩子；
2. 除根结点和叶子结点外，其它每个结点至少有有 ceil(m / 2)个孩子；
3. 若根结点不是叶子结点，则至少有 2 个孩子（特殊情况：没有孩子的根结点，即根结点为叶子
   结点，整棵树只有一个根节点）；
4. 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询
   失败的结点，实际上这些结点不存在，指向这些结点的指针都为 null)；
5. 包含n个关键字，n+1个指针的结点的一般形式为： （n,P0,K1,P1,K2,P2,…,Kn,Pn）。其
   中：
   （a) Ki为关键字，K1<K2<…<Kn。
   （b) Pi 是指向包括Ki到Ki+1之间的关键字的子树的指针。
   （c) 关键字的个数 n 必须满足： ceil(m / 2)-1 ≤ n ≤ m-1。

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

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

五、B+树

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

1. B树中每个节点（包括叶节点和非叶节点）都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。在MySQL中，这里所说的真实数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。
2. 有 n 棵子树的结点中含有 n 个关键字； (B-tree 是 n 棵子树有 n-1 个关键字)
3. 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本
   身依关键字的大小自小而大的顺序链接。 (B-tree 的叶子节点并没有包括全部需要查找的信息)
4. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。
   (B-tree 的非终节点也包含需要查找的有效信息)

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

• 更少的IO次数：B+树真正的数据都存在叶子结点嘛，也就是上面的结点就简单的索引，就内存会更小，意味着同样的一个页内存大小，所以B+树中，同样的磁盘页大小可以装更多个“索引”，也就是在同样的数据量的情况下，B+树会比B树更加矮胖，因此查询时IO的次数也更加少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。
• 更适于范围查询：在B树中进行范围查询时，首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；而B+树的范围查询，只需要对链表进行遍历即可。
• 更稳定的查询效率：B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)，而B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。

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

六、总结

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

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

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

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

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

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

参考文献：https://www.cnblogs.com/kismetv/p/11582214.html