10. B 树与外存数据结构

1. 什么是 B 树？

B 树（B-Tree）是一种自平衡的多路搜索树，主要用于磁盘等外部存储设备。它由 Rudolf Bayer 和 Ed McCreight 在 1972 年发明，专门为减少磁盘 I/O 操作而设计。

1.1 为什么需要 B 树？

在数据库和文件系统中，数据量往往非常大，无法全部加载到内存中。传统的二叉搜索树在处理磁盘数据时效率低下，因为：

磁盘 I/O 操作非常慢：相比内存访问，磁盘访问慢几个数量级
树的高度影响性能：二叉树可能很高，需要多次磁盘访问
磁盘按块读取：一次磁盘读取会读入一个数据块（通常 4KB-8KB）

B 树通过增加每个节点的子节点数量来降低树的高度，从而减少磁盘访问次数。

1.2 B 树的关键特性

B 树是一棵 m 阶（m-way）的搜索树，具有以下性质：

每个节点最多有 m 个子节点
除根节点外，每个内部节点至少有⌈m/2⌉个子节点
根节点至少有 2 个子节点（除非它是叶子节点）
所有叶子节点在同一层
非叶子节点有 k 个子节点时，包含 k-1 个关键字
节点内的关键字按升序排列

2. B 树的结构

2.1 节点结构

一个 B 树节点包含：

关键字数组：存储排序的关键字
子节点指针数组：指向子树的指针
关键字数量：当前节点中的关键字个数
是否为叶子节点：标识节点类型

2.2 阶数的含义

B 树的阶数 m 决定了：

每个节点最多有 m-1 个关键字
每个节点最多有 m 个子节点
除根节点外，每个节点至少有⌈m/2⌉-1 个关键字

例如，对于 5 阶 B 树：

每个节点最多 4 个关键字，5 个子节点
每个非根节点至少 2 个关键字，3 个子节点

3. B 树的基本操作

3.1 搜索操作

搜索过程类似于二叉搜索树，但在每个节点进行多路选择：

算法步骤：

从根节点开始
在当前节点的关键字中查找目标值
如果找到，返回成功
如果未找到，根据关键字的顺序确定应该进入哪个子树
递归在相应子树中继续搜索
如果到达叶子节点仍未找到，返回失败

时间复杂度：O(log n)

代码示例位置：[示例代码 1：B 树搜索]

下面给出搜索操作的核心函数。它在当前节点内先做有序扫描，若未命中则沿着对应分支继续下降。由于 B 树始终保持平衡，这个过程的高度上界是对数级。

enum { T = 3 };

typedef struct BTreeNode {
    int n;
    int leaf;
    int keys[2 * T - 1];
    struct BTreeNode *child[2 * T];
} BTreeNode;

static BTreeNode *bt_search(BTreeNode *x, int k, int *idx) {
    int i = 0;
    while (i < x->n && k > x->keys[i]) {
        ++i;
    }
    if (i < x->n && k == x->keys[i]) {
        if (idx != NULL) {
            *idx = i;
        }
        return x;
    }
    if (x->leaf) {
        return NULL;
    }
    return bt_search(x->child[i], k, idx);
}

运行结果：该代码块展示的是搜索核心逻辑，单独运行通常无终端输出。

3.2 插入操作

插入操作比搜索复杂，需要处理节点分裂：

算法步骤：

像搜索一样找到应该插入的叶子节点
如果叶子节点未满，直接插入关键字
如果叶子节点已满：
- 将节点分裂为两个节点
- 中间关键字提升到父节点
- 如果父节点也满了，继续向上分裂
如果分裂到达根节点，创建新根，树高度增加

分裂规则：

将节点的 m 个关键字分成三部分
左边⌊m/2⌋个关键字留在原节点
中间的关键字提升到父节点
右边的关键字移到新节点

时间复杂度：O(log n)

代码示例位置：[示例代码 2：B 树插入]

插入的关键点是“在下降前先处理满子节点”，这样到达叶子后一定有空位可插入。下面的 split_child 和 insert_nonfull 是最常见的实现骨架。

static BTreeNode *bt_new_node(int leaf);

static void split_child(BTreeNode *x, int i) {
    BTreeNode *y = x->child[i];
    BTreeNode *z = bt_new_node(y->leaf);
    z->n = T - 1;

    for (int j = 0; j < T - 1; ++j) {
        z->keys[j] = y->keys[j + T];
    }
    if (!y->leaf) {
        for (int j = 0; j < T; ++j) {
            z->child[j] = y->child[j + T];
        }
    }
    y->n = T - 1;

    for (int j = x->n; j >= i + 1; --j) {
        x->child[j + 1] = x->child[j];
    }
    x->child[i + 1] = z;

    for (int j = x->n - 1; j >= i; --j) {
        x->keys[j + 1] = x->keys[j];
    }
    x->keys[i] = y->keys[T - 1];
    x->n += 1;
}

