Appearance
题目
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 个"或"求某区间的所有关键字"这类范围查询,只需:
- 从根走一次普通的 B+ 树查找,定位到起始关键字所在的叶子()。
- 沿叶子链表向右扫 个叶子,不需要返回根、不需要中序回溯。
B 树没有这条叶子链表,只能做中序遍历,效率明显劣化。
B+ 树就是为数据库索引设计的:磁盘 I/O 昂贵,"区间扫描"频繁(如
WHERE id BETWEEN 100 AND 200),叶子链表把 B+ 树打造成既能快速点查、又能高效范围扫的双优结构。这就是 MySQL InnoDB 默认用 B+ 树而不是 B 树的根本原因。
最终答案是 A(能支持顺序查找)。