专栏首页SEian.G学习记录MySQL索引为什么使用B+树?

MySQL索引为什么使用B+树?

在数据库面试过程中,经常会被问到一个问题:MySQL索引为什么使用B+树?

面对这个问题,我相信80%的人都不清楚(包括我自己),那么本文就围绕这个问题展开介绍,在了解索引之前,我们先了解一下B+树,什么是B+树?在了解B+树之前,先了解一下什么是B树?介绍B树和B+树的插入、删除操作。

写这篇文章主要是由于自身对B+树某些细节也感到很迷惑,通过学习,对B+树的操作有所顿悟,写下这篇文章以做记录。由于是自身对B+树的理解,肯定有考虑不周的情况,或者理解错误的地方,请留言指出。

一、B树

B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数,阶数表示了一个结点最多有多少个孩子结点,一般用字母m表示阶数。当m取2时,就是我们常见的二叉搜索树。

一颗m阶的B树定义如下:

1)每个结点最多有m-1个关键字。 2)根结点最少可以只有1个关键字。 3)非根结点至少有Math.ceil(m/2)-1个关键字。 4)每个结点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。 5)所有叶子结点都位于同一层,或者说根结点到每个叶子结点的长度都相同。

上图是一颗阶数为4的B树。在实际应用中的B树的阶数m都非常大(通常大于100),所以即使存储大量的数据,B树的高度仍然比较小。每个结点中存储了关键字(key)和关键字对应的数据(data),以及孩子结点的指针。我们将一个key和其对应的data称为一个记录。但为了方便描述,除非特别说明,后续文中就用key来代替(key, value)键值对这个整体。在数据库中我们将B树(和B+树)作为索引结构,可以加快查询速速,此时B树中的key就表示键,而data表示了这个键对应的条目在硬盘上的逻辑地址。

1.1 B树的插入操作

插入操作是指插入一条记录,即(key, value)的键值对。如果B树中已存在需要插入的键值对,则用需要插入的value替换旧的value。若B树不存在这个key,则一定是在叶子结点中进行插入操作。

插入的时候,我们需要记住一个规则:判断当前结点key的个数是否小于等于m-1,如果满足,直接插入即可,如果不满足,将节点的中间的key将这个节点分为左右两部分,中间的节点放到父节点中即可。

1)根据要插入的key的值,找到叶子结点并插入。

2)判断当前结点key的个数是否小于等于m-1,若满足则结束,否则进行第3步。

3)以结点中间的key为中心分裂成左右两部分,然后将这个中间的key插入到父结点中,这个key的左子树指向分裂后的左半部分,这个key的右子支指向分裂后的右半部分,然后将当前结点指向父结点,继续进行第3步。

下面以5阶B树为例,介绍B树的插入操作,在5阶B树中,结点最多有4个key,最少有2个key

插入数据为:39,22,97,41,53,13,21,40,30,27, 33 ;36,35,34 ;24,29,26,17,28,29,31,32

下面是B树插入上述数据的动画:

插入步骤介绍:

a)在空树中插入39;此时根结点就一个key,此时根结点也是叶子结点 b)继续插入22,97和41;根结点此时有4个key c)继续插入53;插入后超过了最大允许的关键字个数4,所以以key值为41为中心进行分裂,结果如下图所示,分裂后当前结点指针指向父结点,满足B树条件,插入操作结束。当阶数m为偶数时,需要分裂时就不存在排序恰好在中间的key,那么我们选择中间位置的前一个key或中间位置的后一个key为中心进行分裂即可。 d)依次插入13,21,40,同样会造成分裂。 e)依次插入30,27, 33 ;36,35,34 ;24,29。 f)插入key值为26的记录,当前结点需要以27为中心分裂,并向父结点进位27,然后当前结点指向父结点。进位后导致当前结点(即根结点)也需要分裂。分裂后当前结点指向新的根,此时无需调整。 g)最后再依次插入key为17,28,29,31,32的记录,结果如上述动画最后的结果。