static void insert_nonfull(BTreeNode *x, int k) {
    int i = x->n - 1;
    if (x->leaf) {
        while (i >= 0 && k < x->keys[i]) {
            x->keys[i + 1] = x->keys[i];
            --i;
        }
        x->keys[i + 1] = k;
        x->n += 1;
        return;
    }

    while (i >= 0 && k < x->keys[i]) {
        --i;
    }
    ++i;
    if (x->child[i]->n == 2 * T - 1) {
        split_child(x, i);
        if (k > x->keys[i]) {
            ++i;
        }
    }
    insert_nonfull(x->child[i], k);
}

运行结果：该代码块展示的是插入核心逻辑，单独运行通常无终端输出。

3.3 删除操作

删除操作是 B 树中最复杂的操作：

算法步骤：

情况 1：从叶子节点删除

如果删除后节点仍满足最小关键字数要求，直接删除
否则需要调整（借用或合并）

情况 2：从内部节点删除

找到前驱或后继关键字替换要删除的关键字
转化为在叶子节点删除的问题

调整策略：

向兄弟节点借用：如果相邻兄弟节点有多余的关键字
- 从左兄弟借：将父节点的关键字下移，左兄弟的最大关键字上移
- 从右兄弟借：将父节点的关键字下移，右兄弟的最小关键字上移
与兄弟节点合并：如果兄弟节点都没有多余关键字
- 将父节点的分隔关键字下移
- 合并当前节点和兄弟节点
- 如果父节点也不满足要求，继续向上调整

时间复杂度：O(log n)

代码示例位置：[示例代码 3：B 树删除]

删除阶段的重点在“下降前保证目标子节点至少有 T 个关键字”，这样在下探过程中不会出现无法修复的下溢。实现上通常分为三步：先尝试向兄弟借关键字；借不到就和兄弟合并；必要时把根下沉一层。下面给出删除入口的常见框架，便于对照前面的文字流程。

typedef struct {
    BTreeNode *root;
} BTree;

static void delete_from_node(BTreeNode *x, int k);

static void bt_delete(BTree *tree, int k) {
    if (tree->root == NULL) {
        return;
    }
    delete_from_node(tree->root, k);

    if (tree->root->n == 0) {
        BTreeNode *old = tree->root;
        if (old->leaf) {
            tree->root = NULL;
        } else {
            tree->root = old->child[0];
        }
        free(old);
    }
}

运行结果：该代码块展示的是删除入口逻辑，单独运行通常无终端输出。

4. B 树的详细示例

4.1 构建 5 阶 B 树

让我们逐步插入关键字序列：10, 20, 30, 40, 50, 60, 70, 80, 90

步骤 1-4：插入 10, 20, 30, 40

txt

[10, 20, 30, 40]

步骤 5：插入 50，节点满了需要分裂

txt

      [30]
     /    \
[10, 20]  [40, 50]

中间值 30 提升为根

步骤 6-7：插入 60, 70

txt

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

步骤 8：插入 80，右子节点满了需要分裂

txt

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

中间值 60 提升到根

步骤 9：插入 90

txt

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

4.2 删除示例

从上述 B 树中删除关键字 40：

步骤 1：40 在内部节点的子节点中

txt

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

删除 40 后，[40, 50]变成[50]，仍满足最小关键字数要求（⌈5/2⌉-1 = 2-1 = 1）

代码示例位置：[示例代码 4：完整的构建和删除演示]

5. B 树的变体

5.1 B+ 树

B+ 树是 B 树的变体，具有以下特点：

所有数据都存储在叶子节点
内部节点只存储索引信息
叶子节点通过链表连接，便于范围查询
广泛应用于数据库索引（如 MySQL 的 InnoDB）

5.2 B*树

B*树是 B 树的另一个变体：

提高了空间利用率：节点至少 2/3 满
延迟分裂：先尝试重新分配关键字，再考虑分裂
减少了分裂操作的次数

6. B 树的应用

6.1 数据库索引

B 树是数据库管理系统中最常用的索引结构：

MySQL：InnoDB 使用 B+ 树
PostgreSQL：使用 B 树的变体
MongoDB：使用 B 树索引

优势：

减少磁盘 I/O 次数
支持范围查询
保持数据有序

6.2 文件系统

许多文件系统使用 B 树来管理目录和文件：

NTFS：使用 B+ 树管理文件记录
HFS+：使用 B 树管理目录结构
Btrfs：Linux 文件系统，名字来源于 B 树

