标签搜索

目 录CONTENT

文章目录

B+树和B*树详解.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 6 阅读 / 3,209 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

B+树和B*树详解

@[toc]

一、B+树

1.B+树的定义

在这里插入图片描述

2.性质

B+树是B树的变体,也是一种多路搜索树,除了:

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

3. 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。

  •  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进入到父结点中,将当前结点指向父结点,结果如下图所示。
    在这里插入图片描述
    当前结点的关键字个数满足条件,插入结束。

4.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。
  •  a)初始状态
    在这里插入图片描述
  •  b)删除22,删除后结果如下图
    在这里插入图片描述
    删除后叶子结点中key的个数大于等于2,删除结束
  •  c)删除15,删除后的结果如下图所示
    在这里插入图片描述
  •  删除后当前结点只有一个key,不满足条件,而兄弟结点有三个key,可以从兄弟结点借一个关键字为9的记录,同时更新将父结点中的关键字由10也变为9,删除结束。
    在这里插入图片描述
  •  d)删除7,删除后的结果如下图所示
    在这里插入图片描述
  •  当前结点关键字个数小于2,(左)兄弟结点中的也没有富余的关键字(当前结点还有个右兄弟,不过选择任意一个进行分析就可以了,这里我们选择了左边的),所以当前结点和兄弟结点合并,并删除父结点中的key,当前结点指向父结点

在这里插入图片描述

  •  此时当前结点的关键字个数小于2,兄弟结点的关键字也没有富余,所以父结点中的关键字下移,和两个孩子结点合并,结果如下图所示。
    在这里插入图片描述

二、B*树

1.概念

是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;
在这里插入图片描述

2.性质

  •  B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);
  •  B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;
  •  B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;
  •  B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);
  •  如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;
  •  所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

3.总结

1.B-/B树:

关键字的数量比孩子的数量少一,M阶的B-/B树最多有M个孩子,M- 1个关键字。分裂的方式把关键字已经满的节点中的数据移动1/2到另一个节点

2.B+树:

B+树中关键字的数量和孩子的数量相等,在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引,遍历叶子节点就可以得到所有的数据;B+树总是到叶子结点才命中。M阶的B+树一个节点最少有M/ 2个关键字。分裂的方式把关键字已经满的节点中的数据拷贝1/2到另一个新节点

3.B*树:

在B+树基础上,为非叶子结点也增加链表指针,M阶的B树一个节点最少有M 2/3 个关键字,将结点空间的最低利用率从1/2提高到2/3分裂的方式是:如果它的下一个兄弟节点的关键字没满,就把关键字已经满的节点中的数据移动到兄弟节点当中;如果兄弟节点也满了,就在二者之间增加新节点,各复制1/3的数据到新节点当中

0

评论区