文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 2407
阅读 1
收藏 0
点赞 0
评论 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树、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
从B 树、B+ 树、B* 树谈到R 树

作者:July、weedge、Frankie。编程艺术室出品。 说明:本文从B树开始谈起,然后论述B+树、B树,最后谈到R 树。其中B树、B+树及B树部分由weedge完成,R 树部分由Frankie完成,全文最终由Jul...

布几岛
2014/06/27
0
0
B树 B-树 B+树 B*树

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

青夜之衫
2017/12/05
0
0
从B树、B+树、B*树谈到R 树

从B 树、B+ 树、B 树谈到R 树 作者:July、weedge、Frankie。编程艺术室出品。 说明:本文从B树开始谈起,然后论述B+树、B树,最后谈到R 树。其中B树、B+树及B树部分由weedge完成,R 树部分由...

Picasso
2011/09/16
0
0
从B 树、B+ 树、B* 树谈到R 树

从B 树、B+ 树、B* 树谈到R 树 作者:July、weedge、Frankie。编程艺术室出品。 说明:本文从B树开始谈起,然后论述B+树、B树,最后谈到R 树。其中B树、B+树及B树部分由weedge完成,R 树部分...

vincent_y
2013/11/27
0
0
B树,B+树,B*树学习笔记

B B+ 这两种处理索引的数据结构的不同之处: 1. B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中.而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有...

liujiest
2016/04/30
214
0
ADT - 树

定义 一棵树是一些节点的集合。这个集合可以是空集,若非空,则一棵树由称作 根(root) 的节点 r 和 0 个或以上的非空子树组成。这些子树中每一棵的根都被来自根 r 的一条有向边(edge)连接。 ...

lionets
2016/08/05
19
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

ES15-JAVA API 索引管理

1.创建连接 创建连接demo package com.sean.esapi.client;import java.net.InetSocketAddress;import org.elasticsearch.action.get.GetResponse;import org.elasticsearch.clien......

贾峰uk
4分钟前
0
0
单点登录的设计,从单域名到多域名(经验分享)

个人实践总结,最初的的需求,多个产品线都在同一个根域名下面。 独立的用户中心分离,单独负责用户登录和用户信息获取、变更等处理逻辑。 第一步,用户登录成功,分配给用户一个memToken(令...

小海bug
6分钟前
0
0
合格前端第十二弹-TypeScript + 大型项目

写在前面 TypeScript 已经出来很久了,很多大公司很多大项目也都在使用它进行开发。上个月,我这边也正式跟进一个对集团的大型运维类项目。 项目要做的事情大致分为以下几个大模块 一站式管理...

qiangdada
9分钟前
0
0
编程学习之如何在Node.js中优化服务器端渲染?[图]

编程学习之如何在Node.js中优化服务器端渲染?[图] 在 Airbnb,我们花了数年时间将所有前端代码迁移到 React 架构,Ruby on Rails 在 Web 应用中所占的比例每天都在减少。实际上,我们很快会...

原创小博客
11分钟前
0
0
gradle学习笔记

相关文档 适合新手的 gradle 自学教程合集 Gradle教程

OSC_fly
25分钟前
0
0
Virtual Serial Port - RFC2217

Virtual Serial Port for Linux RFC-2217 The COM Port Control Protocol pyserial - RFC 2217 NetSerial - Windows Telnet COM Port - RFC Official Using Python, How do I make a virtual......

zungyiu
32分钟前
0
0
全球的IPv6部署急剧增加,中国进度较慢

导读 全球的IPv6部署继续增加,但中国在IPv6方面还需要努力,从部署图上分析,中国几乎没有几个地方是普及IPv6的。这6年来,自世界IPv6发布以来,全球网络和服务提供商的IPv6部署水平急剧增加...

问题终结者
36分钟前
1
0
好看的电影记录

星际迷航三 狂暴之路 新木乃伊 黑夜传说 铁血战士2

xd03122049
40分钟前
0
0
记录Yii2框架开发遇到微信错误提示

转载地址 记录Yii2框架开发遇到微信错误提示 微信公共号开发,提示“该公众号暂时无法提供服务,请稍后再试”,如何解决? 以前使用Yii框架的时候,并没有像Yii2,以前的Yii框架似乎用起来在...

durban
42分钟前
1
0
LSM树(Log-Structured Merge Tree)存储引擎浅析

其实每一种数据库,它都是一种抽象的数据结构的具体实现。 随着rocksDB(facebook的),levelDB(google的),以及我们熟知的hbase,他们都是使用的LSM树结构的数据库。 它的核心思路其实非常...

算法之名
55分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部