B树及B+树查找
B 树（B-Tree）是一种多路平衡查找树，广泛应用于数据库和文件系统。B+树是 B 树的变种，所有关键字都在叶子节点，适合范围查找。
B树/B+树查找演示
此处可扩展为B树/B+树结构和查找过程的可视化。
- 多路平衡树结构
- 节点分裂与合并
- 范围查找演示
B 树的结构特点
- 每个结点最多有 个子女（为阶数）
- 根结点至少有 2 个子女（除非整棵树只有一个结点）
- 非根结点至少有 个子女
- 结点内关键字递增排列，子树区间有序
B+树的结构特点
- 只有叶子节点存储全部关键字，且链式连接
- 非叶子节点只存索引信息
- 适合区间/范围查找
- 从根结点开始，顺序查找结点内关键字
- 若找到，查找成功
- 若未找到，沿对应子树指针向下递归查找
- 直到叶子结点或查找成功
B+树查找过程类似，但所有查找都到叶子结点
- 从根结点开始，沿查找路径找到应插入的叶子结点
- 在叶子结点中按关键字顺序插入
- 分裂：若插入后结点关键字个数超过 （3 阶 B 树为 2），则将该结点分裂为两个结点，并把中间关键字上移到父结点
- 若父结点也超限，继续向上分裂，直至根结点（树增高一层）
删除关键字后，若结点关键字个数少于 ，需要调整：
- 借位：若兄弟结点关键字富余，向其借一个关键字（经父结点中转）
- 合并：若兄弟结点也不足，则与兄弟结点合并，父结点相应关键字下移
- 若父结点因下移而不足，继续向上调整，根结点若被合并则树高减一
| 对比项 | B 树 | B+ 树 |
|---|---|---|
| 关键字位置 | 分布在所有结点 | 全部集中在叶子结点 |
| 非叶子结点 | 存储关键字和数据 | 只存储索引信息 |
| 叶子结点连接 | 不连接 | 用指针链式连接 |
| 查找 | 命中即止 | 必须到叶子结点 |
| 范围查找 | 中序遍历 | 利用链表顺序扫描，高效 |
| 典型应用 | 一般索引 | 数据库/文件系统范围查询 |
- 适用于大规模数据的磁盘存储、数据库索引
- 需要高效范围查找的场合（B+树）
伪代码如下：
node = root
while node != null:
在node关键字中顺序查找x
if 找到:
return 位置
else:
沿对应子树指针向下
return -1- 查找时间复杂度：，为阶数，为关键字数
- B+树查找效率与 B 树相当，但更适合范围查找
习题 1
B 树和 B+树有何区别？各自适合什么场景？
解题思路：
本题考查 B 树与 B+ 树的结构差异及其适用场景。关键区别在于关键字的存放位置：B 树把关键字分布在所有结点中并可充当路标，而 B+ 树把全部关键字集中在叶子结点。
详细步骤：
- B 树关键字分布在所有结点，B+树只在叶子结点
- B+树叶子结点链式连接，适合范围查找
- 补充：B 树的非叶结点本身携带关键字，可在查找过程中直接判定目标应进入哪个分支，单次点查找路径较短；B+ 树的非叶结点只起路标作用，但全部关键字集中在叶子结点并用链表首尾相连，区间查询只需沿链表顺序扫描即可。
最终答案：
B 树适合一般查找，B+树适合范围查找。
习题 2
一棵 4 阶 B 树，非根结点最少有几个子女？
解题思路：
本题考查 B 树阶数与非根结点最少子女数之间的关系。m 阶 B 树规定：除根结点外的所有非叶结点至少有 个子女，而根结点的子女数另作规定。
详细步骤：
- 非根结点最少 个子女
- ，
- 补充：该下限只适用于非根的非叶结点；根结点另行规定——根不是叶子时至少有两个子女，根是叶子时整棵树只有根一个结点。
最终答案：
最少 2 个子女。
习题 3
下列关于 B 树的说法中，错误的是（ ） (A) 一棵 m 阶 B 树中，每个非根结点至少有个子女 (B) 一棵 m 阶 B 树中，每个结点至多有个子女 (C) 有个关键字的 B 树中，根结点至少有 2 个子女，至多有个子女 (D) 对于一棵最大阶数为、含有个关键字的 B 树，若，则该 B 树的高度为 3
解题思路：
本题考查对 B 树性质的逐项辨析。做法是把四个选项与 B 树的三条基本性质对照：结点子女数的上下界、关键字个数与子女数的关系，以及根结点的特例。
详细步骤：
- (A) 正确，(B) 正确
- (C) 错误，根结点可只有 1 个子女（特殊情况）
- (D) 条件不充分，无法确定高度
- 补充说明：(A)、(B) 是 m 阶 B 树对非根结点和所有结点子女数的标准规定；(C) 中“根结点至少有 2 个子女”只对根不是叶子的情况成立，根可以只有一个子女；至于 (D)，仅由 这一条件无法唯一确定树的高度。
最终答案：
(C) 错误。根结点可只有 1 个子女。