一分钟学会MySQL的索引结构及二叉树

哈希表(Hash)
哈希表查询数据的时间复杂度为O(1)，是一种高效的数据结构。面试中常问的HashMap就是基于哈希表的思想，对HashMap不太深入的同学，可以参考我的另外一篇文章HashMap夺命连环问

例如将索引列作为key，对应行的物理地址作为value，非常适用于处理等值查询。

select * from user where id=1;
但哈希表显而易见的缺点就是，哈希表不适用于范围查找。

例如执行以下语句时，哈希表就无能为力了。

select * from user where id>1;
 

二叉搜索树(Binary Search Tree)
经常刷LeetCode的同学，肯定是知道二叉搜索树的中序遍历是一个递增序列。

一颗二叉搜索树，每个节点最多只有2个子节点，左子节点的值小于父节点，右子节点的值大于父节点。

在java培训中二叉搜索树中进行查询，可以利用到二分查找，因此查询的时间复杂度为O(logN)。

例如查找元素23时，先从根节点开始，因为23>20，路由到右子节点32上。因为23<32，路由到其左子节点23上，发现相等，查询结束。

仅需比较3次，就可以查询到想要的数据。

另外，二叉搜索树的插入与删除操作的时间复杂度也为O(logN)，有兴趣的同学可以做做LeetCode上的这道题701. 二叉搜索树中的插入操作

我们大可以将索引列作为节点的值，同样每个节点还有个用于保存相应行物理地址的变量。

二叉搜索树支持范围查找，例如对以下的sql语句

select * from user where id>12 and id<32;
首先利用二分查找到节点12，再对此节点进行中序遍历，在遍历到节点32时停止即可。

二叉搜索树在搜索、插入与删除保持较优的时间复杂度，而且又支持范围查找。那MySQL为啥没有使用它呢？

是因为二叉搜索树在插入、删除的过程中并不会保持自身的平衡！

例如我新增了3条用户数据，初始的树是这样的（节点的值为主键）：

当我再次增加3条数据后，节点被依次加在右子树上，最终形成链表的结构。

此时，二叉搜索树退化成了链表，时间复杂度由O(logN)提升到了O(N)，查询性能大大降低。

因此，我们迫切需要一种能够在变动中保持自平衡的二叉树。

平衡二叉搜索树

AVL树
AVL树就是一种自平衡的二叉搜索树，对于它的任意一个节点，其左子树高度与右子树高度差最大为1，因此就不存在二叉树退化为链表的极端情况。

下图就是一个AVL树：

在往AVL树中插入节点时，需要通过左旋右旋操作来保证树的平衡性。

AVL树在查找、插入与删除操作的时间复杂度都为O(logN)。

AVL树追求极致的平衡性，因此就会进行多次的旋转。在插入与删除次数比较多时，达成平衡的代价甚至比使用它的收益还要大。

那有没有一种能够稍微降低点平衡性，却能带来较大的整体性能上提升的平衡二叉搜索树呢？

红黑树

红黑树也是一种平衡二叉搜索树，相比于AVL树。红黑树似乎对平衡性的追求没有那么执着，红黑树只要求最长路径不能超出最短路径的两倍。

在红黑树中，节点要么是红色，要么是黑色。根节点与叶子节点（NIL）都是黑色的，任意一个路径不能连续出现2个红色节点。从根节点出发的所有路径，黑色节点（不包含NIL）的数量都是相同的。

红黑树通过左旋、右旋与变色三种操作来保证一定的平衡性，相比于AVL树，红黑树的查询效率较低，但是删除与插入的效率大大提高，总体性能优于AVL树。

而且在实际的应用中，红黑树的应用更加广泛。例如HashMap在链表长度大于8时则转化为红黑树，TreeMap使用红黑树来对键值进行排序，IO多路复用中epoll使用红黑树来对Socket进行管理。

那MySQL为啥没有使用红黑树来组织索引数据呢？

如果索引数据能够一次性加载到内存中，那么使用红黑树是没有问题的。

问题就在于，索引数据无法一次性加载到内存中，因此索引数据需要分批加载。

假设要查询的数据位于叶子节点上，树高为n。第一次先把根节点加载到内存中，进行一次磁盘IO。当一直查询到叶子节点时，就需要进行n次IO。

