MySQL索引结构B树、B+树的原理及区别整理

2021/9/6 2:07:14

本文主要是介绍MySQL索引结构B树、B+树的原理及区别整理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

索引是一种数据存储结构,对表中一列或多列进行排序以快速定位获取数据。就像一本书的目录就是一个索引,如果想在一本书中找到某个主题,一般会先找到对应页码。在mysql中,存储引擎用类似的方法使用索引,先在索引中找到对应值,然后根据匹配的索引记录找到对应的行。

B树

大多数存储引擎都支持B树索引。B树通常意味着所有的值都是按顺序存储的,并且每一个叶子到根的距离相同。B树索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取数据。下图就是一颗简单的B数。

B树的查询流程:

如上图我要从找到E字母,查找流程如下:

  1)获取根节点的关键字进行比较,当前根节点关键字为M,E<M(26个字母顺序),所以往找到指向左边的子节点(二分法规则,左小右大,左边放小于当前节点值的子节点、右边放大于当前节点值的子节点)。

  2)拿到关键字D和G,D<E<G 所以直接找到D和G中间的节点。

  3)拿到E和F,因为E=E 所以直接返回关键字和指针信息(如果树结构里面没有包含所要查找的节点则返回null)。

  4)通过指针信息取出这条记录的所有信息。

B+树

下图为B+树的结构,B+树是B树的升级版,我们可以观察一下,B树和B+树的区别是什么?
在这里插入图片描述

B+树和B树的区别是:

  1)B树的节点(根节点/父节点/中间节点/叶子节点)中没有重复元素,B+树有。

  2)B树的中间节点会存储数据指针信息,而B+树只有叶子节点才存储。

  3)B+树的每个叶子节点有一个指针指向下一个节点,把所有的叶子节点串在了一起。

从下图我们可以直观的看到B树和B+树的区别:紫红色的箭头是指向被索引的数据的指针,大红色的箭头即指向下一个叶子节点的指针。
在这里插入图片描述
假设被索引的列是主键,现在查找主键为5的记录,模拟一下查找的过程:

  B树,在倒数第二层的节点中找到5后,可以立刻拿到指针获取行数据,查找停止。

  B+树,在倒数第二层的节点中找到5后,由于中间节点不存有指针信息,则继续往下查找,在叶子节点中找到5,拿到指针获取行数据,查找停止。

  B+树每个父节点的元素都会出现在子节点中,是子节点的最大(或最小)元素。叶子节点存储了被索引列的所有的数据。

那B+树比起B树的优点:

  1)由于中间节点不存指针,同样大小的磁盘页可以容纳更多的节点元素,树的高度就小。(数据量相同的情况下,B+树比B树更加“矮胖”),查找起来就更快。

  2)B+树每次查找都必须到叶子节点才能获取数据,而B树不一定,B树可以在非叶子节点上获取数据。因此B+树查找的时间更稳定。

  3)B+树的每一个叶子节点都有指向下一个叶子节点的指针,方便范围查询和全表查询:只需要从第一个叶子节点开始顺着指针一直扫描下去即可,而B树则要对树做中序遍历。

参考:https://blog.csdn.net/qq_36261130/article/details/100556264



这篇关于MySQL索引结构B树、B+树的原理及区别整理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程