您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

数据库系统:使用例子解释B树中元素的添加和删除

在计算机科学中,B树(英语:B-tree)是一种自平衡的树,能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,都在对数时间内完成。B树,概括来说是一个一般化的二叉查找树(binary search tree)一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同,B树适用于读写相对大的数据块的存储系统,例如磁盘。B树减少定位记录时所经历的中间过程,从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。——维基百科

每个B树存在一个参数m,每个节点可以存储最少m-1,最多2m-1个值,也就是说每个节点可以存储最少m个、最多2m个指向子节点的key。其中,根结点可以存储少于m个节点。

以两道题为例详解B树中元素的添加和删除,题中m=3.

个人经验:任何一个非叶节点,里面的任何节点,都应该有左节点和右节点。

1. 将50添加到B树中

在这里插入图片描述
添加键值对的规则:
1.总是被添加进叶子节点。
2.当被添加节点超过2m-1个值,将叶子节点拆分,将中间节点加入其父节点。如果使得父节点超过2m-1个值,则继续递归拆分父节点。当根节点被拆分,应该重新建立新的根节点,

那么这一题,我们首先尝试将50添加到叶子节点中,发现可以添加到结点38~49,但是该节点即将超过2m-1个值,所以将中间值42升至父节点,从而拆分该叶节点。

在这里插入图片描述
同理,父节点也将以37为中间值进行拆分,37将升入其父节点(此处省略)。
在这里插入图片描述

2.删除B树中的51

在这里插入图片描述
删除key的规则:
如果当前需要删除的key位于非叶子节点上,
1.则用后继key(这里的后继key均指后继记录的意思)覆盖要删除的key,然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上,这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步
2.该结点key个数大于等于m-1,结束删除操作,否则执行第3步。
3.如果兄弟结点key个数大于m-1,则父结点中的key下移到该结点,兄弟结点中的一个key上移,删除操作结束。
否则,将父结点中的key下移与当前结点及它的兄弟结点中的key合并,形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针,指向这个新结点。然后当前结点的指针指向父结点,重复上第2步。

如果当前需要删除的key位于叶子节点上,直接删除,然后根据B树的原则使用兄弟节点进行平衡。

那么这一题,我们发现51位于42的右节点,将其删去,发现该节点子节点的数量少于m-1个,然后发现其兄弟节点只有m-1个节点,满足融合条件,融合在一起。
在这里插入图片描述

参考链接:
https://zh.wikipedia.org/wiki/B%E6%A0%91
https://zhuanlan.zhihu.com/p/134056266
https://www.cnblogs.com/nullzx/p/8729425.html


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进