MySQL索引：BST、AVL、红黑树，B-树、B+树

二叉查找树(BST)

二叉查找树（Binary Search Tree），也称二叉搜索树、有序二叉树（ordered binary tree），排序二叉树（orted binary tree），是指一棵空树或者具有下列性质的二叉树：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；
没有键值相等的节点

二叉查找树在极端的情况下会退化成现线性的结构，降低查找效率
在这里插入图片描述

树的深度直接决定了最坏条件下的查找次数，也就是决定了查找的效率，因此降低树的深度很重要，所以引出了AVL树和红黑树

优点：有序
缺点：极端条件下会退化成链表，降低查找效率

平衡二叉树(AVL Tree)

AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）,平衡二叉树全称平衡二叉搜索树，也叫AVL树。是一种自平衡的树。

平衡二叉树也是一种特殊的二叉查找树，满足二叉查找树的特性

AVL树也规定了左结点小于根节点，右结点大于根节点。并且还规定了左子树和右子树的高度差不得超过1。这样保证了它不会成为线性的链表。
AVL树的查找稳定，查找、插入、删除的时间复杂度都为O（logN）
但是由于要维持自身的平衡，所以进行插入和删除结点操作的时候，需要对结点进行频繁的旋转。

AVL树每一个节点只能存放一个元素，并且每个节点只有两个子节点。当进行查找时，就需要多次磁盘IO，（数据是存放在磁盘中的，每次查询是将磁盘中的一页数据加入内存，树的每一层节点存放在一页中，不同层数据存放在不同页。）这样如果需要多层查询就需要多次磁盘IO。为了解决AVL树的这个问题，就出现了B树。

优点：有序，解决了BST会退化成线性结构的问题
缺点：进行插入和删除结点操作的时候，需要对结点进行频繁的旋转

红黑树（R-B Tree）

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

红黑树示意图如下：
红黑树

红黑树在查找方面和AVL树操作几乎相同。但是在插入和删除操作上，AVL树每次插入删除会进行大量的平衡度计算，红黑树是牺牲了严格的高度平衡的优越条件为代价，它只要求部分地达到平衡要求，结合变色，降低了对旋转的要求，从而提高了性能。红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。

相比于BST，因为红黑树可以能确保树的最长路径不大于两倍的最短路径的长度，所以可以看出它的查找效果是有最低保证的。在最坏的情况下也可以保证O(logN)的，这是要好于二叉查找树的。因为二叉查找树最坏情况可以让查找达到O(N)。

红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高，在插入和删除中AVL树所做的后期维护操作肯定会比红黑树要耗时好多，但是他们的查找效率都是O(logN)，所以红黑树应用还是高于AVL树的. 实际上插入 AVL 树和红黑树的速度取决于你所插入的数据.如果你的数据分布较好,则比较宜于采用 AVL树(例如随机产生系列数),但是如果你想处理比较杂乱的情况,则红黑树是比较快的。

红黑树广泛用于TreeMap、TreeSet，以及jdk1.8后的HashMap。

以上三种树都是基于二叉树

二叉树每一个节点只能存放一个元素，并且每个节点只有两个子节点。当进行查找时，就需要多次磁盘IO
在实际应用中，数据是存放在磁盘中的，每次查询是将磁盘中的一页数据加入内存，树的每一层节点存放在一页中，不同层数据存放在不同页。
这样如果需要多层查询就需要多次磁盘IO。为了解决这个问题，就出现了B树

B树（B-tree）

B树不是二叉树，B树每一层存放了更多的节点，由AVL树的“瘦高”变成了“矮胖”。
B树属于多叉树又名平衡多路查找树（查找路径不只两个）
B树的阶数指的就是
该树每个节点最多有 m个子树，m为该树的阶数，

一个m阶的B树规定了：

  1. 根结点至少有两个子女。
  2. 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m，即k介于 m/2和m之间。
  3. 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m。
  4. 所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

B-树

特点：

B树也是一种自平衡的树，在进行插入和删除操作时也需要对结点进行旋转等操作。
但是与AVL树和红黑树相比每个节点包含的关键字增多了，从而减小了树的深度，可以相对减少磁盘IO的次数。
特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度，因此B树被广泛用于文件系统及数据库中

弊端：
B树的查找不稳定，最好的情况就是在根节点查到了，最坏的情况就是在叶子结点查到。
B树在遍历方面比较麻烦，由于需要进行中序遍历，所以也会进行一定数量的磁盘IO。

除非完全重建数据库，否则无法改变键值的最大长度。这使得许多数据库系统将人名截断到70字符之内。

为了解决这些问题，出现了B+树。

应用场景：

  • Windows：HPFS 文件系统
  • Mac：HFS，HFS+ 文件系统
  • Linux：ResiserFS，XFS，Ext3FS，JFS 文件系统
  • MongoDB

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

B+树

一个m阶的B+树具有如下几个特征：

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

在这里插入图片描述

B+树的优点：

  1. B+树的层级更少：非叶子结点中存放的元素不存放数据，所以每一层可以容纳更多元素，比B-树更加“矮胖”，也就是磁盘中的每一页可以存放更多元素。这样在查找时，磁盘IO的次数也会减少
  2. B+树查询速度更稳定：每次查找都必须匹配到叶子节点，因此每一次查找都是稳定的。B-树由于中间节点也携带数据，因此只需要匹配到要查找的元素即可，最好的情况是在根节点就结束查找，最坏的情况是在叶子节点结束查找，查找性能不稳定
  3. B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在范围查询数据时候更方便，数据紧密性很高，缓存的命中率也会比B-树高。
  4. B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描

参考：
【1】知乎@小灰