• 欢迎访问 winrains 的个人网站!
  • 本网站主要从互联网整理和收集了与Java、网络安全、Linux等技术相关的文章,供学习和研究使用。如有侵权,请留言告知,谢谢!

索引数据结构之B-Tree与B+Tree(下篇)

数据库 winrains 来源:天堂同志 5个月前 (04-23) 37次浏览

前言

接上篇博客《索引数据结构之 B-Tree 与 B+Tree(上篇)》,本文将简单介绍 B+Tree 中插入、查找、删除等相关操作,以及对比 B-Tree 与 B+Tree 的区别,最后会重点分析为什么 MySQL 会选择 B+Tree 作为索引的数据结构,而不是 B-Tree。

B+Tree

B+Tree 的大分部性质与 B-Tree 的性质一样,例如:对于一个 m 阶的 B+Tree 而言,根结点的关键字数量为 1 <= k <= m-1,非根结点的关键字数量为 m/2 <= k <= m-1;每一个结点上,所有的关键字都是有序排列的;每个结点最多 m 个子结点。 但 B+Tree 有几个十分重要的性质与 B-Tree 不一样。

  1. B+Tree 的所有非叶子结点不存储数据,只存储关键字,即只存储 key,不存储 value;而 B-Tree 的所有结点,不论是叶子结点还是非叶子结点,都存放的是关键字和数据,即存放了 key 和 value;
  2. B+Tree 的叶子结点才存储关键字和数据,即存放了 key 和 value;
  3. 因为 B+Tree 的非叶子结点只存放关键字,叶子结点才存放数据,因此非叶子结点中关键字对应的数据只能在叶子结点存储,所以在叶子结点中会都会冗余一份非叶子结点的关键字;
  4. 因为叶子结点会冗余非叶子结点的关键字,因此 B+Tree 中,每个关键字的右子树的值都是大于等于该关键字,左子树所有的值小于该关键字。
  5. 叶子结点中存有一个指针指向兄弟结点,这一点对于 MySQL 中数据的查找是非常方便的。

插入

B+Tree 的插入操作与 B-Tree 的插入操作类似,也存在结点的分裂情况,不同的是,非叶子结点的关键字会在叶子结点中冗余一份。下面以一颗 5 阶的 B+Tree 为例,看看数据的插入流程。 一次向 B+Tree 中插入数据:50、30、40、25,前面的步骤与 B-Tree 完全一样。

图1

当继续向其中插入数据 20 时,此时结点的关键字数量达到 5,超过了 m-1,因此需要将结点从中间分裂,所以从最中间的关键字 30 这儿分裂,将 30 提取到父结点当中,30 左边的所有关键字组成一个新的结点——左孩子,30 右边的所有关键字组成一个新的结点——右孩子,由于 B+Tree 中非叶子结点中的关键字会冗余一份在叶子结点中,所以 30 这个关键字以及这个关键字所对应的数据 value 也会存放进右孩子当中。如下图所示。

图2

查找

B+Tree 中根据关键字查找数据的流程与 B-Tree 也几乎一样,不同的是,B+Tree 的所有数据都存放在叶子结点,因此 B+Tree 最后需要一直查找到叶子结点这一层,查到关键字对应的数据后才返回,而 B-Tree 中非叶子结点也可以存放数据,因此 B-Tree 中查找数据时,可能遍历到非叶子结点时就找到了数据,就可以提前结束寻找过程。 如图所示,从图中的数据中查找关键字 22 的数据。

图3

首先从根结点开始出发,要查找的关键字 22 大于根结点中的第一个关键字 19,因此进入 19 的右子树继续查找,即进入到关键字 22 和 30 所在的这个结点。由于要查找的数据 22 等于当前节点的第一个关键字(此时由于当前节点不是叶子结点,所以不能停止查找),因此继续进入到关键字 22 的右子树查找,即进入到关键字 22、25、26 所在的结点,由于当前结点是叶子结点,并在结点中找到了关键字 22,因此将数据返回。如上图中,红色线条即表示的是本次查找的路径。

删除

