B 树

为磁盘 I/O 设计的查找结构

折半查找和 BST/AVL 都是内存中的查找结构，但数据库索引动辄存储百万条记录，不可能全放内存。B 树是专为磁盘访问设计的多路平衡查找树——每个结点存储多个关键字，一次磁盘 I/O 读一个结点，大幅减少磁盘访问次数。

例如一棵 1001 阶 B 树，存储 10 亿个关键字只需要 3 层，最多 3 次磁盘访问即可完成查找。408 考研中，B 树的插入分裂、删除合并是高频综合题。

核心思想

B 树是m 阶多路平衡查找树的典型代表。核心特点：

• 多路分支：每个节点最多有 m 棵子树、m-1 个关键字，一次磁盘 I/O 读入一个节点后可以进行多次比较
• 平衡：所有叶节点都在同一层，保证最坏情况下查找路径长度一致
• 节点半满约束：除根节点外，每个节点至少有 ⌈m/2⌉ 棵子树，保证空间利用率

B 树节点的结构示意：

┌──┬────┬──┬────┬──┬─ ... ─┬──────┬──┐
│P₀│ K₁ │P₁│ K₂ │P₂│       │Kₙ    │Pₙ│
└──┴────┴──┴────┴──┴─ ... ─┴──────┴──┘

其中 Kᵢ 为关键字（K₁ < K₂ < ... < Kₙ），Pᵢ 为指向子树的指针。子树 Pᵢ 中所有关键字的值在 Kᵢ 和 Kᵢ₊₁ 之间。

交互可视化

通过下方的交互动画，你可以逐步观察B 树的执行过程：

加载可视化中...

操作详解

B 树的性质

一棵 m 阶 B 树满足以下性质：

性质	描述
每个节点最多 m 棵子树	即最多 m-1 个关键字
根节点子树数	至少 2 棵（若非叶节点）；关键字至少 1 个
非根非叶节点子树数	至少 ⌈m/2⌉ 棵，即关键字至少 ⌈m/2⌉-1 个
所有叶节点在同一层	叶节点是查找失败到达的空指针，不含任何信息
节点内关键字有序	K₁ < K₂ < ... < Kₙ，节点内可用顺序/折半查找

易错：B 树中"叶结点"的含义与其他树不同——B 树的叶结点指的是最底层的外部空结点（查找失败到达的 NULL 指针），不含任何信息。而最底层有关键字的结点叫做"终端结点"。408 选择题"B 树的所有叶结点在同一层"说的就是这些 NULL 空结点都在同一层。终端结点在叶结点的上面一层。

B 树节点的 C 语言定义：

#define M 5  // 5 阶 B 树

typedef struct BTNode {
    int keyNum;             // 当前关键字个数
    int keys[M];            // 关键字数组（keys[0]不用，从1开始）
    struct BTNode *children[M + 1]; // 子树指针数组
    struct BTNode *parent;  // 指向父节点的指针
} BTNode;

关键字个数范围（m 阶 B 树，非根节点）：

$$\lceil m/2\rceil -1\le n\le m-1$$

最小/最大关键字总数：

• 含 n 个关键字的 B 树，最小高度：每个节点尽可能满，每层 m-1 个关键字。各层节点数为 1, m, m², ...，因此 $n\le m^h-1$，即 $h\ge {\log }_m(n+1)$
• 含 n 个关键字的 B 树，最大高度：每个节点尽可能少。根节点至少 1 个关键字、2 棵子树，其余节点至少 ⌈m/2⌉ 棵子树。第 h+1 层（叶节点层/失败层）至少有 $2\lceil m/2{\rceil }^{h-1}$ 个节点，而 n 个关键字对应 n+1 个失败节点，因此 $n+1\ge 2\lceil m/2{\rceil }^{h-1}$，即 $h\le {\log }_{\lceil m/2\rceil }\frac{n+1}{2}+1$

易错：上述公式中的 h 是 B 树的内部高度，即从根到终端结点的层数，不包含最底层的叶结点（失败结点）层。部分教材将失败结点层也计入高度（此时高度 = h+1），做题时先看清题目对"高度"的定义。例如同一棵树，按内部高度算是 3 层，算上失败层就是 4 层。

查找操作

B 树的查找是一个在节点间纵向移动（磁盘 I/O）与在节点内横向比较（内存操作）交替进行的过程。

关键步骤：

1. 从根节点开始，将目标关键字 key 与当前节点中的关键字顺序比较（节点内关键字较少时用顺序查找，较多时可用折半查找）
2. 若 key = Kᵢ，查找成功，返回该节点及位置
3. 若 K ᵢ < key < Kᵢ₊₁，沿着指针 Pᵢ 进入对应子树，读取下一层节点（一次磁盘 I/O）
4. 若到达叶节点（空指针），查找失败

