文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 2407
阅读 1
收藏 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)所示。

 

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2012/12/28/5637130.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
B树、B+树、B-树

1、多路查找树(mutil-way search tree)定义 多路查找树,其每一个节点的孩子数可以多于两个,且每一个节点处可以存储多个元素。 由于它是查找树,所以元素之间存在某种特定的排序关系。由于...

笨拙的小Q
2016/06/29
88
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
05/08
0
0
算法之树(一,B-树原理详解)(Java版)-持续更新补充

因为是复习,从基础开始一起复习。 如果冲着标题来的,可以直接跳到后半部分看B树的内容(~ ̄▽ ̄)~ 支持云栖社区!同时俺也有自己的独立博客——白水东城,因为在社区博客里只能发发技术文...

kissjz
08/11
0
0
B树、B-树、B+树、B树都是什么

B树、B-树、B+树、B*树都是什么 B树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指...

racoon
2011/05/09
0
2
B树、B-树、B+树、B*树 总结

学习Kafka时遇到B树,突然想起B树、B-树、B+树、B*树,概念有点模糊了,查找到一篇好的资料,学习一下 B树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存...

u012050154
2017/07/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

转:XMLHttpRequest2 新技巧

”XMLHttpRequest 的异步调用网上找的例子运行没问题,但稍微改了一点点就报错”InvalidStateError: XMLHttpRequest has an invalid context“。断断续续 搞了3天终于通了,可以接收二进制文...

SamXIAO
16分钟前
0
0
=====D服务器定时任务=====

Linux定时任务 crontab linux系统是有cron这个系统服务来控制的,Liunx系统上包含很多的计划性工作,使用者自己可以设置计划任务,所以linux系统提供了使用者控制计划任务的命令 crontab的启...

覃光林
25分钟前
0
0
xilinx资源

本系列教学视频由赛灵思高级战略应用工程师带领你:从零开始,一步步深入 掌握 HLS 以及 UltraFAST 设计方法,帮助您成为系统设计和算法加速的大拿! http://www.eetrend.com/topics/2018-0...

whoisliang
36分钟前
2
0
企业级开源四层负载均衡解决方案--LVS

网盘链接 企业级开源四层负载均衡解决方案--LVS 本课程将在Linux环境下,学习配置使用LVS,对Web集群和MySQL集群进行负载均衡,并结合利用Keepalived实现负载均衡器的高可用,实现对后端Rea...

qq__2304636824
45分钟前
3
0
Windows上安装Spacemacs

emacs安装 下载地址emacs 安装比较简单,解压后执行\bin\addpm.exe即可 emacs配置 emacs的默认配置文件路径和.emacs.d文件夹都是在Windows主目录下的 C:\Users\Administrator\AppData\Roami...

yxmsw2007
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部