由于 B+Tree 的所有数据都存在叶子结点,所以如果要删除的数据存在于 B+Tree 中,那么最终一定是在叶子结点中删除数据,同时如果关键字还存在与非叶子结点中,那么就还需要修改非叶子结点中的指针。在删除过程中也涉及到找兄弟结点借关键字以及合并结点的情况,操作与 B-Tree 类似。 下面以下图中的数据为例。

图4

从 B+Tree 中删除 19。找到 19 所处的叶子结点,然后将 19 删除,然后叶子结点中只剩下关键字 20 了。由于 19 这个关键字还处于非叶子结点中,因此将 19 从非叶子结点中删除,然后用关键字 20 替换。如图。

图5

由于叶子结点中只剩下 20 这一个关键字了,小于 m-1,因此需要向兄弟结点借元素,右边的兄弟结点的元素个数大于 m/2,因此可以将 22 借出,然后修改父节点的指针。所以最终状态如下。

图6

至于删除的其他复杂情形,可以参照上篇文章索引数据结构之 B-Tree 与 B+Tree(上篇)中 B-Tree 的删除示例或者在可视化网站进行动态演示(https://www.cs.usfca.edu/~galles/visualization/Algorithms.html),会更加直观。

MySQL 中索引数据结构

前面关于 B-Tree 和 B+Tree 的知识,介绍了那么多,那么它们究竟有什么用呢?关于 MySQL 中索引的数据结构,网上有很多说法,有的地方说是 B-Tree,有的地方说成 B+Tree,那么究竟是哪一种数据结构呢?答案是 B+Tree。为什么不是 B-Tree 呢?

简单点的答案就是,B-Tree 的非叶子结点会存放数据,而 B+Tree 的非叶子结点不存放数据,只存放关键字,这样同一个结点,B+Tree 的结点能形成的叉数越多,那么存储一定数量的数据,B+Tree 的高度越小,那么插入、查找、删除的性能会越高。(B-Tree 和 B+Tree 的插入、查找、删除的时间复杂度与树的高度成正相关)。

MySQL 中 Innodb 存储引擎存储数据的最小单元是页,一页的大小默认是 16KB,可以通过如下命令查看具体的值,这个值可以被修改。

show variables like 'innodb_page_size';

而对于索引树结构中,一个结点的大小通常是一个数据页的整数倍,即 16KB 的倍数,而一个结点的大小通常也是 16KB。

现在我们假设一个关键字(key)的大小为 2KB,它对应的数据(value)是 2KB,所以一对 key-value 的大小就是 4KB,且假设树的高度都为 3。

对于 B-Tree 而言,所有结点中存的都是 key-value,所以 B-Tree 的第一层,也就是根结点层,最多能存放 16KB/4KB=4 对 key-value,也就是最多分出 5 个叉(5 颗子树)。

因此第二层最多有 5 个结点,每个结点依旧是最多能存储 16KB/4KB=4 对 key-value,每个结点也是分出 5 个叉,所以第二层最多能存储 20 对 key-value。

那么第三层就会有 25 个结点,每个结点最多能存放 16KB/4KB=4 对 key-value,所以第三层最多能存储 25*4 = 100 对 key-value。

因此该 B-Tree 的三层一共能存放 4+20+100 = 124 对 key-value。

再来看下 B+Tree,第一层和第二层都是非叶子结点,只存放 key,第三层是叶子结点,存放 key-value。

第一层最多能存放 16KB/2KB =8 对 key-value,最多能分出 9 个叉;

因为第一层最多能分出 9 个叉,所以第二层最多可以有 9 个结点,每个结点也是最多能存放 16KB/2KB =8 对 key-value,,每个结点能分出 9 个叉,因此第二层最多能存储 72 对 key-value,分出 81 个叉;

因为第二层最多能分出 9 乘以 9 个叉,所以第三层最多有 81 个结点,由于第三层是叶子结点,存放 key 和 value,因此每个结点能存放 16KB/4KB=4 对 key-value。所以第三层一共最多能存放 81*4=324 对 key-value。

B+Tree 的所有数据都存放在叶子结点,即第三层,因此该 B+Tree 一共能存放 324 对 key-value。(远远大于B-Tree的124对key-value)

对比发现,同样高度的树,B+Tree 能存放的数据远远多于 B-Tree(这里举例时,假设的 key 的大小为 2KB,实际的 key 远远比这个小,如果 key 越小,这个差距会越来越大)。前面我们假设的是树的高度不变,那反过来假设我们要存储的数据量是一定的,比如 5GB 的数据,那么最终 B-Tree 的树高肯定是远远高于 B+Tree。

树的高度越高,会有什么影响呢?熟悉树这种数据结构的同学肯定知道,通常树的插入、查找、删除的时间复杂度与树的高度成正相关,树越高,时间复杂度越高,性能越差,这个时间复杂度是理论推导出来的,接下来我们通过 MySQL 的数据读取为例,来解释一下为什么数越高,性能越差。

假设 MySQL 的某张表的大小为 5GB,对于主键索引来说,如果用 B-Tree 来存储,那么它最终的高度可能是 20(这个 20 是假设的一个值),而如果使用 B+Tree 来存储,它最终的高度可能是 4(这个 4 也是假设的一个值)。(这里的高度 4 和 20 都是我们假设的一个值,不是精确值,但反应的是 B+Tree 和 B-Tree 在相同数据量时最终树高相差较大的现象。)

MySQL 中存储数据是以页为单位的,在读数据时,也是以页为单位将数据从磁盘加载进内存当中,每从磁盘中读取一个页,就会发生一次磁盘 IO。也就是说,在查找数据时,每遍历一个结点,就意味着读取一个数据页,也就是发生一次 IO。

对于 B-Tree 而言,如果要查找的数据在树的越底层,就意味着要发生的 IO 次数越多,树越高,查找时可能发生的磁盘 IO 次数越多,磁盘 IO 越多,意味着程序的耗时会越长,性能越差。

而对于 B+Tree 而言,它的树高相对 B-Tree 而言会低很多,而且所有的数据都是存放在叶子结点当中的,所以查询数据时,一定是遍历到叶子结点层,时间复杂度相对稳定,而且发生的磁盘 IO 次数较少,所以整体来讲,B+Tree 性能更优,因此 MySQL 的索引数据结构选择的是 B+Tree,而不是 B-Tree。

通常一颗 B+Tree 的高度为 3 或者 4,这样一次索引的查找通常最多只需要发生 3-4 次磁盘 IO,而 MySQL 中由于 buffer pool 缓冲池的机制,第一层的结点所对应的数据页通常存在于缓存中,第二层的数据页也有很大可能也存于缓存中(MySQL 的预读机制、LRU 缓存淘汰机制等都有可能导致),因此在遍历时,B+Tree 的第一层、第二层极有可能不会发生磁盘 IO,而是基于内存查找,所以一次数据查找,可能就只会发生 1-2 次磁盘 IO,这个查询效率得到了大大提高。

另外,B+Tree 的叶子结点中,存放了相邻叶子结点的指针,因此在进行范围查找时,不需要多次遍历整棵树,只需要找到一个叶子结点后,通过指针,就能找到其他的叶子结点,这是十分高效的一种做法。

总结

本文前半部分主要介绍了 B+Tree 的性质以及通过对比 B-Tree 的插入、查找、删除操作的流程,简单介绍了 B+Tree 的插入、查找、删除操作的流程。最后从 B+Tree 和 B-Tree 数据结构的不同之处出发,详细说明了为什么 MySQL 中索引的数据结构是 B+Tree,而不是 B-Tree。

我们知道了 MySQL 的索引结构为什么没有选择 B-Tree,而是选择了 B+Tree,而那么多高效的数据结构,例如:数组、哈希表、红黑树等,为什么 MySQL 没有选择它们呢?下一篇博客分析。

作者:天堂同志

来源:https://juejin.im/post/5e909f34518825739b2d386a


版权声明:文末如注明作者和来源,则表示本文系转载,版权为原作者所有 | 本文如有侵权,请及时联系,承诺在收到消息后第一时间删除 | 如转载本文,请注明原文链接。
喜欢 (1)