6.3 其他应用

键值存储：LevelDB、RocksDB
全文搜索引擎：某些索引结构
操作系统：内存管理、进程调度

7. B 树的性能分析

7.1 时间复杂度

操作	平均情况	最坏情况
搜索	O(log n)	O(log n)
插入	O(log n)	O(log n)
删除	O(log n)	O(log n)

7.2 空间复杂度

空间利用率：约 50%（最坏情况）到 100%（最好情况）
平均空间利用率：约 69%
总空间：O(n)

7.3 与其他数据结构的比较

B 树 vs 二叉搜索树：

B 树高度更低，适合磁盘存储
二叉树实现更简单，适合内存操作

B 树 vs 哈希表：

B 树支持范围查询和有序遍历
哈希表查找更快（O(1)），但不支持范围查询

B 树 vs 跳表：

B 树更节省空间
跳表实现更简单，并发性能更好

8. 实现要点

8.1 节点的最小度数（t）

实践中常用"最小度数 t"而不是"阶数 m"：

每个节点至少有 t-1 个关键字（根节点除外）
每个节点最多有 2t-1 个关键字
每个内部节点至少有 t 个子节点
每个内部节点最多有 2t 个子节点

关系：t = ⌈m/2⌉

8.2 性能优化技巧

选择合适的阶数：
- 考虑磁盘块大小
- 通常选择使节点大小接近一个磁盘块
批量操作优化：
- 批量插入时可以自底向上构建
- 减少分裂次数
缓存策略：
- 将根节点和高层节点保持在内存中
- 使用 LRU 等缓存算法
并发控制：
- 使用锁或锁存器保护节点
- 考虑乐观并发控制

9. 常见问题

Q1：为什么 B 树适合磁盘存储？

A：B 树通过增加节点的分支因子来降低树的高度，从而减少磁盘访问次数。一个节点可以存储多个关键字，恰好对应一个磁盘块，充分利用了磁盘的块读取特性。

Q2：B 树和 B+ 树的主要区别是什么？

A：主要区别在于：

B 树的数据存储在所有节点中，B+ 树只在叶子节点存储数据
B+ 树的叶子节点通过链表连接，支持高效的范围查询
B+ 树的内部节点更小，可以有更多的分支，树高更低

Q3：如何选择 B 树的阶数？

A：通常根据磁盘块大小和关键字大小来选择：

txt

阶数 m ≈ 磁盘块大小 / (关键字大小 + 指针大小)

例如，磁盘块 4KB，关键字 + 指针共 100 字节，则 m ≈ 40

Q4：B 树的删除为什么这么复杂？

A：因为 B 树要维护平衡性质，删除可能导致节点关键字数不足，需要通过借用或合并来调整。这个调整可能级联向上传播到根节点。

10. 可运行最小实现（搜索 + 插入 + 删除）

为了让前面的流程可以直接落地，本章补充了一份可运行的最小实现，路径是：/code/数据结构与算法/数据结构/b_tree_minimal.c。它覆盖了创建节点、搜索、分裂、插入、删除、遍历与释放，采用最小度数 T=2，便于把插入与删除的主路径一起验证。

下面是该程序在 main 中的核心调用片段：

int data[] = {10, 20, 5, 6, 12, 30, 7, 17};
for (int i = 0; i < 8; ++i) {
    bt_insert(&t, data[i]);
}

printf("inorder: ");
bt_traverse(t.root);
printf("\n");

printf("search 6: %s\n", bt_search(t.root, 6, NULL) != NULL ? "found" : "not found");
printf("search 15: %s\n", bt_search(t.root, 15, NULL) != NULL ? "found" : "not found");

int removed[] = {6, 13, 7, 4, 2, 16};
for (int i = 0; i < 6; ++i) {
    printf("delete %d\n", removed[i]);
    bt_delete(&t, removed[i]);
    printf("inorder: ");
    bt_traverse(t.root);
    printf("\n");
}

可能的输出（示例）：

bash

inorder: 5 6 7 10 12 17 20 30 search 6: found search 15: not found delete 6 inorder: 5 7 10 12 17 20 30 delete 13 inorder: 5 7 10 12 17 20 30 delete 7 inorder: 5 10 12 17 20 30 delete 4 inorder: 5 10 12 17 20 30 delete 2 inorder: 5 10 12 17 20 30 delete 16 inorder: 5 10 12 17 20 30

习题

#30018

⚡5⏳5

实现一个最小度数为 $2$ 的 B 树页分裂操作和不变式验证器。这里不要求实现磁盘文件或完整的删除算法，只处理已经装入内存的页：

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

enum {
    BTREE_MAX_KEYS = 3,
    BTREE_MAX_CHILDREN = 4
};

