文档章节

动态查找---->B树(broad-tree 平衡多路查找树)

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 2407
阅读 261
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

B-tree的引入 可以讲B理解成 broad

在现代计算机中通常采用分级存储系统,以最简单的二级分级存储策略为例,就是由内存储器与外存储器(磁盘)组成二级存储系统。这一策略的思想是:将最常用的数据副本存放于内存中,而大量的数据存放于外存中,借助有效的算法可以将外存的大存储量与内存高速度的优点结合起来。

一般的,在分级存储系统中,各级存储器的速度有着巨大的差异,仍然以磁盘和内存为例,前者的平均访问速度为10ms左右,而内存储器的平均访问时间为ns级,通常在10~100ns左右,二者之间差异大约为106。因此,为了节省一次外存储器的访问,我们宁愿多访问内存储器一百次、一千次甚至一万次。

当问题规模太大时,以至于内存储器无法容纳时,即使是前面介绍的AVL 树,在时间上也会大打折扣。B-tree确是一种可以高效解决这个问题的一种数据结构。

B-tree定义(即B-tree是所有结点的平衡因子均为0的多叉查找树

所谓m阶B-tree或者为空树,或为满足下列特性的m叉树:

1. 树中每个结点至多有m棵子树;

2. 若根结点不是叶子结点,则至少有两棵子树;

3. 除根结点之外的所有非终端结点至少有⎡m/2⎤棵子树;

4. 所有的非终端结点中包含以下信息数据:(n, A0 ,K1 ,A1 ,K2 ,… , Kn ,An)其中:,①n为结点中关键字的个数,除根结点外,其他所有结点的关键字个数n,满足⎡m/2⎤-1≤n≤ m-1;Ki(i=1,2,…,n)为关键字,且Ki<Ki+1,Ai为指向子树根结点的指针(i=0,1,…,n),且指针Ai-1所指子树中所有结点的关键字均小于Ki (i=1,2,…,n),An所指子树中所有结点的关键字均大于Kn,⎡m/2⎤ −1≤ n ≤ m −1 ,n为关键码的个数。

5. 所有的叶子结点都出现在同一层次上,即B-tree是所有结点的平衡因子均为0的多叉查找树。并且不带信息(黑色的方块可以看成叶子节点,可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空,即箭头的尾部保存∧)。

关键字的查找

B-tree的查找类似二叉排序树的查找,所不同的是B-tree每个结点上是多关键码的有序表,在到达某个结点时,先在有序表中查找,若找到,则查找成功;否则,到按照对应的指针信息指向的子树中去查找,当到达叶子结点时,则说明树中没有对应的关键码,查找失败。即在B-tree上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程。例如在图中所示的B-tree中查找23 和47 的过程为虚线所示的路径。

正如前面所指出的,B-tree的查找适合于大规模的数据。实际的做法是,将大量数据组织为一棵B-tree,并存于外存储器,B-tree的根结点常驻内存。一旦需要查找,则按照上述过程,首先将根结点作为当前结点,在当前结点中顺序查找;如果当前结点不存在需要查找的关键字,则根据相应的引用,找到外存中的某一个下层结点,将其读入内存,作为新的当前结点继续查找。如此进行下去,直到相应关键字或查找失败。

由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:

其中,M为设定的非叶子结点最多子树个数,N为关键字总数;所以B-tree的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;

关键字的插入操作

B-tree的生成:从空树起逐个插入关键字便可生成B-tree。

为了在m 阶B-tree中插入一个新关键字key,首先要找到该关键字应该插入的位置,该过程实际是在B-tree中查找关键字的过程。倘若查找成功,则不再插入重复的关键字,若查找不成功,则在此查找过程中遇到的最后一个非叶子结点p,即为关键字key的插入位置。然后,在结点p 中,按照关键字有序的顺序将key插入。若插入后结点p 关键字个数不超过m−1个,则可直接插入到该结点上;否则,要进行调整,即结点的“分裂”。

将关键字k插入到B-tree中的过程分两步完成:

(1)利用B-tree的查找算法找出该关键字的插入结点(注意B-tree的插入结点一定是叶子结点)。

(2)若该结点关键字个数n<m-1,说明该结点还有空位置,直接把关键字k插入到该结点的合适位置上;

(3)若该结点关键字个数n=m-1,说明该结点已没有空位置,插入后需按以下方法把该结点分裂成两个结点:分配一新结点,把需分裂结点上的关键字从中间位置(即⎡m/2⎤处)分成两部分,左部分所含关键字放在旧结点中,右部分所含关键字放在新结点中,中间位置的关键字连同新结点的存储位置插入到父亲结点中。如果父结点的关键字个数也超过M-1,则要再分裂,再往上插,直至这个过程传到根结点为止。

例子:

 

 

 

关键字的删除操作

与插入关键字相反,若在B-tree上删除一个关键字,则首先应该找到该关键字所在的结点u,并从中删除。

如果删除的关键字在非叶子节点x中,x的数组下标为i

    a.如果x的左孩子节点存在,x->child[i],并且x->child[i]的节点关键字个数至少是n个,则找到        child[i]中最大的关键字max替换x中删除的关键字,继续递归child[i]删除关键字max

 

b.如果x的右孩子节点存在,x->child[i+1],并且x->child[i+1]的节点关键字个数至少是n个,则找到 child[i+1]中最小的关键字min替换x中删除的关键字,继续递归child[i+1]删除关键字min

例如在图所示的5阶B-tree中删除关键字46,可以用关键字48替代,然后再删除关键字48即可,结果如图(b)所示;

在B-tree的叶子结点上删除关键字共有以下三种情况:

①  假如被删结点的关键字个数大于Min,说明删去该关键字后该结点仍满足B-tree的定义,则可直接删去该关键字;

②假如被删结点的关键字个数等于Min,说明删去关键字后该结点将不满足B-tree的定义,此时若该结点的左(或右)兄弟结点中关键字个数大于Min,则把该结点的左(或右)兄弟结点中最大(或最小)的关键字上移到双亲结点中,同时把双亲结点中大于(或小于)上移关键字的关键字下移到要删除关键字的结点中,这样删去关键字k后该结点以及它的左(或右)兄弟结点都仍旧满足B-tree的定义

从左兄弟“借”关键字

从右兄弟“借”关键字

 

例子:

继续删除关键字20,因为20 所在结点关键字数目达到下限⎡m/2⎤ −1,而其右兄弟有多余的关键字,因此可以向其右兄弟“借”一个关键字30,结果如图(c)所示;

③ 假如被删结点的关键字个数等于Min,并且该结点的左右兄弟结点中关键字个数均等于Min,这时,需把要删除关键字的结点与其左(或右)兄弟结点以及双亲结点中分割二者的关键字合并成一个结点.如果因此使双亲结点中关键字个数小于Min,则对此双亲结点作同样的处理,以致于可能直到对根结点作这样的处理而使整个树减少一层.

从父亲“借”关键字

例子:

若在(c)基础上继续删除关键字3,由于3 所在结点的所有兄弟的关键字数目均达到下限,因此在删除3 后,将剩余关键字7 与父结点中关键字12、以及其右兄弟结点中关键字一起组成一个新结点,如图(d)所示,由于父结点中减少一个关键字,导致父结点关键字数目小于⎡m/2⎤ −1,因此再对父结点进行修复,如图(e)所示。

 

 

小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
私信 提问
加载中
请先登录后再评论。
B树B+树

动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree),红黑树(Red-Black Tree ),B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查...

