大连网站建设连城传媒,网球排名即时最新排名,上海地产网站建,新片场视频素材目录
B树和B树
考纲内容
1.B树及其基本操作
1.1B树的查找
1.2B树的高度#xff08;磁盘存取次数#xff09;
1.3B树的插入
1.4B树的删除
2.B树的基本概念 B树和B树
考纲内容 考研大纲对 B树和 B树的要求各不相同#xff0c;重点在于考查B树#xff0c;不仅要求理解…目录
B树和B树
考纲内容
1.B树及其基本操作
1.1B树的查找
1.2B树的高度磁盘存取次数
1.3B树的插入
1.4B树的删除
2.B树的基本概念 B树和B树
考纲内容 考研大纲对 B树和 B树的要求各不相同重点在于考查B树不仅要求理解B树的基本特点还要求掌握 B树的建立、插入和删除操作而对 B树则只考查基本概念。 1.B树及其基本操作
所谓m阶B树也可写成“B-树”注意这里的“-”是连接词不能读作“减”。是所有结点的平衡因子均等于0的m路平衡查找树。
【命题追踪 ——B树的定义和特点(2009)】
一棵 m 阶 B树或为空树或为满足如下特性的 m 叉树:
1) 树中每个结点至多有m棵子树即至多有m-1个关键字。
2) 若根结点不是叶结点则至少有2棵子树即至少有1个关键字。
3) 除根结点外的所有非叶结点至少有棵子树即至少有个关键字。
4) 所有非叶结点的结构如下: 其中Ki(i12.….n)为结点的关键字且满足K1K2…Kn
Pi(i01…n)为指向子树根结点的指针且指针 所指子树中所有结点的关键字均小于KiPi所指子树中所有结点的关键字均大于Ki
为结点中关键字的个数。
5) 所有的叶结点大多数教材将B树的叶结点定义为失败结点而408真题中却常将B树的叶结点定义为最底层的终端结点。都出现在同一层次上并且不带信息(可以视为外部结点或类似于折半查找判定树的失败结点实际上这些结点并不存在指向这些结点的指针为空)。
【命题追踪——B 树中关键字数和结点数的分析】
图7.28所示为一棵5阶B树可以借助该实例来分析上述性质: 1结点的孩子个数等于该结点中关键字个数加1。
2若根结点没有关键字就没有子树则此时B树为空
若根结点有关键字则其子树个数必然大于或等于 2因为子树个数等于关键字个数加1。
3除根结点外的所有非叶结点至少有棵子树(即至少有个关键字)至多有5棵子树(即至多有4个关键字)。
4结点中的关键字从左到右递增有序关键字两侧均有指向子树的指针左侧指针所指子树的所有关键字均小于该关键字右侧指针所指子树的所有关键字均大于该关键字。
或者看成下层结点的关键字总是落在由上层结点的关键字所划分的区间内如第二层最左结点的关键字划分成了3个区间:(-∞,5)(5,11)(11,∞)该结点中的3个指针所指子 树的关键字均分别落在这3个区间内。
5所有叶结点均在第4层代表查找失败的位置。
1.1B树的查找
在B树上进行查找与二叉排序树很相似只是每个结点都是多个关键字的有序表在每个结点上所做的不是两路分支决定而是根据该结点的子树所做的多路分支决定。
B树的査找包含两个基本操作
① 在 B树中找结点;
② 在结点内找关键字。
由于B树常存储在磁盘上则前一查找操作是在磁盘上进行的而后一查找操作是在内存中进行的即在磁盘上找到目标结点后先将结点信息读入内存然后再采用顺序查找法或折半查找法。
因此在磁盘上进行查找的次数即目标结点在B树上的层次数决定了B树的查找效率。
在B树上查找到某个结点后先在有序表中进行查找若找到则查找成功否则按照对应的指针信息到所指的子树中去査找
B树查找操作举例
(例如在图 7.28 中查找关键字 42
首先从根结点开始根结点只有一个关键字且 4222若存在必在关键字 22 的右边子树上右孩子结点有两个关键字
而 364245则若存在必在 36 和 45 中间的子树上在该子结点中查到关键字 42查找成功)。
查找到叶结点时(对应指针为空)则说明树中没有对应的关键字查找失败。
1.2B树的高度磁盘存取次数
由上一节得知B树中的大部分操作所需的磁盘存取次数与B树的高度成正比。
下面来分析B树在不同情况下的高度。当然首先应该明确B树的高度不包括最后的不带任何信息的叶结点所处的那一层(有些书对 B树的高度的定义中包含最后的那一层)。
若 n≥1则对任意一棵包含n个关键字、高度为 h、阶数为 m的 B树:
1若让每个结点中的关键字个数达到最多则容纳同样多关键字的 B 树的高度达到最小。
因为 B树中每个结点最多有m棵子树m-1个关键字所以在一棵高度为h的m阶 B树中关键字的个数应满足
因此有
2若让每个结点中的关键字个数达到最少则容纳同样多关键字的 B树的高度达到最大。
第一层至少有1个结点
第二层至少有2个结点
除根结点外的每个非叶结点至少有棵子树则第三层至少有个结点……第 h1层至少有个结点注意到第h1层是不包含任何信息的叶结点。
对于关键字个数为n的B树叶结点即查找不成功的结点为n1由此有即 。
例如假设一棵3阶 B树共有8个关键字则其高度范围为2h3.17取整数。
1.3B树的插入
【命题追踪——通过插入操作构造一棵初始为空的 B树】
与二叉排序树的插入操作相比B树的插入操作要复杂得多。在B树中查找到插入的位置后并不能简单地将其添加到终端结点(最底层的非叶结点)中因为此时可能会导致整棵树不再满足 B树定义中的要求。
将关键字 key 插入 B树的过程如下:
1) 定位。
利用前述的 B树查找算法找出插入该关键字的终端结点(在B树中查找 key 时会找到表示查找失败的叶结点因此插入位置一定是最底层的非叶结点)。
2) 插入。
每个非根结点的关键字个数都在。
若结点插入后的关键字个数小于 m可以直接插入
若结点插入后的关键字个数大于m-1必须对结点进行分裂。
分裂的方法是
取一个新结点在插入 key后的原结点
从中间位置将其中的关键字分为两部分
左部分包含的关键字放在原结点中
右部分包含的关键字放到新结点中
中间位置的结点插入原结点的父结点。
若此时导致其父结点的关键字个数也超过了上限则继续进行这种分裂操作直至这个过程传到根结点为止进而导致B树高度增1。
对于m3的B树所有结点中最多有m-12个关键字若某结点中已有两个关键字则结点已满,如图 7.29(a)所示。
插入一个关键字 60 后,结点内的关键字个数超过了 m-1,如图 7.29(b)所示此时必须进行结点分裂分裂的结果如图 7.29(c)所示。 1.4B树的删除
B树的删除操作与插入操作类似但要稍微复杂一些即要使得删除后的结点中的关键字个数因此将涉及结点的“合并”问题。
【命题追踪——B 树的删除操作的实例2012,2022】
当被删关键字k不在终端结点中时可以用k的前驱(或后继)k
即k的左侧子树中“最右下”的元素(或右侧子树中“最左下”的元素)来替代k
然后在相应的结点中删除k关键字k必定落在某个终端结点中则转换成了被删关键字在终端结点中的情形。
在图7.30的4阶B树中删除关键字 80用其前驱 78 替代然后在终端结点中删除 78。 因此只需讨论被删关键字在终端结点中的情形有下列三种情况:
1直接删除关键字。
若被删关键字所在结点删除前的关键字个数表明删除该关键字后仍满足B树的定义则直接删去该关键字。
2兄弟够借。
若被删关键字所在结点删除前的关键字个数且与该结点相邻的右(或左)兄弟结点的关键字个数则需要调整该结点、右(或左)兄弟结点及其双 亲结点(父子换位法)以达到新的平衡。
在图 7.31(a)中删除 4阶 B树的关键字 65右兄弟关键字个数将 71 取代原 65 的位置将 74 调整到 71 的位置。 3兄弟不够借。
若被删关键字所在结点删除前的关键字个数且此时与该结点相邻的左、右兄弟结点的关键字个数都则将关键字删除后与左(或右)兄弟结 点及双亲结点中的关键字进行合并。
在图 7.31(b)中删除4阶 B树的关键字 5它及其右兄弟结点的关键字个数所以在5删除后将 60 合并到 65 结点中。
【命题追踪——非空B树的查找、插入、删除操作的特点】
在合并过程中双亲结点中的关键字个数会减1。
若其双亲结点是根结点且关键字个数减少至 0(根结点关键字个数为1时有2棵子树)则直接将根结点删除合并后的新结点成为根
若双亲结点不是根结点且关键字个数减少到则又要与它自己的兄弟结点进行调整或合并操作并重复上述步骤直至符合B树的要求为止。
2.B树的基本概念
【命题追踪——B树的应用场合(2017)】
B树是应数据库所需而出现的一种B树的变形树。
一棵 m 阶 B树应满足下列条件:
1每个分支结点最多有m棵子树(孩子结点)。
2非叶根结点至少有两棵子树其他每个分支结点至少有棵子树。
3结点的子树个数与关键字个数相等。
4所有叶结点包含全部关键字及指向相应记录的指针叶结点中将关键字按大小顺序排列,并且相邻叶结点按大小顺序相互链接起来(支持顺序查找)。
5所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。
【命题追踪——B 树和 B树的差异的分析(2016)】
m阶B树与m阶B树的主要差异如下:
1在 B树中具有n个关键字的结点只含有n棵子树即每个关键字对应一棵子树
而在B树中具有n个关键字的结点含有n1棵子树。
2在 B树中每个结点(非根内部结点)的关键字个数n的范围是(非叶根结点:2≤n≤m)
而在B树中,每个结点(非根内部结点)的关键字个数n的范围是(根结点:1≤n≤m-1)。
3在 B树中叶结点包含了全部关键字非叶结点中出现的关键字也会出现在叶结点中
而在B树中最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
4在 B树中叶结点包含信息所有非叶结点仅起索引作用非叶结点的每个索引项只含有对应子树的最大关键字和指向该子树的指针不含有对应记录的存储地址。
这样能使一个磁盘块存储更多的关键字使得磁盘读/写次数更少查找速度更快。
5在 B树中用一个指针指向关键字最小的叶结点将所有叶结点串成一个线性链表。
图 7.32 所示为一棵4阶 B树。可以看出分支结点的关键字是其子树中最大关键字的副本。
通常在 B树中有两个头指针一个指向根结点另一个指向关键字最小的叶结点。
因此可以对 B树进行两种查找运算
一种是从最小关键字开始的顺序查找另一种是从根结点开始的多路查找。 B树的查找、插入和删除操作和 B树的基本类似。
只是在查找过程中非叶结点上的关键字值等于给定值时并不终止而是继续向下查找直到叶结点上的该关键字为止。
所以在B树中查找时无论查找成功与否每次查找都是一条从根结点到叶结点的路径。