// B 树查找（返回关键字所在节点和位置）
typedef struct {
    BTNode *node;  // 关键字所在节点
    int index;     // 在节点中的位置
    int found;     // 是否找到：1-成功，0-失败
} SearchResult;

SearchResult BTreeSearch(BTNode *root, int key) {
    BTNode *p = root, *parent = NULL;
    int i;
    while (p != NULL) {
        // 在当前节点中顺序查找
        for (i = 1; i <= p->keyNum && key > p->keys[i]; i++);
        if (i <= p->keyNum && key == p->keys[i])
            return (SearchResult){p, i, 1};  // 查找成功
        parent = p;
        p = p->children[i - 1];  // 沿指针进入子树
    }
    return (SearchResult){parent, i, 0};  // 查找失败，返回插入位置
}

查找过程中磁盘 I/O 次数 = 查找路径上的节点数 = 树的高度 h。节点内的比较在内存中完成，不涉及磁盘访问。

易错：m 阶 B 树中，根结点至少有 2 个子树（如果不是叶子的话），非根结点至少有 ⌈m/2⌉ 个子树。很多同学把根和非根的最小子树数混淆。例如 5 阶 B 树：根至少 2 个子树，非根至少 3 个子树。

易错：B 树的所有叶结点都在同一层（绝对平衡），这是 B 树保持平衡的根本性质。插入导致分裂、删除导致合并，都是为了维护这个性质。B 树长高的唯一方式是根结点分裂。

插入操作

B 树的插入总是发生在最底层的非叶节点（即终端节点）。

关键步骤：

1. 先执行查找，确定关键字应插入的终端节点位置
2. 若该节点插入后关键字数 ≤ m-1，直接插入，完成
3. 若插入后关键字数 = m（溢出），需要进行节点分裂

节点分裂过程：

1. 取该节点的中间关键字 K₍⌈m/2⌉₎
2. 将中间关键字上提到父节点中
3. 原节点分裂为两个节点：中间关键字左边的关键字组成左节点，右边的关键字组成右节点
4. 若父节点也溢出，继续向上分裂，最坏情况一直分裂到根节点，树高度增加 1

以 5 阶 B 树为例，每个节点最多 4 个关键字，插入导致 5 个关键字时触发分裂：

分裂前（溢出）:  [K₁ K₂ K₃ K₄ K₅]
                      ↑ 中间关键字 K₃ 上提

分裂后:    父节点 ← [..., K₃, ...]
              /              \
         [K₁ K₂]          [K₄ K₅]

B 树长高的唯一方式就是根节点分裂——这保证了所有叶节点始终在同一层。

删除操作

B 树的删除需要保证删除后每个节点的关键字数不低于 ⌈m/2⌉-1。分两种情况讨论：

情况一：删除的关键字在终端节点

直接删除，然后检查是否下溢（关键字数 < ⌈m/2⌉-1）。

情况二：删除的关键字在非终端节点

用该关键字的直接前驱（左子树中最右的关键字）或直接后继（右子树中最左的关键字）替换它，转化为删除终端节点中的关键字。

删除后下溢的处理（终端节点关键字数 < ⌈m/2⌉-1）：

处理策略	条件	操作
借兄弟（左借）	左兄弟关键字数 > ⌈m/2⌉-1	父节点关键字下移到当前节点，左兄弟最大关键字上移到父节点
借兄弟（右借）	右兄弟关键字数 > ⌈m/2⌉-1	父节点关键字下移到当前节点，右兄弟最小关键字上移到父节点
合并	左右兄弟关键字数都 = ⌈m/2⌉-1	当前节点与一个兄弟合并，父节点中间隔关键字下移参与合并

合并操作可能导致父节点也下溢，需要逐层向上处理，最坏情况合并到根节点，根节点关键字被掏空后树高度减 1。

借右兄弟示例（5 阶 B 树，节点最少 2 个关键字）:

        [..., 35, ...]          父节点
        /          \
    [20]          [40, 50, 60]   当前节点下溢，右兄弟富余
                ↓
        [..., 40, ...]          35 下移，40 上提
        /          \
    [20, 35]      [50, 60]      恢复平衡

合并示例（5 阶 B 树）:

        [..., 35, ...]          父节点
        /          \
    [20]          [40, 50]       当前节点下溢，右兄弟刚好 ⌈m/2⌉-1
                ↓
        [...]                    35 下移参与合并
          |
    [20, 35, 40, 50]            合并为一个节点

删除连环手算例（一棵树串完全部情况）

5 阶 B 树（非根节点 2~4 个关键字，根至少 1 个），初始：

            [30, 60]
           /    |    \
   [10, 20] [40, 50] [70, 80, 90]

