B树及B+树查找

定义与结构

B 树（B-Tree）是一种多路平衡查找树，广泛应用于数据库和文件系统。B+树是 B 树的变种，所有关键字都在叶子节点，适合范围查找。

B树/B+树查找演示

此处可扩展为B树/B+树结构和查找过程的可视化。

• 多路平衡树结构
• 节点分裂与合并
• 范围查找演示

B 树的结构特点

• 每个结点最多有 $m$ 个子女（$m$为阶数）
• 根结点至少有 2 个子女（除非整棵树只有一个结点）
• 非根结点至少有 $\lceil m/2 \rceil$ 个子女
• 结点内关键字递增排列，子树区间有序

B+树的结构特点

• 只有叶子节点存储全部关键字，且链式连接
• 非叶子节点只存索引信息
• 适合区间/范围查找

查找过程

1. 从根结点开始，顺序查找结点内关键字
2. 若找到，查找成功
3. 若未找到，沿对应子树指针向下递归查找
4. 直到叶子结点或查找成功

B+树查找过程类似，但所有查找都到叶子结点

适用场景

• 适用于大规模数据的磁盘存储、数据库索引
• 需要高效范围查找的场合（B+树）

算法描述

伪代码如下：

node = root
while node != null:
    在node关键字中顺序查找x
    if 找到:
        return 位置
    else:
        沿对应子树指针向下
return -1

时间复杂度分析

• 查找时间复杂度：$O(\log_m n)$，$m$为阶数，$n$为关键字数
• B+树查找效率与 B 树相当，但更适合范围查找

练习题

练习 1

B 树和 B+树有何区别？各自适合什么场景？

参考答案

解题思路：比较结构和应用。

详细步骤：

1. B 树关键字分布在所有结点，B+树只在叶子结点
2. B+树叶子结点链式连接，适合范围查找

答案：B 树适合一般查找，B+树适合范围查找。

练习 2

一棵 4 阶 B 树，非根结点最少有几个子女？

参考答案

解题思路：考查 B 树阶数与子女数关系。

详细步骤：

1. 非根结点最少 $\lceil m/2 \rceil$ 个子女
2. $m=4$，$\lceil 4/2 \rceil=2$

答案：最少 2 个子女。

考研真题

真题 1

【2019·408】下列关于 B 树的说法中，错误的是（ ） (A) 一棵 m 阶 B 树中，每个非根结点至少有$\lceil m/2 \rceil$个子女 (B) 一棵 m 阶 B 树中，每个结点至多有$m$个子女 (C) 有$n$个关键字的 B 树中，根结点至少有 2 个子女，至多有$n$个子女 (D) 对于一棵最大阶数为$m$、含有$n$个关键字的 B 树，若$m=\lceil n/2 \rceil$，则该 B 树的高度为 3

参考答案

解题思路：逐项分析 B 树性质。

详细步骤：

1. (A) 正确，(B) 正确
2. (C) 错误，根结点可只有 1 个子女（特殊情况）
3. (D) 条件不充分，无法确定高度

答案：(C) 错误。根结点可只有 1 个子女。