为什么mysql索引要使用B+树,而不是B树,红黑树

服务器

浏览数:43

2020-6-28

我们在MySQL中的数据一般是放在磁盘中的,读取数据的时候肯定会有访问磁盘的操作,磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟,而磁盘移动则是在盘片旋转到指定位置以后,移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程,而定位是磁盘的存取中花费时间比较大的一块,毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候,显然定位是一个非常花费时间的过程,但是我们可以通过B树进行优化,提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢?我们可以根据B类树的特点,构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数(树的高度)尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

特别地:只有B-树和B+树,这里的B-树是叫B树,不是B减树。没有B减树的。

以下摘自【程序员小灰】

什么是B树

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

1、根结点至少有两个子女。 2、每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m 3、每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m 4、所有的叶子结点都位于同一层。5、每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

下面以3阶B树开始学习

这棵树中,重点看(2,6)节点。该节点有两个元素2和6,又有三个孩子1,(3,5),8。其中1小于元素2,(3,5)在(2,6)之间,8大于(3,5),正好符合上面所列的特征。

B树查询的流程:

比如上面的3阶B树查询数值5。

第1次IO:

第2次IO:

第3次IO:

第3次内存比较:

总结:每次深度加1就会进行一次磁盘IO的查询,将当前高度的数据加到内存中,再进行数值比较。从中可以看出相比大部分的查询时间是花费在磁盘IO的速度上,所以要想提高性能就是将树的高度足够低,IO次数足够少,这就是B树的优势。

B树添加的流程:

比如树里添加数值4 自顶向下查找4的节点位置,发现4应当插入到节点元素3,5之间

节点3,5已经是两元素节点,无法再增加。父亲节点 2, 6 也是两元素节点,也无法再增加。根节点9是单元素节点,可以升级为两元素节点。于是拆分节点3,5与节点2,6,让根节点9升级为两元素节点4,9。节点6独立为根节点的第二个孩子。

从图中可以看到,为了插入一个元素,几乎全部的位置都变化了,这就是B树的自平衡(始终维持多路平衡)

B树删除的流程:

自顶向下查找元素11的节点位置。

删除11后,节点12只有一个孩子,不符合B树规范。因此找出12,13,15三个节点的中位数13,取代节点12,而节点12自身下移成为第一个孩子。(这个过程称为左旋)

B树应用

主要用于文件系统以及部分数据库索引(MongoDB) 而Mysql是用B+树的。

什么是B+树

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

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

从上图可以发现每一个父节点的元素都出现在子节点中,并且是子节点的最大(或最小)

从图中可以看到根节点元素8是字节点2,5,8的最大元素,也是叶子节点6,8的最大元素。根节点15是子节点11,15的最大元素,也是叶子节点13,15的最大元素。

B+树的最大元素始终位于根节点当中。所有叶子节点包含了全量元素信息,并且每一个叶子节点都带有指向 下一个节点指针,形成了一个有序链表。

B+树查询流程

单个查询:查询某个元素3

第一次磁盘IO:

第二次磁盘IO:

第三次磁盘IO:

这样看起来跟B树没有什么区别。但其实有两点是需要注意的:

1、B+树的中间节点没有卫星数据的。所以同样大小的磁盘页可以容纳更多的节点元素。(这就意味着B+会更加矮胖,查询的IO次数会更少)

B树的卫星数据

B+树的卫星数据

2、B树查找性能是不稳定的(如果要查找的数据分别在根节点和叶子节点,他们的性能就会不同)。但B+树的每一次都是稳定的,为啥呢,看下面的范围查询。

范围查询:查找到范围的下限(3)

B树的范围查询:

自顶向下,查找到范围的下限(3),最多6条:

中序遍历到元素6:

中序遍历到元素8:

中序遍历到元素9:

中序遍历到元素11,遍历结束:

B+树的范围查询:

自顶向下,查找到范围的下限(3),最多6条:

通过链表指针,遍历到元素6, 8:

通过链表指针,遍历到元素9, 11,遍历结束:

从上面的流程比较,可以得出以下B+树的优势:

1.单一节点存储更多的元素,使得查询的IO次数更少。

2.所有查询都要查找到叶子节点,查询性能稳定。

3.所有叶子节点形成有序链表,便于范围查询。

面试题

问题1:MySQL中存储索引用到的数据结构是B+树,B+树的查询时间跟树的高度有关,是log(n),如果用hash存储,那么查询时间是O(1)。既然hash比B+树更快,为什么mysql用B+树来存储索引呢?

答:一、从内存角度上说,数据库中的索引一般时在磁盘上,数据量大的情况可能无法一次性装入内存,B+树的设计可以允许数据分批加载。

二、从业务场景上说,如果只选择一个数据那确实是hash更快,但是数据库中经常会选中多条这时候由于B+树索引有序,并且又有链表相连,它的查询效率比hash就快很多了。

问题2:为什么不用红黑树或者二叉排序树?

答:树的查询时间跟树的高度有关,B+树是一棵多路搜索树可以降低树的高度,提高查找效率

问题3:既然增加树的路数可以降低树的高度,那么无限增加树的路数是不是可以有最优的查找效率?

答:这样会形成一个有序数组,文件系统和数据库的索引都是存在硬盘上的,并且如果数据量大的话,不一定能一次性加载到内存中。有序数组没法一次性加载进内存,这时候B+树的多路存储威力就出来了,可以每次加载B+树的一个结点,然后一步步往下找,

问题4:在内存中,红黑树比B树更优,但是涉及到磁盘操作B树就更优了,那么你能讲讲B+树吗?

B+树是在B树的基础上进行改造,它的数据都在叶子结点,同时叶子结点之间还加了指针形成链表。

下面是一个4路B+树,它的数据都在叶子结点,并且有链表相连。

问题5:为什么B+树要这样设计?

答:这个跟它的使用场景有关,B+树在数据库的索引中用得比较多,数据库中select数据,不一定只选一条,很多时候会选中多条,比如按照id进行排序后选100条。如果是多条的话,B+树需要做局部的中序遍历,可能要跨层访问。而B+树由于所有数据都在叶子结点不用跨层,同时由于有链表结构,只需要找到首尾,通过链表就能把所有数据取出来了。

比如选出7到19只需要在叶子结点中就能找到。

作者:logan