热 综合-网站正在建设中,wordpress 新闻资讯,杭州建设网站公司网站,网络舆情监测 toom平衡树结构的树高为 O(logn) #xff0c;平衡树结构包括两种平衡二叉树结构#xff08;分别为 AVL 树和 RBT#xff09;以及一种树结构#xff08;B-Tree#xff0c;又称 B 树#xff0c;它的度大于 2 #xff09;。AVL 树和 RBT 适合内部存储的应用#xff0c;而 B 树… 平衡树结构的树高为 O(logn) 平衡树结构包括两种平衡二叉树结构分别为 AVL 树和 RBT以及一种树结构B-Tree又称 B 树它的度大于 2 。AVL 树和 RBT 适合内部存储的应用而 B 树适合外部存储的应用。对于 B 树应掌握其查找、插入以及删除的操作过程对于 B 树一种 B 树的变形树 需了解其基本概念和性质。 一、了解m叉搜索树
1. m叉搜索树的定义
m 叉搜索树m-way search tree可以是一棵空树。如果非空它必须满足以下特征
1在相应的扩充搜索树中即用外部结点替换空指针之后所得到的搜索树每个内部结点最多可以有 m 个孩子以及 1 ~ m - 1 个元素外部结点指不含元素和孩子的结点。
2每一个含有 p 个元素的结点都有 p 1 个孩子。
3对任意一个含有 p 个元素的结点设 k1 , … , kp 分别是这些元素的关键字。这些元素按顺序排列即 k1 k2 … kp 。设 c0 , c1 , … , cp 是该结点的 p 1 个孩子。在以 c0 为根的子树中元素的关键字小于 k1 在以 cp 为根的子树中元素的关键字大于 kp 在以 ci 为根的子树中元素的关键字大于 ki而小于 ki1其中 1 i p。
下图是一棵七叉搜索树其中黑色方块代表外部结点其他都是内部结点。 根结点包含 2 个元素关键字是 10 和 80 ) 以及 3 个孩子中间的孩子有 6 个元素和 7 个孩子这 7 个孩子中有 6 个孩子是外部结点。 2. m叉搜索树的搜索
1在上图的七叉搜索树中要查找关键字为 31 的元素先从根结点开始。 2由于 31 位于 10 和 80 之间因此沿中间的指针第二棵子树往下找。根据定义在第一棵子树中所有元素的关键字 10在第三棵子树中所有元素的关键字80 3搜索中间子树的根。因为 31 位于 30 和 40 之间所以要移动到该结点的第三棵子树中。 4此时 31 32因此要继续移动到该结点的第一棵子树中。 5这时的移动搜索到达了外部结点。由此得知在搜索树中不包含关键字为 31 的元素。
3. m叉搜索树的插入
1如果要插入关键字为 31 的元素 I、先按上述步骤查找该元素然后在结点 [32, 36] 处查找失败。 II、由于该结点最多可以容纳 6 个元素根据定义七叉树搜索树的每个结点最多可以容纳 6 个元素所以新元素被插入该结点的第一个位置。
2如果要插入关键字为 65 的元素 I、先按上述步骤查找该元素然后在结点 [20, 30, 40, 50, 60, 70] 处查找失败。 II、因为该结点已满所以必须生成一个新的结点来容纳该元素而且要成为结点 [20, 30, 40, 50, 60, 70] 的第六个孩子。
4. m叉搜索树的删除
1如果要删除关键字为 20 的元素 I、先按上述步骤查找该元素它位于根结点的中间孩子中且是中间孩子的第一个元素。 II、因为该元素没有与之相邻的非空子树所以该元素可以直接从结点中删除。这时的结点变为 [30, 40, 50, 60, 70]。
2如果要删除关键字为 84 的元素 I、类似的首先确定该元素的位置它是根结点的第三个孩子中的第二个元素。 II、因为该元素没有与之相邻的非空子树所以该元素可以直接从结点中删除这时的结点变为 [82, 86, 88]。
3如果要删除关键字为 5 的元素 删除关键字为 5 的元素要复杂一点因为该元素不仅是结点中唯一的一个元素而且与它相邻的孩子有 1 个是非空的位于该元素的左侧。这时需要用左侧相邻的非空子树中关键字最大的元素即关键字为 4 的元素来替换被删除的元素。
4如果要删除关键字为 10 的元素 要在根结点中删除关键字为 10 的元素 既可以用左侧相邻的非空子树中关键字最大的元素来替换也可以用右侧相邻的非空子树中关键字最小的元素来替换。如果用左侧相邻的非空子树中关键字最大的元素进行替换那么将关键字为 5 的元素移上来之后还要继续做一次替换即用关键字为 4 的元素占据原来 5 的位置即上述情况 3。
5. m叉搜索树的高
一棵高度为 h 的 m 叉搜索树不含外部结点 最少有 h 个元素每层一个结点每个结点包含一个元素最多有 mh - 1 个元素除根结点外每层 m 个结点每个结点包含 m - 1 个元素。因为在高度为 h 的 m 叉搜索树中元素个数在 h 到 mh - 1 之间所以一棵 n 元素的 m 叉搜索树的高度在 logm(n 1) 到 n 之间。 当搜索树储存在磁盘上时搜索、插入和删除的时间取决于磁盘的访问次数假设每一个结点的大小不大于一个磁盘块。当 h 是树的高度时这个次数为 O(h)因此要减少磁盘访问次数就要确保树的高度接近于 logm(n 1) 为此就要利用 m 叉平衡搜索树。 二、平衡搜索树——B树及其基本操作 所谓 m 阶 B 树是所有结点的平衡因子均等于 0 的 m 路平衡查找树。B 树的英文是 B - Tree因此 B 树也可写成 B - 树需要注意的是这里的“-”是连接词而非减号。 1. B树的定义
m 阶 B 树B - Tree of order m是一棵 m 叉搜索树。如果 B 树非空那么相应的扩展树满足下列特征
1若根结点不是叶结点则根结点至少有 2 个孩子。 2除根结点以外所有内部结点至少有 ⌈m / 2⌉ 个孩子即至少含有 ⌈m / 2⌉ - 1 个关键字。 3树中每个结点至多有 m 棵子树即至多含有 m - 1 个关键字。 4所有外部结点在同一层。
所有非叶结点的结构如下图所示 介绍 m 叉搜索树时用于举例的那颗七叉搜索树不是一棵七阶 B 树因为它的外部结点不在同一层同时它的非根内部结点 [5] 和 [32, 36] 分别有 2 个孩子和 3 个孩子而七阶的 B 树的非根内部结点应该至少有 ⌈7 / 2⌉ 4 个孩子。
下图所示的七叉搜索树就是是七阶 B 树因为它的外部结点均在第 3 层根结点有 3 个孩子且其余内部结点至少有 4 个孩子。 2. 二~五阶B树
1二阶 B 树
在二阶 B 树中每个内部结点都不会有 2 个以上的孩子而每个内部结点又至少有 2 个孩子因此二阶 B 树的所有内部结点都恰好有 2 个孩子。又因为所有外部结点都处于同一层上所以二阶 B 树是满二叉树。因此对某个树高为 h 的二阶 B 树仅当其元素个数为 2h - 1 时该树才存在。
2三阶 B 树与四阶 B 树
① 一棵三阶 B 树因为其内部结点必须有 2 个孩子或 3 个孩子所以也称 2 - 3 树 ② 一棵四阶 B 树因为其内部结点必须有 2 个、3 个或 4 个孩子所以也称 2 - 3 - 4 树或简称2, 4 树。
下图是一棵 2 - 3 树。不过如果把关键字为 14 和 16 的元素加入 20 的左孩子中这棵树就成为 2 - 3 - 4 树了。 3五阶 B 树
下图是一颗 5 阶 B 树对它进行分析 ① 结点的孩子个数等于该结点中关键字个数加 1 。
② 如果根结点没有关键字就没有子树此时 B 树为空如果根结点有关键字则其子树个数必然大于或者等于 2因为子树个数等于关键字个数加 1 。
③ 除根结点外的所有非叶结点至少有 ⌈m / 2⌉ ⌈5 / 2⌉ 3 棵子树即至少有 ⌈m / 2⌉ - 1 ⌈5 / 2⌉ - 1 2 个关键字至多有 5 棵子树即至多有 4 个关键字。
④ 结点中的关键字从左到右递增有序关键字两侧均有指向子树的指针左侧指针所指子树的所有关键字均小于该关键字右侧指针所指子树的所有关键字均大于该关键字。或者看成下层结点的关键字总是落在由上层结点的关键字所划分的区间内。如第二层最左结点的关键字划分成了 3 个区间(-∞, 5), (5, 11), (11, ∞) 该结点中的 3 个指针所指子树的关键字均分别落在这 3 个区间内。
⑤ 所有叶结点均在第 4 层代表查找失败的位置。
3. B树的高度磁盘存取次数 B 树中的大部分操作所需的磁盘存取次数与 B 树的高度成正比。 下面来分析 B 树在不同情况下的高度。当然首先应该明确 B 树的高度不包括最后的不带任何信息的叶结点所处的那一层。 若 n 1则对任意一棵包含 n 个关键字、高度为 h 、阶数为 m 的 B 树
1若让每个结点中的关键字个数达到最多则容纳同样多关键字的 B 树的高度达到最小。 因为 B 树中每个结点最多有 m 棵子树m - 1 个关键字所以在一棵高度为 h 的 m 阶 B 树中关键字的个数应满足 n (m - 1) × (1 m m2 … mh-1) mh - 1因此有 h logm(n 1) 。
2若让每个结点中的关键字个数达到最少则容纳同样多关键字的 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 。
推出logm(n 1) h log⌈m/2⌉((n 1) / 2) 1
例如假设一棵 3 阶 B 树共有 8 个关键字则其高度范围为 2 h 3.17h 取整数。
4. B树的查找 B 树的搜索算法与 m 叉搜索树的搜索算法相同。在搜索过程中从根至外部结点路径上的所有内部结点都有可能被搜索到因此磁盘访问次数最多为 h其中h 是 B 树的高度。 在 B 树上进行查找与二叉查找树很相似只是每个结点都是多个关键字的有序表在每个结点上所做的不是两路分支决定而是根据该结点的子树所做的多路分支决定。
B 树的查找包含 两个基本操作 1在B 树中找结点2在结点内找关键字。
由于 B 树常存储在磁盘上因此前一个查找操作是在磁盘上进行的而后一个查找操作是在内存中进行的即在找到目标结点后先将结点信息读入内存然后在结点内采用顺序查找法或折半查找法。因此在磁盘上进行查找的次数即目标结点在 B 树上的层次数决定了 B 树的查找效率。
在 B 树上查找到某个结点后先在有序表中进行查找若找到则查找成功否则按照对应的指针信息到所指的子树中去查找。查找到叶结点时对应指针为空则说明树中没有对应的关键字查找失败。
5. B树的插入 要在 B 树中插入一个新元素首先要在 B 树中搜索关键字与之相同的元素。如果存在这样的元素那么插入失败因为在 B 树的元素中不允许有重复的关键字。如果不存在这样的元素便可以将元索插入在搜索路径中所遇到的最后一个内部结点中。 与二叉查找树的插入操作相比B 树的插入操作要复杂得多。在 B 树中查找到插入的位置后并不能简单地将其添加到终端结点最底层的非叶结点中因为此时可能会导致整棵树不再满足 B 树定义中的要求。将关键字 key 插入 B 树的过程如下
1定位
利用上述 B 树的查找算法找出插入该关键字的最底层中的某个非叶结点。 在 B 树中查找 key 时 会找到表示查找失败的叶结点这样就确定了最底层非叶结点的插入位置。注意插入位置一定是最底层中的某个非叶结点。
2插入
在 B 树中每个非失败结点的关键字个数都在区间 [⌈m / 2⌉ - 1 , m - 1] 内。若结点插入后的关键字个数小于 m则可以直接插入若结点插入后的关键字个数大于等于 m则必须对结点进行分裂操作。
分裂的方法是取一个新结点在插入 key 后的原结点从中间位置⌈m / 2⌉将其中的关键字分为两部分左部分包含的关键字放在原结点中右部分包含的关键字放到新结点中中间位置⌈m / 2⌉的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限则继续进行这种分裂操作直至这个过程传到根结点为止进而导致 B 树高度增 1 。
示例 ① 示例 ②
对于 m 7 的 B 树所有结点中最多能有 6 个关键字。若某结点中已存在 6 个关键字则该结点已满。 a插入元素 3 得到
对根结点有 1 次磁盘读操作对根结点的第一个孩子结点有 1 次磁盘读操作、 1 次磁盘写操作。因此磁盘访问次数一共是 3 次。 b进一步插入元素 25 得到【当在一个饱和结点中插入一个新元素时需要分裂该结点。】
对根结点有 1 次磁盘读操作对根结点的中间孩子结点有 1 次磁盘读操作然后需要将分开的两个结点和修改后的根结点写回磁盘。因此磁盘访问次数一共是 5 次。 示例 ③
对于 m 3 的 B 树所有结点中最多能有 2 个关键字。若某结点中已存在 2 个关键字则该结点已满。 插入元素 44 得到
读取结点 [30, 80]、[50, 60] 和 [35, 40] 需要访问 3 次磁盘有 3 个结点被分裂所以执行了 6 次磁盘写操作每次结点分裂之后要将修改的结点和新结点写回磁盘因此需要访问两次磁盘最后产生一个新的根结点并写回磁盘又需要访问 1 次磁盘。因此磁盘访问次数一共是 10 次。 当插入操作引起了 s 个结点分裂时磁盘访问的次数为 h读取搜索路径上的结点 2 × s 回写分裂出的两个新结点 1回写新的根结点或插入后没有导致分裂的结点。 因此所需要的磁盘访问次数是 h 2 × s 1 最多可达到 3 × h 1 。 6. B树的删除 删除一个元素分为两种情况① 该元素位于叶结点 即该结点的所有孩子都是外部结点② 该元素位于非叶结点。 B 树中的删除操作与插入操作类似但要稍微复杂一些即要使得删除后的结点中的关键字个数 ⌈m / 2⌉ - 1因此将涉及结点的“合并”问题。
当被删关键字 k 不在终端结点最底层的非叶结点中时可以用 k 的前驱或后继 k’ 即 k 的左侧子树中“最右下”的元素 或 右侧子树中“最左下”的元素来替代 k然后在相应的结点中删除 k’关键字 k’ 必定落在某个终端结点中则转换成了被删关键字在终端结点中的情形。
示例在下图的 4 阶 B 树中删除关键字 80用其前驱 78 替代然后在终端结点中删除 78。 因此 只需讨论被删关键字在终端结点 中的情形有下列三种情况
1直接删除关键字
若被删关键字所在结点删除前的关键字个数 ⌈m / 2⌉表明删除该关键字后仍满足 B 树的定义则直接删去该关键字。
此时在沿搜索路径从根结点到叶结点的过程中需要 h 次磁盘访问将修改后的叶结点写回磁盘还需要一次额外的磁盘访问。因此磁盘访问次数一共是 h 1 次。
2兄弟够借
若被删关键字所在结点删除前的关键字个数 ⌈m / 2⌉ - 1且与该结点相邻的右或左兄弟结点的关键字个数 ⌈m / 2⌉则需要调整该结点、右 或左兄弟结点及其双亲结点父子换位法以达到新的平衡。 【注意除了根结点以外每个结点都会有一个最邻近的左兄弟或一个最邻近的右兄弟或二者都有。为了降低在最坏情况下的磁盘访问次数在删除一个元素后的结点缺少一个元素时我们只考察它的一个最邻近的兄弟。】
示例 ①
在下图的 4 阶 B 树中删除关键字 65右兄弟关键字个数 ⌈m / 2⌉ 2将 71 取代原 65 的位置将 74 调整到 71 的位置。 示例 ②
对于 m 7 的 B 树所有结点中最多能有 6 个关键字最少要有 3 个关键字。 删除元素 25 得到6 上去10 下来。
删除后得到的结点是 [20, 30] 元素个数为 2 。但七阶 B 树的非根结点至少要有 3 个元素。它最邻近的左兄弟 [2, 3, 4, 6] 可以提供一个额外的元素因此可把该结点的最大元素移至其父结点然后把关键字为10 的元素移下来结果下图所示。 磁盘访问次数为2读根结点和 25 所在的叶结点 1读取该叶结点的最邻近的左兄弟 3写回修改后的叶结点、左兄弟结点以及父结点 6 。 3兄弟不够借
若被删关键字所在结点删除前的关键字个数 ⌈m / 2⌉ - 1且此时与该结点相邻的左、右兄弟结点的关键字个数均 ⌈m / 2⌉ - 1则将关键字删除后与左或右 兄弟结点及双亲结点中的关键字进行合并将两个兄弟与父结点中介于两个兄弟之间的元素合并成一个新结点。
由于被删关键字所在结点与其相邻的左或右兄弟结点分别有有 ⌈m / 2⌉ - 2 和 ⌈m / 2⌉ - 1 个元素因此合并后的结点共有 (⌈m / 2⌉ - 2) (⌈m / 2⌉ - 1) 1 2 × ⌈m / 2⌉ - 2 个元素。当 m 是奇数时2 × ⌈m / 2⌉ - 2 m - 1而当 m 是偶数时2 × ⌈m / 2⌉ - 2 m - 2 。可以得出结点有足够的空间来容纳这么多元素。
示例 ①
在下图的 4 阶 B 树中删除关键字 5它及其右兄弟结点的关键字个数 ⌈m / 2⌉ - 1 1所以在 5 删除后将 60 合并到 65 结点中。 示例 ②
对于 m 3 的 B 树所有结点中最多能有 2 个关键字最少要有 1 个关键字。 删除元素 10 得到
删除元素 10 后得到的结点不含任何元素。它的最相邻右兄弟 [25] 没有额外的元素因此删除元素结点、右兄弟结点 [25] 及父结点 [20] 的元素被合并到一个结点结果如下图 (I) 所示。
I、树叶层合并 现在第二层有一个结点缺少一个元素它的最邻近的右兄弟 [50, 60] 有一个额外的元素。因此把该兄弟中最左边的元素关键字为 50 的元素移到父结点中并将父结点中关键字为 30 的元素移下来结果下图 (II) 所示。注意结点 [50, 60] 的左子树也要移动。
II、第二层合并 到达被删除元素所在的叶结点需要 3 次读访问取得第二层和叶结点层的最邻近右兄弟结点需要 2 次读访问将第一、二和三层的 4 个修改后的结点写回磁盘需要 4 次写访问。因此总的磁盘访问次数是 3 2 4 9 次。
示例 ③
对于 m 3 的 B 树所有结点中最多能有 2 个关键字最少要有 1 个关键字。 删除元素 44 得到树的高度减少了一层。
找到被删除元素所在的叶结点需要 4 次磁盘访问最邻近的兄弟需要 3 次读取磁盘和 3 次写磁盘。因此总的访问磁盘次数是 10 次。 【总结】
在合并过程中 双亲结点中的关键字个数会减 1 。 I、若其双亲结点是根结点且关键字个数减少至 0根结点关键字个数为 1 时有 2 棵子树则直接将根结点删除合并后的新结点成为根树的高度减 1 II、若双亲结点不是根结点 且关键字个数减少到 ⌈m / 2⌉ - 2则需要选择与双亲结点最邻近的一个兄弟结点要么从中取一个元素要么与它合并。 a如果从最邻近的左右兄弟中取一个元素那么此兄弟结点的最右最左子树也将被读取。 b如果进行合并那么祖父结点的关键字个数也可能因此减少到 ⌈m / 2⌉ - 2导致祖父结点也需要重复上述相同的过程。 最坏情况下这种过程会一直回溯到根结点需要重复上述步骤直至符合 B 树的要求为止。 对高度为 h 的 B 树实施删除操作最坏情况是合并操作发生在 h, h-1, … , 3 层进行合并从最邻近的兄弟中获取一个元素的操作发生在第 2 层。在最坏情况下磁盘访问次数是 3 × h。 【找到被删除元素所在的结点需要 h 次读访问得到第 2 至 h 层的最邻近兄弟需要 h - 1 次读访问第 3 至 n 层的合并需要 h - 2 次写访问对修改过的根结点和第 2 层的 2个结点进行 3 次写访问】 7. 有关B树的历年统考真题
① 【2009 统考真题】下列叙述中不符合 m 阶 B 树定义要求的是 A。 A. 根结点至多有 m 棵子树 B. 所有叶结点都在同一层上 C. 各结点内关键宇均升序或降序排列 D. 叶结点之间通过指针链接
② 【2012 统考真题】已知一棵 3 阶 B 树如下图所示。删除关键字 78 得到一棵新 B 树其最右叶结点中的关键字是 D 。 A. 60 B. 60, 62 C. 62, 65 D. 65
③ 【2013 统考真题】在一棵高度为 2 的 5 阶 B 树中所含关键字的个数至少是 A 。 A. 5 B. 7 C. 8 D. 14
④ 【2014 统考真题】在一棵有 15 个关键字的 4 阶 B 树中含关键字的结点个数最多是 D 。 A. 5 B. 6 C. 10 D. 15
⑤ 【2018 统考真题】高度为 5 的 3 阶 B 树含有的关键字个数至少是 B 。 A. 15 B. 31 C. 62 D. 242
⑥【2020 统考真题】依次将关键字 5, 6, 9, 13, 8, 2, 12, 15 插入初始为空的 4 阶 B 树后根结点中包含的关键字是 B 。 A. 8 B. 6, 9 C. 8, 13 D. 9, 12
⑦ 【2021 统考真题】在一棵高度为 3 的 3 阶 B 树中根为第 1 层若第 2 层中有 4 个关键字则该树的结点数最多是 A 。 A. 11 B. 10 C. 9 D. 8
⑧ 【2022 统考真题】在下图所示的 5 阶 B 树 T 中删除关键字 260 之后需要进行必要的调整得到新的 B 树 T1 。下列选项中不可能是 T1 根结点中关键字序列的是 D 。 A. 60, 90, 280 B. 60, 90, 350 C. 60, 85, 110, 350 D. 60, 90, 110, 350
⑨ 【2023 统考真题】下列关于非空 B 树的叙述中正确的是 B 。 I、插入操作可能增加树的高度 II、删除操作一定会导致叶结点的变化 III、查找某关键字总是要查找到叶结点 IV、插入的新关键字最终位于叶结点中 A. 仅 I B. 仅 I、II C. 仅 III、IV D. 仅 I、II、IV
三、B树的变形——B树的基本概念
1. B树的定义
B 树是应数据库所需而出现的一种 B 树的变形树。一棵 m 阶的 B 树需满足下列条件
1每个分支结点最多有 m 棵子树孩子结点。
2非叶根结点至少有 2 棵子树其他每个分支结点至少有 ⌈m / 2⌉ 棵子树。
3结点的子树个数与关键字个数相等。
4所有叶结点包含全部关键字及指向相应记录的指针叶结点中将关键字按大小顺序排列并且相邻叶结点按大小顺序相互链接起来支持顺序查找。
5所有分支结点可视为索引的索引中仅包含它的各个子结点即下一级的索引块中关键字的最大值及指向其子结点的指针。
2. m阶B树与m阶B树的差异
m 阶的 B 树与 m 阶的 B 树的主要差异如下
1在 B 树中具有 n 个关键字的结点只含有 n 棵子树即每个关键字对应一棵子树而在 B 树中具有 n 个关键字的结点含有 n 1 棵子树。
2在 B 树中每个结点 非根内部结点的关键字个数 n 的范围是 ⌈m / 2⌉ n m非叶根结点2 n m而在 B 树中每个结点非根内部结点的关键字个数 n 的范围是 ⌈m / 2⌉ - 1 n m - 1根结点1 n m - 1。
3在 B 树中叶结点包含了全部关键字非叶结点中出现的关键字也会出现在叶结点中而在 B 树中最外层的终端结点包含的关键字和其他结点包含的关键字是不重复的。
4在 B 树中叶结点包含信息所有非叶结点仅起索引作用非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针不含有该关键字对应记录的存储地址。这样能使一个磁盘块存储更多的关键字使得磁盘读 / 写次数更少查找速度更快。
5在 B 树中用一个指针指向关键字最小的叶结点将所有叶结点串成一个线性链表。
下图所示为一棵 4 阶 B 树。可以看出分支结点的某个关键字是其子树中最大关键字的副本。通常在 B 树中有两个头指针一个指向根结点另一个指向关键字最小的叶结点。因此可以对 B 树进行两种查找运算 一种是从最小关键字开始的顺序查找另一种是从根结点开始的多路查找。 B 树的查找、插入和删除操作和 B 树的基本类似。只是在查找过程中非叶结点上的关键字值等于给定值时并不终止而是继续向下查找直到叶结点上的该关键字为止。所以在 B 树中查找时无论查找成功与否每次查找都是一条从根结点到叶结点的路径。 3. 有关B树的历年统考真题
① 【2016 统考真题】B树不同于 B 树的特点之一是 A 。 A. 能支持顺序查找 B. 结点中含有关键字 C. 根结点至少有两个分支 D. 所有叶结点都在同一层上
② (2017 统考真题】下列应用中适合使用 B树的是 B 。 A. 编译器中的词法分析 B. 关系数据库系统中的索引 C. 网络中的路由表快速查找 D. 操作系统的磁盘空闲块管理
