MySQL底层数据结构选用B+树的原因

2024-04-02 19:04:59 328人浏览泡泡鱼

摘要

我们都知道Mysql底层数据结构是选用的B+树，那为什么不用红黑树，或者其他什么数据结构呢？红黑树是一种自平衡二叉查找树，Java8中的HashMap

我们都知道Mysql底层数据结构是选用的B+树，那为什么不用红黑树，或者其他什么数据结构呢？

红黑树是一种自平衡二叉查找树，Java8中的HashMap就用到红黑树来优化它的查询效率，可见，红黑树的查询效率还是比较高的，但是为什么mysql的底层不用红黑树而用B+数呢？

下图是红黑树依次插入1,2,3,4,5,6之后的情况：

然后再在上面的红黑树中插入7：

可以看到，尽管红黑树经过了自平衡，数据整体仍然偏向树的右侧，如果继续添加更多数据，添加的数据上百万、千万之后，树的层级将会非常高，查询时每多经过一层，就会多进行一次io，树的层级多了之后查找效率就会很慢。这个时候可能就会有人问了，那为什么不用平衡性更好的AVL树呢？

AVL树在一次插入1,2,3,4,5,6,7之后是这样的：

的确变顺眼了很多，树的层数也变少了，可AVL仍然没有解决根本问题，当数据量达到百万、千万之后，树的层数仍然会比较大，先不说AVL树维护平衡所需的代价，单论AVL树的层数就无法达到我们的要求。

那么什么样的数据结构可以让数据量达到百万，千万，甚至更大的体量时，层数仍然很小呢？很显然，想要减少层数，就必须要让每层储存的数据数更多，二叉树不管平衡性再好也只能做到每个节点有两个分叉，每层的数据量从数据结构被限制住了，那么，我们就不能从二叉树中选。所以这个时候B树的优势就体现出来了，B树每个节点可以存储多个元素，每个元素之间可以都可以拥有一个分叉，下图是B树每个节点最多可以存储3个元素的情况：

可以看到树的层级减小到两层，如果说每次每个节点最多可以存储的元素个数足够大，那么就算数据量达到上千万的量级，也可以将树的层级控制在一个可以接受的范围内。

但B树还有一个问题，下图展示的是B树层级达到三层时的情况：

如果现在我需要取出5-10号元素，当我通过层层查询，找到5号元素，然后发现其他元素不在这个节点，还需要通过局部中序遍历查询其他元素，找到7之后还需如此操作找到8,9,10，这又会增加io次数，所以也就有了B+树。

B+树是对B树的优化，主要是从两个地方进行优化的：

第一个优化是在每个叶子节点之间加上了一个双向指针，指向相邻节点，这样就解决了刚才的范围查询问题，范围查询如果跨了多个节点，就可以通过这个双向指针快速找到相邻节点，而不需要通过局部的中序遍历，从而减少了io次数。下图演示的是B+树：

但如果要找的元素不在叶子节点上呢？别担心，B+树的另一个优化就是的叶子节点包含了这颗树的所有元素！B+树的非叶子节点不再保存元素的data数据或者指针了，只是作为冗余的索引构成完整的B+树来方便查询。可以看到上图的15号元素不仅仅存在于非叶子节点中，也存在于叶子节点中。这样的设计虽然带来了很多冗余的索引，但是却让范围查询时不再需要向上查找非叶子节点了，而且每一层可以保存的索引数量变多了，让数据库每次io可以查询到更多的索引元素，毕竟在正常情况下，数据占的空间比索引占的空间要大很多。（需要注意的是，InnoDB和MyISAM引擎虽然都是用的B+树，但InnoDB的聚簇索引和数据是保存在一起的，而MyISAM是将聚簇索引和相应数据的指针保存在一起的，索引和数据是分开的。MyISAM引擎下的B+树也只有叶子节点才保存数据的指针）

由上面的分析我们可以知道，选用B+树作为Mysql的底层是为了减少io次数，那我们为什么不直接极端一点，使用hash来保存数据或者索引呢？其实MySQL确实支持hash类型的索引。