无心是一首歌
2019/03/02
0
0
红黑树、自平衡二叉树、AVL树、B树的比较

红黑树和自平衡二叉(查找)树区别 1.红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简...

靖凯
03/05
1
0
B树

多路查找树(mutil-way search tree)其每个节点的孩子数可以多于两个,且每个结点处可存储多个元素。 4中特殊形式:2-3树、2-3-4树、B树、B+树 2-3树: 是这样的一棵多路查找树:其中的每个...

SibylY
2013/08/19
53
0
AVL树、红黑树以及B树介绍

简介 首先,说一下在数据结构中为什么要引入树这种结构,在我们上篇文章中介绍的数组与链表中,可以发现,数组适合查询这种静态操作(O(1)),不合适删除与插入这种动态操作(O(n)),而链表则是适...

osc_kjmfkyv9
2018/07/22
1
0
B-Tree与B+Tree的区别

二叉树: 左右两个子节点 可以为空 二叉查找树: 左子树小于根节点,又子树大于根节点 平衡二叉树: 任何节点的左右两个子树的高度相差最大为1,(高度相差大于1会旋转操作) B-Tree:(平衡多...

osc_1wnye1so
2018/09/03
13
0

没有更多内容

加载失败,请刷新页面

加载更多

还在用Swagger(丝袜哥)生成接口文档?我推荐你试试它.....

JApiDocs是一个无需额外注解、开箱即用的SpringBoot接口文档生成工具。 编写和维护API文档这个事情,对于后端程序员来说,是一件恼人但又不得不做的事情,我们都不喜欢写文档,但除非项目前后...

路人甲Java
07/09
7
0
智能仓储的独角兽逻辑

智能仓储的主要应用市场在哪里?客户的付费意愿和付费能力如何? 1、仓储设备具备标准化和通用化特点 由于电商和新零售的快速发展,轻工业品零售仓库的需求量大幅增加。而中国又是全球轻工业...

logiter
2019/08/23
14
0
可是小腿哪能扭过大腿

父亲是一个特别勤苦的人,他从不睡懒觉,每天天麻麻亮,或是下地干活,或是在家搞副业,或是拿着铁锨、粪筐,到路边,到村子周围,到牲畜常出入的地方,去拾粪蛋子,为庄稼积攒肥料,父亲不仅...

瑾123
29分钟前
16
0
一个volatile跟面试官扯了半个小时

《安琪拉与面试官二三事》系列文章,本文是此系列第三篇 一个HashMap能跟面试官扯上半个小时 一个synchronized跟面试官扯了半个小时 欢迎关注Wx公众号:【安琪拉的博客】—揭秘Java后端技术,...

osc_6ls9vwji
30分钟前
0
0
内网渗透靶机-VulnStack 2

WEB服务器:windows2008系统 外网网卡IP:192.168.1.152 内网网卡IP:10.10.10.80 域成员:windows server 2003系统 网卡IP:10.10.10.200 域控服务器:windows server 2008系统 网卡IP:192...

dnsil
07/10
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部