一般来说,对于确定的m和确定类型的记录,结点大小是固定的,无论它实际存储了多少个记录。但是分配固定结点大小的方法会存在浪费的情况,比如key为28,29所在的结点,还有2个key的位置没有使用,但是已经不可能继续在插入任何值了,因为这个结点的前序key是27,后继key是30,所有整数值都用完了。所以如果记录先按key的大小排好序,再插入到B树中,结点的使用率就会很低,最差情况下使用率仅为50%。

1.2 B树的删除操作

删除操作是指,根据key删除记录,如果B树中的记录中不存对应key的记录,则删除失败。

1)如果当前需要删除的key位于非叶子结点上,则用后继key(这里的后继key均指后继记录的意思)覆盖要删除的key,然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上,这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步

2)该结点key个数大于等于Math.ceil(m/2)-1,结束删除操作,否则执行第3步。

3)如果兄弟结点key个数大于Math.ceil(m/2)-1,则父结点中的key下移到该结点,兄弟结点中的一个key上移,删除操作结束。 否则,将父结点中的key下移与当前结点及它的兄弟结点中的key合并,形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针,指向这个新结点。然后当前结点的指针指向父结点,重复上第2步。 有些结点它可能即有左兄弟,又有右兄弟,那么我们任意选择一个兄弟结点进行操作即可。

下面以上述1.1 插入的一个5阶B树为例,介绍B树的删除操作,5阶B树中,结点最多有4个key,最少有2个key

1、在上面的B树中删除21,删除后结点中的关键字个数仍然大于等2,所以删除结束,如下动画所示:

2、在上述情况下接着删除27。27位于非叶子结点中,所以用27的后继替换它。从图中可以看出,27的后继为28,我们用28替换27,然后在28(原27)的右孩子结点中删除28。删除后发现,当前叶子结点的记录的个数小于2,而它的兄弟结点中有3个记录(当前结点还有一个右兄弟,选择右兄弟就会出现合并结点的情况,不论选哪一个都行,只是最后B树的形态会不一样而已),我们可以从兄弟结点中借取一个key。所以父结点中的22下移,兄弟结点中的26上移,删除结束。删除动画如下所示:

3、删除35数据,当前结点的记录数小于2,兄弟结点中没有多余key,所以父结点中的key下移,和兄弟(这里我们选择左兄弟,选择右兄弟也可以)结点合并,合并后的指向当前结点的指针就指向了父结点。对于当前结点而言只能继续合并了,合并后结点当前结点满足条件,删除结束。删除过程动画如下所示:

2.B+树

2.1 B+树的定义

各种资料上B+树的定义各有不同,一种定义方式是关键字个数和孩子结点个数相同。这里我们采取维基百科上所定义的方式,即关键字个数比孩子结点个数小1,这种方式是和B树基本等价的。

B+树其实B+树和B树是非常相似的,我们首先看看相同点:

  • 根节点至少一个元素
  • 非根节点元素范围:m/2 <= k <= m-1 除此之外B+树还有以下的要求。

1)B+树包含2种类型的结点:内部结点(也称索引结点)和叶子结点。根结点本身即可以是内部结点,也可以是叶子结点。根结点的关键字个数最少可以只有1个。 2)B+树与B树最大的不同是内部结点不保存数据,只用于索引,所有数据(或者说记录)都保存在叶子结点中。 3) m阶B+树表示了内部结点最多有m-1个关键字(或者说内部结点最多有m个子树),阶数m同时限制了叶子结点最多存储m-1个记录。 4)内部结点中的key都按照从小到大的顺序排列,对于内部结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。 5)每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序链接。

2.2 B+树的插入操作

1)若为空树,创建一个叶子结点,然后将记录插入其中,此时这个叶子结点也是根结点,插入操作结束。

2)针对叶子类型结点:根据key值找到叶子结点,向这个叶子结点插入记录。插入后,若当前结点key的个数小于等于m-1,则插入结束。否则将这个叶子结点分裂成左右两个叶子结点,左叶子结点包含前m/2个记录,右结点包含剩下的记录,将第m/2+1个记录的key进位到父结点中(父结点一定是索引类型结点),进位到父结点的key左孩子指针向左结点,右孩子指针向右结点。将当前结点的指针指向父结点,然后执行第3步。