当单表数据达到100万时，树的高度约为log1000000(以2为底)=20。一次磁盘IO平均耗时10ms，20次就是0.2秒。如果再考虑到范围查询、不走索引的查询与多表联查，速度慢得令人发指。

因此，我们现在的首要目标，就是降低IO次数，也就是降低树的高度。

B树
B树又称为B-树，注意不是B减树啊，“-”是一个连字符！！！

B树是一种多叉平衡搜索树，在节点总数相同的情况下，B树的高度明显低于二叉树。

B树有以下几个重要的特性：

每个节点可能存储多个元素，节点内元素是有序的，每一个元素也会对应一份数据行（当然也有可能是主键索引项，或者数据行的地址）。
父节点中的元素不会出现在子节点当中
叶子节点都在同一层，且之间没有通过指针相连
一颗具有3个分叉的B树为：

可以看到，B树的高度被压缩得很厉害。

另外一个方面，B树充分利用到了程序访问的局部性原理。也就是说，当程序访问磁盘或内存中的一份数据时，其周围的数据将会有很大概率在接下来被使用到。

因此，B数每个节点不会只存一个元素，而是存储多份。我们查询数据时，每进行一次IO，就会将B树的一个节点读进缓存中。这样在接下访问其周围的数据时，无需从磁盘读取，直接从缓存读取，缓存命中率大大提升。

也许会有人问？如果一个节点内存放大量元素，那么从磁盘读取的速度是否和个数相关，呈线性增长呢？

答案是不会的。第一次读取一个节点时，进行的是随机读，需要先进行磁盘寻道，是非常耗时的。之后读取其他的元素，是进行的顺序读。之所以进行顺序读，是因为一个节点内的元素被顺序存储在磁盘上的。顺序读是非常快速的，其效率可能千倍于随机读。

那么，在B树上读取索引项为21的流程是怎样的呢？

在节点内部，使用的是二分查找，用于找到下层指针。

看来B树能有效解决平衡二叉树io次数过多的问题，似乎已经能满足所有的要求了。

但是MySQL最终采用的B+树，而不是B树。

相对来说，B树还有以下的不足：

每个节点不仅存索引项，又存具体的数据，那么每个节点可存放的索引项就比较少。索引项少，io次数就会变多。
B树不能做到快速的范围查找，需要进行多次的查找，类似于中序遍历。
为了改进B树，后来提出了B+树。

B+树
这个时候你又可以读作B加树了...

B+树有以下的特性：

非叶子节点只存放索引项，叶子节点既存放索引项，也存放具体的数据。
叶子节点会存放当前所有的索引项，就是说，可以与父节点的索引项重复。
叶子节点通过指针相连，形成有序的双向链表结构。
一颗成熟的B+树，应该是有如下的作风：

由于B+树叶子节点才存放数据行，因此每次的查询，都需要加载到叶子节点。而B树每个节点都存放数据行，每次的查询不一定非要到叶子节点。

所以这个时候会有人发出这样的疑问：B+树每次查询必须要深入到叶子节点，那么它的平均查询效率不是应该低于B树的吗？

如果在树高相同的情况下，确实是的。可实际情况是，在索引项相同的情况下，B+树的高度明显低于B树的，因为B+树的非叶子节点可以比B树存放更多的元素，毕竟少了数据行嘛。所以考虑到io成本加上范围查询，B+树的整体查询效率是优于B树的，但B+树对单个数据的查询效率是低于B树的。

B+树在范围查询上，是怎么表现出不错的性能的呢？

首先查找到范围下限，直接使用叶子节点的指针来加载下一个数据块，避免通过父节点来中转。在遍历到范围上限后，直接返回遍历到的所有数据即可。

B+树通过在叶子节点重复存储元素，其整体占用的空间其实是略高于B树的。但这点浪费的空间却能够换来巨大的性能提升，也是蛮不错的。

鉴于B+树用于以上的优点，MySQL最终采用了B+树作为索引的组织方式。

各种数据结构的对比
在这里直接以最简单明了的方式突出各个数据结构的优缺点：

链接：https://juejin.cn/post/7033235164364963877