文档章节

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

小强斋太
 小强斋太
发布于 2016/11/09 20:06
字数 2407
阅读 2
收藏 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
二叉查找树,红黑树,AVL树,B~/B+树(B-tree),伸展树——优缺点及比较

本文转载自:http://blog.csdn.net/bytxl/article/details/40920165 二叉查找树(Binary Search Tree) BST 的操作代价分析: (1) 查找代价: 任何一个数据的查找过程都需要从根结点出发,沿某...

亮亮-AC米兰
2017/01/17
0
0
为什么MySQL数据库要用B+树存储索引?

要回答好这个问题,首先我们要弄懂什么是索引?索引常见的数据结构有哪些?这些数据结构有何优缺点?只有弄懂这些,再去比较,才会知道为啥要用B+树作为MySQL数据库的存储索引了。 一、索引是...

Lienson
2018/12/12
0
0
MySQL 索引 BST树、B树、B+树、B*树

一、二叉查找树(Binary Search Tree)BST 即二叉搜索树: 所有非叶子结点至多拥有两个儿子(Left和Right); 所有结点存储一个关键字; 非叶子结点的左指针指向小于其关键字的子树,右指针指...

PeakFang-BOK
2018/11/13
0
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

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

snailclimb
2018/05/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周三乱弹 —— 风扇写着先生请自爱

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @蚂蚁哈哈哈 :分享陈奕迅的单曲《落花流水》 《落花流水》- 陈奕迅 手机党少年们想听歌,请使劲儿戳(这里) @车谷 :我发现每天上班都好困 ...

小小编辑
40分钟前
4
0
centos7重置密码、单用户模式、救援模式、ls命令、chmod命令

在工作当中如果我们错误的配置了文件使服务器不能正常启动或者忘记密码不能登录系统,如何解决这些问题呢?重装系统是可以实现的,但是往往不能轻易重装系统的,下面用忘记密码作为例子讲解如...

李超小牛子
今天
3
0
Python如何开发桌面应用程序?Python基础教程,第十三讲,图形界面

当使用桌面应用程序的时候,有没有那么一瞬间,想学习一下桌面应用程序开发?行业内专业的桌面应用程序开发一般是C++,C#来做,Java开发的也有,但是比较少。本节课会介绍Python的GUI(图形用...

程序员补给栈
今天
8
0
kafka在的使用

一、基本概念 介绍 Kafka是一个分布式的、可分区的、可复制的消息系统。它提供了普通消息系统的功能,但具有自己独特的设计。 这个独特的设计是什么样的呢? 首先让我们看几个基本的消息系统...

狼王黄师傅
今天
3
0
Android JNI总结

0x01 JNI介绍 JNI是Java Native Interface的缩写,JNI不是Android专有的东西,它是从Java继承而来,但是在Android中,JNI的作用和重要性大大增强。 JNI在Android中起着连接Java和C/C++层的作...

天王盖地虎626
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部