3)针对索引类型结点:若当前结点key的个数小于等于m-1,则插入结束。否则,将这个索引类型结点分裂成两个索引结点,左索引结点包含前(m-1)/2个key,右结点包含m-(m-1)/2个key,将第m/2个key进位到父结点中,进位到父结点的key左孩子指向左结点, 进位到父结点的key右孩子指向右结点。将当前结点的指针指向父结点,然后重复第3步。

下面是一颗5阶B树的插入过程,5阶B数的结点最少2个key,最多4个key。

插入的数据为:5,8,10,15,16,17,18,6,9,19,20,21,22,7

B+树插入上述数据的动画如下:

B+树插入上述数据的步骤如下:

a)空树中插入5 b)依次插入8,10,15 c)插入16;插入16后超过了关键字的个数限制,所以要进行分裂。在叶子结点分裂时,分裂出来的左结点2个记录,右边3个记录,中间key成为索引结点中的key,分裂后当前结点指向了父结点(根结点)。当然我们还有另一种分裂方式,给左结点3个记录,右结点2个记录,此时索引结点中的key就变为15。 d)插入17 e)插入18;当前结点的关键字个数大于5,进行分裂。分裂成两个结点,左结点2个记录,右结点3个记录,关键字16进位到父结点(索引类型)中,将当前结点的指针指向父结点。当前结点的关键字个数满足条件,插入结束。 f)插入若干数据后 g)插入7,当前结点的关键字个数超过4,需要分裂。左结点2个记录,右结点3个记录。分裂后关键字7进入到父结点中,将当前结点的指针指向父结点。 当前结点的关键字个数超过4,需要继续分裂。左结点2个关键字,右结点2个关键字,关键字16进入到父结点中,将当前结点指向父结点,结果如下图所示。 当前结点的关键字个数满足条件,插入结束。

2.3 B+树的删除操作

如果叶子结点中没有相应的key,则删除失败。否则执行下面的步骤

1)删除叶子结点中对应的key。删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1,删除操作结束,否则执行第2步。 2)若兄弟结点key有富余(大于Math.ceil(m-1)/2 – 1),向兄弟结点借一个记录,同时用借到的key替换父结(指当前结点和兄弟结点共同的父结点)点中的key,删除结束。否则执行第3步。 3)若兄弟结点中没有富余的key,则当前结点和兄弟结点合并成一个新的叶子结点,并删除父结点中的key(父结点中的这个key两边的孩子指针就变成了一个指针,正好指向这个新的叶子结点),将当前结点指向父结点(必为索引结点),执行第4步(第4步以后的操作和B树就完全一样了,主要是为了更新索引结点)。 4)若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1,则删除操作结束。否则执行第5步 5)若兄弟结点有富余,父结点key下移,兄弟结点key上移,删除结束。否则执行第6步 6)当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点,重复第4步。 注意,通过B+树的删除操作后,索引结点中存在的key,不一定在叶子结点中存在对应的记录。

下面上述插入的是一颗5阶B树的删除过程,5阶B数的结点最少2个key,最多4个key。

1、删除22;删除后叶子结点中key的个数大于等于2,删除结束删除动画如下所示:

2、删除15,删除后当前结点只有一个key,不满足条件,而兄弟结点有三个key,可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9,删除结束;删除动画如下所示:

3、删除7;当前结点关键字个数小于2,(左)兄弟结点中的也没有富余的关键字(当前结点还有个右兄弟,不过选择任意一个进行分析就可以了,这里我们选择了左边的),所以当前结点和兄弟结点合并,并删除父结点中的key,当前结点指向父结点。此时当前结点的关键字个数小于2,兄弟结点的关键字也没有富余,所以父结点中的关键字下移,和两个孩子结点合并,删除过程如下所示:

3. B树和B+树总结

B+树相对于B树有一些自己的优势,可以归结为下面几点:

1、单一节点存储的元素更多,使得查询的IO次数更少,所以也就使得它更适合做为数据库MySQL的底层数据结构了。

2、所有的查询都要查找到叶子节点,查询性能是稳定的,而B树,每个节点都可以查找到数据,所以不稳定。