typedef struct {
    bool leaf;
    size_t key_count;
    int64_t keys[BTREE_MAX_KEYS];
    size_t children[BTREE_MAX_CHILDREN];
} BTreePage;

bool btree_split_full_child(
    BTreePage *pages,
    size_t page_count,
    size_t parent_index,
    size_t child_slot,
    size_t right_index,
    int64_t *out_promoted
);

bool btree_validate(
    const BTreePage *pages,
    size_t page_count,
    size_t root
);

约定 SIZE_MAX 表示不存在的子页；page_count 表示已经分配的页数，不包含容量池中的空闲页。分裂调用可以暂时传入一个尚未被父页引用的 right_index；分裂成功后它必须从根页可达，而 btree_validate 要求传入的整组页已经全部从根页可达。

要求：

btree_split_full_child 的 child_slot 指向一个恰好有 3 个升序键的满子页；将中间键提升到父页，左页保留较小键，right_index 指向的新右页保留较大键。非叶子页的 4 个子页引用也必须按中间键正确分配。
父页必须有空余键槽；插入提升键前安全地向右搬移键和子页引用。所有页索引、槽位、key_count 和 right_index 都必须先验证，失败时页数组和 *out_promoted 保持不变。
新右页必须是当前树中未被引用的页；分裂成功后父页新增一个子页引用，且不能制造重复引用、环或不可达页。
btree_validate 必须检查根页和非根页的占用范围（非根页有 $1$ 到 $3$ 个键，空树只能由一个空的叶根表示）、键的严格升序、内部页的子页数量和 SIZE_MAX 位置、所有叶子深度相同，以及每个页只能从根到达一次。
验证键范围时使用上下界和开闭区间，不得通过对 INT64_MIN 或 INT64_MAX 做加减来构造边界；必须检查页索引和所有计数运算不会溢出。
分裂操作的时间复杂度应为 $O (1)$ （这里的最小度数固定为 $2$ ），验证器的时间复杂度应为 $O (P)$ ，其中 $P$ 是页数；说明页数组的所有权和遍历标记的释放责任。

3.10 求值

4.3 选择语句

5.5 跳转语句

10.2 结构体

14.3 程序支持

15.1 声明

16.2 对象表示

18.2 标准库中的宏

10. B 树与外存数据结构 ​

1. 什么是 B 树？ ​

1.1 为什么需要 B 树？ ​

1.2 B 树的关键特性 ​

2. B 树的结构 ​

2.1 节点结构 ​

2.2 阶数的含义 ​

3. B 树的基本操作 ​

3.1 搜索操作 ​

3.2 插入操作 ​

3.3 删除操作 ​

4. B 树的详细示例 ​

4.1 构建 5 阶 B 树 ​

4.2 删除示例 ​

5. B 树的变体 ​

5.1 B+ 树 ​

5.2 B*树 ​

6. B 树的应用 ​

6.1 数据库索引 ​

6.2 文件系统 ​

6.3 其他应用 ​

7. B 树的性能分析 ​

7.1 时间复杂度 ​

7.2 空间复杂度 ​

7.3 与其他数据结构的比较 ​

8. 实现要点 ​

8.1 节点的最小度数（t） ​

8.2 性能优化技巧 ​

9. 常见问题 ​

Q1：为什么 B 树适合磁盘存储？ ​

Q2：B 树和 B+ 树的主要区别是什么？ ​

Q3：如何选择 B 树的阶数？ ​

Q4：B 树的删除为什么这么复杂？ ​

10. 可运行最小实现（搜索 + 插入 + 删除） ​

习题 ​

10. B 树与外存数据结构

1. 什么是 B 树？

1.1 为什么需要 B 树？

1.2 B 树的关键特性

2. B 树的结构

2.1 节点结构

2.2 阶数的含义

3. B 树的基本操作

3.1 搜索操作

3.2 插入操作

3.3 删除操作

4. B 树的详细示例

4.1 构建 5 阶 B 树

4.2 删除示例

5. B 树的变体

5.1 B+ 树

5.2 B*树

6. B 树的应用

6.1 数据库索引

6.2 文件系统

6.3 其他应用

7. B 树的性能分析

7.1 时间复杂度

7.2 空间复杂度

7.3 与其他数据结构的比较

8. 实现要点

8.1 节点的最小度数（t）

8.2 性能优化技巧

9. 常见问题

Q1：为什么 B 树适合磁盘存储？

Q2：B 树和 B+ 树的主要区别是什么？

Q3：如何选择 B 树的阶数？

Q4：B 树的删除为什么这么复杂？

10. 可运行最小实现（搜索 + 插入 + 删除）

习题