Skip to content

2016年 408 数据结构 第 10 题

数据结构2016年选择题2分

题目

B+ 树不同于 B 树的特点之一是( )。

错因

B

把"关键字"和"卫星数据"混在一起。两者结点中都含有关键字——B 树和 B+ 树的内部结点都靠存关键字来引导分支。区别在于 B 树所有结点都既存关键字也存数据,B+ 树只在叶子存数据、内部结点只存关键字索引;但"是否含有关键字"两者一致,不构成区别。

C

"根结点至少有两个分支"是 B 树和 B+ 树共同的定义条件之一(除空树或仅一棵根的情形外)。这条性质两者都满足,不是区别。可能因为两种树都涉及"分支因子 m"导致考生看到"分支"就以为是 B+ 树独有的性质。

D

"所有叶结点都在同一层上(即树高平衡)"是所有 B 类树(B 树、B+ 树、B* 树)共同的核心性质——这正是它们之所以叫"B 树家族"的原因,多路平衡查找树才是它们的共同身份。这点两者完全一致,不构成区别。

总解析

B 树 vs B+ 树的核心差异(按相关性从高到低):

比较点B 树B+ 树
数据存储位置所有结点都存关键字和卫星数据只有叶子存数据,内部结点只存索引关键字
关键字在树中的副本数每个关键字只存 1 次索引关键字在内部结点和叶子各存 1 次(叶子是真值)
叶子链表所有叶子用指针顺序链接成有序链表
顺序遍历支持必须中序遍历整棵树沿叶子链表顺序扫一遍即可,O(叶子数)
查找路径找到即停(可能在任意层)必须走到叶子层
一个内部结点能容纳的索引数较少(需带卫星数据)较多(只存关键字+指针,更"瘦")

为什么 B+ 树支持顺序查找而 B 树不(直接)支持

B+ 树所有叶子之间有一条横向指针链表,按关键字从小到大串起来。要做"从某关键字开始顺序读 K 个"或"求某区间的所有关键字"这类范围查询,只需:

  1. 从根走一次普通的 B+ 树查找,定位到起始关键字所在的叶子()。
  2. 沿叶子链表向右扫 个叶子,不需要返回根、不需要中序回溯

B 树没有这条叶子链表,只能做中序遍历,效率明显劣化。

B+ 树就是为数据库索引设计的:磁盘 I/O 昂贵,"区间扫描"频繁(如 WHERE id BETWEEN 100 AND 200),叶子链表把 B+ 树打造成既能快速点查、又能高效范围扫的双优结构。这就是 MySQL InnoDB 默认用 B+ 树而不是 B 树的根本原因。

最终答案是 A(能支持顺序查找)

最后更新:

🎬 可视化演示
加载中...

提示:可在可视化区直接操作播放、步进、修改参数