3、所有的叶子节点形成了一个有序链表,更加便于查找。

本文分享自微信公众号 - DBA的辛酸事儿(dbabitter),作者:SEianG

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-05-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【深入学习MySQL】MySQL的索引结构为什么使用B+树?

    在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决...

    Java_老男孩
  • MySQL为什么要使用B+树索引

    搞懂这个问题之前,我们首先来看一下MySQL表的存储结构,再分别对比二叉树、多叉树、B树和B+树的区别就都懂了。

    java乐园
  • 为什么Mongodb索引用B树,而Mysql用B+树?

    好久没写文章了,今天回来重操旧业。 今天讲的这个主题,是《面试官:谈谈你对mysql索引的认识》,里头提到的一个坑。

    帅地
  • 为什么Mongodb索引用B树,而Mysql用B+树?

    好久没写文章了,今天回来重操旧业。 今天讲的这个主题,是《面试官:谈谈你对mysql索引的认识》,里头提到的一个坑。

    Java3y
  • 为什么MongoDB索引用B树,而Mysql用B+树?

    如果面试官问的是,为什么Mysql中Innodb的索引结构采取B+树?这个问题时,给自己留一条后路,不要把B树喷的一文不值。因为网上有些答案是说,B树不适合做文...

    week
  • 为什么MySQL索引要用B+树,而不是B树?

    原文链接:https://www.cnblogs.com/leefreeman/p/8315844.html

    业余草
  • MySQL索引为什么要用B+树实现?

    在从一堆数据中查找指定的数据时,我们常用的数据结构是哈希表和二叉查找树,表本质上就是一堆数据的集合,所以MySQL数据库用了B+树和哈希表来实现索引

    Java识堂
  • B树和B+树对比,为什么MySQL数据库索引选择使用B+树?

    B+树是B树的一个变形,非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中,

    ydymz
  • 为什么MySQL数据库索引选择使用B+树?

    在进一步分析为什么MySQL数据库索引选择使用B+树之前,我相信很多小伙伴对数据结构中的树还是有些许模糊的,因此我们由浅入深一步步探讨树的演进过程,在一步步引出...

    Java后端技术
  • 为什么MySQL数据库索引选择使用B+树?

    我们在MySQL中的数据一般是放在磁盘中的,读取数据的时候肯定会有访问磁盘的操作,磁盘中有两个机械运动的部分,分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所...

    用户3467126
  • 数据库索引为什么使用B+树?

    java404
  • 为什么MySQL InnoDB 存储引擎要用B+树做索引,而不用B树?

    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗。而因为B+树的内部节...

    一个会写诗的程序员
  • [MySQL] B+树索引为什么比B树的好

    B树的数据指针存储在各层节点中 , B+树的数据都存储在了叶子节点 , 那查找的时候B+树比B树效率按逻辑应该更高吗?

    陶士涵
  • 面试官:为什么 MySQL 的索引要使用 B+ 树,而不是其它树?比如 B 树?

    来源 | https://www.cnblogs.com/leefreeman/p/8315844.html

    五分钟学算法
  • It's Design——为什么MySQL使用B+树?

    相信每一个后台开发工程师在面试过程中,都曾经被问到过“MySQL的默认存储引擎是什么?MySQL索引是什么数据结构?”这样的问题。相信准备充分(熟读八股文)的大...

    yuann
  • 面试官:为什么 MySQL 索引要使用 B+树而不是其它树形结构?比如 B 树?

    https://www.cnblogs.com/leefreeman/p/8315844.html?from=singlemessage&isappinstal...

    挨踢小子部落阁
  • 面试官:为什么 MySQL 索引要使用 B+树而不是其它树形结构?比如 B 树?

    https://www.cnblogs.com/leefreeman/p/8315844.html?from=singlemessage&isappinstal...

    哲洛不闹
  • 一篇文章讲透MySQL为什么要用B+树实现索引

    索引这个词,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述的很完整。本文就来从...

    用户1260737
  • Mysql的索引结构为什么要用B+数

    在MySQL中,无论是Innodb还是MyIsam,都使用了B+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决...

    程序员白楠楠

扫码关注云+社区

领取腾讯云代金券