408考研逐题详解：2009年第8题

2009年第8题

下列叙述中，不符合 m 阶 B 树定义要求的是（ ）
A. 根结点最多有 m 棵子树
B. 所有叶结点都在同一层上
C. 各结点内关键字均升序或降序排列
D. 叶结点之间通过指针链接

详解

本题考查了 B 树和 B+树的基础知识。

首先看有关 B 树的基本概念：

• 一棵 $m$ 阶的 B-树（即结点中孩子的最大数量是 $m$），或为空树，或为满足下列特性的 $m$ 叉树：
  • 树中每个结点至多有 m 棵子树；
  • 若根结点不是叶子结点，则至少有两棵子树；
  • 除根之外的所有非终端结点至少有 $\lceil m/2\rceil$ 棵子树；
  • 所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点 （失败结点并不存在，指向这些结点的指针为空。引入失败结点是为了便于分析 B-树的查找性能）；
  • 所有的非终端结点最多有 $m-1$ 个关键字，结点的结构如图所示。其中：
    • $K_i(i=1,\cdots ,n)$ 为关键字，且 $K_i<K_{i+1}(i=1,\cdots ,n-1)$ ；
    • $P_i(i=0,\cdots ,n)$ 为指向子树根结点的指针，且指针 $P_{i-1}$ 所指子树中所有结点的关键字均小于 $K_i$ ，$P_n$ 所指子树中的所有结点的关键字均大于 $K_n$ ，$n(\lceil m/2\rceil -1\le n\le m-1)$ 为关键字的个数（或 $n+1$ 为子树的个数）

根据以上内容，可以判断，题目中的 A/B/C 选项的叙述都是符合 m 阶 B 树定义的。

再看关于 B+树的基本知识：

一棵 $m$ 阶 B+树满足下列条件：

• 每个分支结点最多有 $m$ 棵子树。
• 根结点或者没有子树，或者最少有两棵子树。
• 除根结点以外，其他每个分支结点最少有 $\lceil m/2\rceil$ 棵子树。
• 有 $n$ 棵子树的结点有 $n$ 个关键字。
• 所有叶子结点（不是外部结点）包含全部关键字及指向相应记录的指针，而且叶子结点按关键字大小顺序链接（可 以 把每个叶子结点看成是一个基本索引块，它的指针不再指向另一级索引块，而是直接指向数据文件中的记录）。
• 所有分支结点（可看成是索引的索引）中仅包含它的各个子结点（即下级索引的索引块）中的最大关键字及指向子结点的指针。

很显然，B+树的叶结点之间通过指针链接。所以题目中的选项 D 不符合 B 树定义，这是 B+树的特点。

本题答案：D