删的关键字在终端节点且删后不下溢（比如删 90），直接删完事，不值得演示。有意思的是下面这条连环：

第 1 删：删 50 → 借右兄弟

[40, 50] 删 50 后剩 [40]，1 < 2 下溢。左兄弟 [10, 20] 刚好 2 个不富余；右兄弟 [70, 80, 90] 有 3 个富余 → 借右：父节点分隔关键字 60 下移到当前节点，右兄弟最小关键字 70 上移到父节点：

            [30, 70]
           /    |    \
   [10, 20] [40, 60] [80, 90]

注意不是把 70 直接搬给 [40]——借兄弟必须经父节点中转（60 下来、70 上去），否则会破坏"父关键字分隔左右子树"的有序性。

第 2 删：删 60 → 合并

[40, 60] 删 60 剩 [40] 下溢。这回左右兄弟都只有 2 个，谁也不富余 → 与右兄弟合并：父节点分隔关键字 70 下移参与合并，[40] + 70 + [80, 90] 拼成一个节点：

         [30]
        /    \
  [10, 20] [40, 70, 80, 90]

父节点只剩 [30]——它是根，根允许只有 1 个关键字，到此为止。

第 3 删：删 30 → 非终端关键字，前驱替换

30 在根（非终端节点），不能直接删：用直接前驱（左子树中最右下的关键字）20 替换 30，问题转化为"删终端节点 [10, 20] 里的 20"。删完 [10] 下溢，右兄弟 [40, 70, 80, 90] 富余 → 借右（20 下移、40 上移）：

         [40]
        /    \
  [10, 20] [70, 80, 90]

第 4 删：删 20 → 又一次借

[10] 下溢，右兄弟 [70, 80, 90] 富余 → 借右（40 下移、70 上移）：

         [70]
        /    \
  [10, 40] [80, 90]

第 5 删：删 10 → 合并掏空根，树高减 1

[40] 下溢，右兄弟 [80, 90] 不富余 → 合并：70 下移，拼成 [40, 70, 80, 90]，根被掏空——删掉空根，树高从 2 层降为 1 层：

  [40, 70, 80, 90]

易错：①下溢判断顺序是"先看能不能借（任一兄弟 > ⌈m/2⌉−1），借不到才合并"，反过来会多做无谓合并；②树长高的唯一方式是根分裂，变矮的唯一方式是根被合并掏空——一对常考结论；③非终端关键字删除用前驱或后继替换均可，真题若未指定，两种替换得到的树形不同但都正确。

复杂度分析

操作	时间复杂度	说明
查找	O(log_m n) 次磁盘 I/O，节点内 O(m)	树高 h = O(log_{⌈m/2⌉} n)，每层一次磁盘访问
插入	O(log_m n)	查找 + 最坏情况逐层分裂到根
删除	O(log_m n)	查找 + 最坏情况逐层合并到根

磁盘 I/O 次数：查找过程中为 h 次；插入最坏需要 h 次查找 + h 次分裂写回；删除最坏需要 h 次查找 + h 次合并写回。实际应用中 m 取较大值（如几百到上千），使得 h 通常只有 3~4 层。

考研高频考点

• m 阶 B 树中非根节点关键字数范围 ⌈m/2⌉-1 ~ m-1（选择题/填空题高频）
• 含 n 个关键字的 m 阶 B 树的最大高度公式推导（大题常考）
• 插入时节点分裂的过程、中间关键字上提（手动建树题）
• 删除时借兄弟与合并操作的判断和执行（手动操作题）
• B 树 vs B+ 树的区别（简答题/选择题高频考查）
• B 树所有叶节点在同一层的原因（概念题）
• 磁盘 I/O 与 B 树阶数选择的关系（理解题）
• 给定关键字序列，画出 B 树的构造过程（综合应用题）

相关知识

• B+ 树是 B 树的变体，所有数据下沉到叶结点并用链表串联，更适合范围查询
• AVL 树是内存中的平衡查找树，B 树可以看作 AVL 在磁盘场景下的多路推广
• 折半查找的判定树本质上是 2 阶 B 树的特例
• 哈希表（开放定址法）在精确匹配上更快，但不支持范围查询，这是树索引与哈希索引的核心权衡

相关文章

• 查找基本概念
• 顺序查找
• 折半查找（二分查找）
• 分块查找
• 二叉排序树查找 → 见树章节
• 平衡二叉树查找 → 见树章节
• 红黑树查找 → 见树章节
• B+ 树
• 哈希表：拉链法
• 哈希表：开放定址法
• 查找算法对比

交互体验

前往完整可视化页面 →

真题练习