6.3.1 B树及其基本操作

B树,又称多路平衡查找树,B树中所有节点的孩子结点数的最大值成为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

1)树中每个结点至多有m棵子树(即至多含有m-1个关键字)。

2)若根结点不是终端结点,则至少有两棵子树。

3)除根结点外的所有非叶结点至少有【m/2】(向下取整)棵子树(即至少含有【m/2】-1个关键字)

4)所有非叶结点的结构如下:

n

P0

K1

P1

k2

P2

...

Kn

Pn

其中,Ki(i=1,2,...,n)为结点的关键字,且满足K1<K2<···<Kn;Pi(i=0,1,···,n)为指向子树根结点的指针,且指针Pi-1所指向子树中所有结点的关键字均小于Ki,Pi所指子树中所有结点的关键字均大于Ki,n( 向下取整【m/2】-1<=n<=m-1 )为结点中关键字的个数。

5)所有的叶节点都出现在同一层次上,并且不带信息(可以看做是外部结点或者类似于折半查找判定树的查找失败结点,实际上这些结点不存在,指向这些结点的指针为空)。

B树是所有结点的平衡因子均等于0的多路查找树,其中底层方形结点表示叶结点,在这些结点中没有存储任何信息。

1.B树的高度(磁盘存取次数)

由下一节可知,B树中的大部分操作所需的磁盘存取次数与B树的高度成正比。

下面来分析B树在不同的情况下的高度。当然,首先应明确B树的高度不包括最后的不带任何信息的叶结点所处的那一层。

如果n>=1,则对任意一棵包含n个关键字,高度为h,阶数为m的B树:

1)因为B树中每个结点最多有m棵子树,m-1个关键字,所以在一棵高度为h的m阶B树中关键字的个数应满足n<=(1+m+m^2+……+m^(h-1))=m^h-1。因此有

h>=logm  (n+1)(由关键字个数计算B树的最小高度) 2)若让每个结点的关键字个数达到最少,则容纳同样多关键字的B树的高度可达到最大。

由B树定义:

第一层至少有1个结点;

第二层至少有2个结点;

除根结点以外的每个非终端结点至少有【m/2】(向下取整)棵子树,则第三层至少有2*【m/2】(向下取整)个结点

……

第h+1层至少有2*(【m/2】向下取整)^(h-1)个结点,注意到第h+1层是不包含任何信息的叶结点。

对于关键字个数为n的B树,叶结点即查找不成功的结点为n+1,

由此有n+1>2*([m/2]向下取整)^(h-1),

即h<=log[m/2](向下取整)((n+1)/2)+1(由关键字个数计算B树的最大高度)。

假设一棵3阶B树,共有8个关键字,则其高度范围为2<=h<=3.17

2.B树的查找

在B树在进行查找二叉树很相似,只是每个结点都是多个关键字的有序表,在每个结点上所做的不是两路分支决定,而是根据该结点的子树所做的多路分支决定。

B树的查找包含两个基本操作:

①在B树中找结点;

②在结点中找关键字。

由于B树常存储在磁盘上,则前一个查找操作是在磁盘上进行的,而后一个操作是在内存中进行的,即在找到目标结点后,先将结点中的信息读入内存,然后再顺序查找法或折半查找法查找等于k的关键字。

在B树上查找到某个结点后,先在有序表中进行查找,若找到则查找成功,否则按照对应的指针信息到所指的子树中查找。当查找到叶结点时(对应的指针为空指针),则说明树中没有对应的关键字,查找失败。

3.B树的插入

与二叉查找树的插入操作相比,B树的插入操作要复杂得多。在二叉查找树中,仅需查找到需插入的终端结点的位置。但是,在B树中找到插入的位置后,并不能简单地将其加到终端结点中去,因为此时可能导致整棵树不再满足B树中定义的要求。将关键字key插入到B树的过程如下:

1)定位:利用前述的B树查找算法,找出插入该关键字的最底层中某个非叶结点(注意,B树中的插入关键字一定是插入在最底层中的某个非叶子结点内)

2)插入:在B树中,每个非失败结点的关键字个数都在【(m/2)向下取整-1,m-1】之间。当插入后的结点关键字个数小于m,则可以直接插入;插入后检查被插入结点内关键字的个数,当插入后的结点关键字个数大于m-1时,则必须对结点进行分裂。

分裂的方法是:取一个新结点,将插入key后的原结点从中间位置将其中的关键字分为两部分,左部分包含的关键字放在原结点中,右部分包含的关键字放在新的结点中,中间位置(【m/2】向下取整)的结点插入到原结点的父结点中。若此时导致其父结点的关键字个数也超过了上限,则继续进行这种分裂操作,直到这个过程传到根结点为止,这样导致B树高度增1。

4.B树的删除

B树中的删除操作与插入操作类似,但要稍微复杂些,要使删除后的结点的关键字个数>=([m/2]向下取整)-1,因此涉及结点的合并问题。

当所删除的关键字k不在终端结点(最底层非叶结点)中时,有下列几种情况:

1)如果小于k的子树中关键字个数>([m/2]向下取整)-1,则找出k的的前驱值K',并且用K'来取代k,再递归地删除K'即可。

2)如果大于k的子树中关键字个数>([m/2]向下取整)-1,则找出k的的后继值K',并且用K'来取代k,再递归地删除K'即可。

3)如果前后两个子树中关键字个数均为([m/2]向下取整)-1,则直接将两个子结点合并,直接删除k即可。

当被删除的关键字在终端结点(最低层非叶结点)中时,有下列几种情况:

1)直接删除关键字:若被删除关键字所在结点的关键字个数>【m/2】(向下取整)-1,表明删除该关键字后仍满足B树的定义,则直接删去该关键字。

2)兄弟够借:若被删除关键字所在结点删除前的关键字个数=【m/2】(向下取整)-1,且与此结点相邻的左(右)兄弟结点的关键字个数>=【m/2】(向下取整),需要调整该结点左(右)兄弟结点及其双亲结点(父子换位法),以达到新的平衡。

3)兄弟不够借:若被删除关键字所在结点删除前的关键字个数=【m/2】(向下取整)-1,且此时与该结点相邻的左(右)兄弟结点的关键字个数=【m/2】(向下取整)-1,则将关键字删除后,将左(右)兄弟结点及双亲结点中的关键字合并。

在合并的过程中,双亲结点的关键字个数会减少。若其双亲结点是根结点并且关键字个数减少至0(根结点关键字个数为1时,有两棵子树),则直接将根结点删除,合并后的新结点成为根;若双亲结点不是根结点,且关键字个数减少至【m/2】-2,又要与它自己的兄弟结点进行调整或合并操作,并重复上述步骤,直至符合B树的要求为止。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java系列博客

Iterator在ArrayList中的源码实现

1892
来自专栏机器学习和数学

[算法与数据结构] 《算法导论》堆排序笔记

堆排序的实现是靠叫做“堆”的数据结构来实现的。所以学习堆排序,首先要了解什么是堆 堆 堆是一个数组,每个结点表示数组中的一个元素,堆可以看做是一个近似的完全二叉...

3139
来自专栏俞其荣的博客

HashSet内部原理解析Header源码解析Footer

2855
来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

992
来自专栏余林丰

有关ArrayList常用方法的源码解析

jdk1.7.0_79   我相信几乎所有的同学在大大小小的笔试、面试过程中都会被问及ArrayList与LinkedList之间的异同点。稍有准备的人这些问...

2297
来自专栏desperate633

ArrayList实现原理分析(Java源码剖析)ArrayList使用的存储的数据结构ArrayList的初始化ArrayList是如何动态增长ArrayList如何实现元素的移除ArrayList

ArrayList是我们经常使用的一个数据结构,我们通常把其用作一个可变长度的动态数组使用,大部分时候,可以替代数组的作用,我们不用事先设定ArrayList的...

1413
来自专栏wannshan(javaer,RPC)

关于 java.util.ConcurrentModificationException jdk源码分析

先看怎么发生 List<Integer> list=new ArrayList<>(); for(int i=0;i<10;i++){ list.add...

2993
来自专栏Java后端技术

一道面试题引发的思考

为什么呢?那么我们怎么来发现它背后的秘密呢?答案只有一个:那就是通过源码来解惑(ArrayList部分源码)。

710
来自专栏java小白

ArrayList源码详解

1755
来自专栏nnngu

数据结构07 二叉树

这篇文章开始总结 树和二叉树。 什么是树呢? 1、树的定义 (1)有且仅有一个特定的称为根(root) 的节点。 (2)当 n>1 时,其余节点可分为 m(m>...

3524

扫码关注云+社区

领取腾讯云代金券