C 训练营教程

主题

Lesson 52: B+ 树索引 ​

练习任务 ​

难度：中

实现 B+ 树索引（ORDER=3, MAX_KEY=2），完成以下 7 个核心函数：

  1. create_node(is_leaf) — 分配并初初始化节点（叶子/内部节点节点）
  2. insert_into_leaf(leaf, key, value) — 在有序叶子中插入键值对
  3. split_leaf_child(parent, idx, child) — 分裂满叶子节点（3 key → 2+1）
  4. insert_rec(node, key, value) — 递归插归插入，处理溢出与分裂
  5. insert(root, key, value) — 插入入口口：空树建叶 / 递归插入 / 根溢出建新根
  6. search(root, key) — 从根走到叶子，线性查找 key
  7. print_tree(root, depth) — 递归缩进打印树结构

insert_into_inner（内部节点插入）、free_tree、main 已提供。

本课测试按插入序列 (10,100), (20,200), (5,50), (15,150), (25,250) 逐步验证 B+ 树结构：

After insert(10, v0):
[leaf] keys: 10 | values: 100                    ← 空树创建叶子

After insert(20, v1):
[leaf] keys: 10 20 | values: 100 200             ← 有序插入，未满

After insert(5, v2):                               ← 第一次分裂！
[inner] keys: 20                                  ← 根溢出，创建内部根
  [leaf] keys: 5 10 | values: 50 100
  [leaf] keys: 20 | values: 200

After insert(15, v3):                              ← 第二次分裂
[inner] keys: 15 20
  [leaf] keys: 5 10 | values: 50 100
  [leaf] keys: 15 | values: 150
  [leaf] keys: 20 | values: 200

After insert(25, v4):
[inner] keys: 15 20                               ← 无分裂
  [leaf] keys: 5 10 | values: 50 100
  [leaf] keys: 15 | values: 150
  [leaf] keys: 20 25 | values: 200 250

=== Search Results ===
search(15) = 150
search(30) = -1

提示：核心挑战在于理解分裂的"上移"机制——叶子分裂后，右半第一个 key 上移到父节点作为路由键。同时注意数组多 1 位的溢出位（keys[MAX_KEY+1], values[MAX_KEY+1], children[ORDER+1]）只在分裂前临时存放第 3 个 key。

核心知识点 ​

  • B+ 树 vs 普通 B 树 — 内部节点只存 key（路由），所有 key+value 在叶子，叶子通过 next 形成有序链表
  • 多路平衡树 — ORDER=3（每个节点最多 3 个子节点），MAX_KEY=2（每个节点最多 2 个 key），树始终完美平衡
  • 分裂机制 — 节点满（> MAX_KEY）时分裂：叶子 3→2+1，上移右半第一个 key 到父节点；根溢出时创建新根，树高 +1
  • 叶子链表 — next 指针将叶子串成有序链表，范围查询只需 O(log n + k) 时间
  • 磁盘友好性 — 一个节点 = 一个磁盘磁盘页（4KB~16KB），高分支因子使树高极低，100 万数据只需 ~3 层
  • Union 内存布局 — 叶子用 values[]，内部路由用 children[]，共享同一块内存

代码框架 ​

bplus_tree.c
c
#include <stdio.h>
#include <stdlib.h>

#define ORDER 3
#define MAX_KEY (ORDER - 1) /* = 2, 节点最多 2 个 key */

/* ---------- B+ 树节点 ---------- */
typedef struct BPTreeNode {
    int is_leaf;
    int num_keys;
    int keys[MAX_KEY + 1]; /* +1 容纳分裂前的溢出 */
    union {
        struct BPTreeNode *children[ORDER + 1];
        int values[MAX_KEY + 1];
    };
    struct BPTreeNode *next; /* 叶子链表指针 */
} BPTreeNode;

/* 前向声明 */
static BPTreeNode *create_node(int is_leaf);
static void insert_into_leaf(BPTreeNode *leaf, int key, int value);
static void insert_into_inner(BPTreeNode *inner, int idx, int key,
                               BPTreeNode *left, BPTreeNode *right);
static void split_leaf_child(BPTreeNode *parent, int idx, BPTreeNode *child);
static BPTreeNode *insert_rec(BPTreeNode *node, int key, int value);
static BPTreeNode *insert(BPTreeNode *root, int key, int value);
static int search(BPTreeNode *root, int key);
static void print_tree(BPTreeNode *root, int depth);
static void free_tree(BPTreeNode *root);

/* ================================================================
 * TODO 1: create_node(is_leaf)
 *
 * 用 malloc 分配节点，初始化所有字段。
 * 若 is_leaf: values[0..MAX_KEY] 置 0
 * 若 !is_leaf: children[0..ORDER] 置 NULL
 * ================================================================ */
static BPTreeNode *create_node(int is_leaf) {
    // ① malloc 分配 BPTreeNode
    // ② 设置 is_leaf, num_keys=0, next=NULL
    // ③ 若 is_leaf: for 循环清零 values[0..MAX_KEY]
    // ④ 若 !is_leaf: for 循环置 NULL children[0..ORDER]
}

/* ================================================================
 * TODO 2: insert_into_leaf(leaf, key, value)
 *
 * 将 key/value 按升序插入叶子节点。
 * 1. 找到 pos（第一个 keys[pos] >= key 的位置）
 * 2. 将 pos 及之后的元素后移
 * 3. 在 pos 处写入新 key/value
 * 4. num_keys++
 * ================================================================ */
static void insert_into_leaf(BPTreeNode *leaf, int key, int value) {
    // ① 找位置: pos = 0; while (pos < num_keys && keys[pos] < key) pos++
    // ② 后移: for (i = num_keys; i > pos; i--) keys[i]=keys[i-1]; values[i]=values[i-1]
    // ③ 写入: keys[pos]=key; values[pos]=value
    // ④ num_keys++
}

/* ---------- 在内部节点 idx 位置插入 key 和左右孩子（已提供）---------- */
static void insert_into_inner(BPTreeNode *inner, int idx, int key,
                               BPTreeNode *left, BPTreeNode *right) {
    for (int i = inner->num_keys; i > idx; i--) {
        inner->keys[i] = inner->keys[i - 1];
        inner->children[i + 1] = inner->children[i];
    }
    inner->keys[idx] = key;
    inner->children[idx] = left;
    inner->children[idx + 1] = right;
    inner->num_keys++;
}

/* ================================================================
 * TODO 3: split_leaf_child(parent, idx, child)
 *
 * child 溢出（num_keys=3）。分裂：左 2 + 右 1，右半第一个 key 上移。
 * ================================================================ */
static void split_leaf_child(BPTreeNode *parent, int idx, BPTreeNode *child) {
    // ① new_leaf = create_node(1)
    // ② 复制: new_leaf->keys[0]=child->keys[2]; new_leaf->values[0]=child->values[2]
    // ③ 更新 num_keys: new_leaf->num_keys=1; child->num_keys=2
    // ④ 链表: new_leaf->next = child->next; child->next = new_leaf
    // ⑤ 上移: insert_into_inner(parent, idx, new_leaf->keys[0], child, new_leaf)
}

/* ================================================================
 * TODO 4: insert_rec(node, key, value)
 *
 * 递归插入，返回溢出节点或 NULL
 * ================================================================ */
static BPTreeNode *insert_rec(BPTreeNode *node, int key, int value) {
    // 若 node 是叶子:
    //   ① insert_into_leaf(node, key, value)
    //   ② 若 num_keys > MAX_KEY: return node  // 溢出
    //   ③ return NULL
    //
    // 若 node 是内部节点:
    //   ① 找位置: pos=0; while (pos < num_keys && keys[pos] <= key) pos++
    //   ② overflow = insert_rec(children[pos], key, value)
    //   ③ 若 overflow:
    //        split_leaf_child(node, pos, overflow)
    //        若 num_keys > MAX_KEY: return node
    //   ④ return NULL
}

/* ================================================================
 * TODO 5: insert(root, key, value)
 *
 * 入口函数：处理根溢出、创建新根。
 * ================================================================ */
static BPTreeNode *insert(BPTreeNode *root, int key, int value) {
    // ① 空树: root = create_node(1); 放入 key/value; num_keys=1; return root
    // ② 非空: overflow = insert_rec(root, key, value)
    // ③ 若 overflow:
    //        new_root = create_node(0)
    //        new_root->children[0] = root
    //        split_leaf_child(new_root, 0, overflow)
    //        return new_root
    // ④ return root
}

/* ================================================================
 * TODO 6: search(root, key)
 *
 * 从根走到叶子，线性查找 key，返回 value 或 -1。
 * ================================================================ */
static int search(BPTreeNode *root, int key) {
    // ① root == NULL → return -1
    // ② while (!cur->is_leaf): 找 pos → cur = children[pos]
    // ③ 在叶子中: for i 遍历，keys[i]==key → return values[i]
    // ④ return -1
}

/* ================================================================
 * TODO 7: print_tree(root, depth)
 *
 * 递归缩进打印 B+ 树结构（缩进 = depth 个 "  "）。
 * ================================================================ */
static void print_tree(BPTreeNode *root, int depth) {
    // ① root == NULL: print "(empty tree)\n"
    // ② 缩进: depth 个 "  "
    // ③ 若 is_leaf: "[leaf] keys: ... | values: ...\n"
    // ④ 若 !is_leaf: "[inner] keys: ...\n" + 递归打印 children[0..num_keys]
}

/* ---------- 释放整棵树（已提供）---------- */
static void free_tree(BPTreeNode *root) {
    if (root == NULL) return;
    if (!root->is_leaf) {
        for (int i = 0; i <= root->num_keys; i++)
            free_tree(root->children[i]);
    }
    free(root);
}

/* ========== 主流程（已提供）========== */
int main(void) {
    printf("=== B+ Tree Index (ORDER=3, MAX_KEY=2) ===\n\n");
    BPTreeNode *root = NULL;

    int inserts[][2] = {
        {10, 100}, {20, 200}, {5, 50}, {15, 150}, {25, 250},
    };
    int n_inserts = sizeof(inserts) / sizeof(inserts[0]);

    for (int i = 0; i < n_inserts; i++) {
        int key = inserts[i][0];
        int value = inserts[i][1];
        root = insert(root, key, value);
        printf("After insert(%d, v%d):\n", key, i);
        print_tree(root, 0);
        printf("\n");
    }

    printf("=== Search Results ===\n");
    printf("search(15) = %d\n", search(root, 15));
    printf("search(30) = %d\n", search(root, 30));

    free_tree(root);
    return 0;
}

阅读骨架后，尝试自己填充 // ① 到 // ⑦ 标记的部分。核心挑战在于：分裂时如何计算"右半第一个 key"？insert_rec 的返回值如何驱动分裂？根溢出时如何创建新根？叶子链表的 next 如何维护？

TIP

先不要往下翻看参考解答。用 insert(10,v0), insert(20,v1), insert(5,v2) 三个操作在纸上完整追踪一遍分裂过程。重点关注 num_keys 的变化——3 个 key 如何变成左 2 右 1。

深度讲解 ​

1. B+ 树结构——什么是 B+ 树？ ​

1.1 B+ 树 vs 普通 B 树 ​

B+ 树是一种多路平衡搜索树，是数据库索引（如 MySQL InnoDB）的核心数据结构。它与普通 B 树的本质区别在于数据存放位置：

B 树（所有节点存数据）:          B+树（仅叶子存数据）:
       [10,v0 | 20,v1]                 [10 | 20]       ← 内部节点只存 key（路由）
      /      |       \                /      |      \
  [5,v2] [15,v3] [25,v4]        [5,v2|10,v0] [15,v3|20,v1] [25,v4]  ← 叶子存 key+value
                                 ↑                              ↑
                                 └──────── next ────────────────┘  ← 链表连接

B+ 树的四个关键特性：

特性说明工程价值
内部节点只存 key不存 value，节省空间每个节点可容纳更多 key，树更矮
数据全在叶子key+value 只出现在叶子查找代价稳定，总是走到叶子
叶子链表next 串联所有叶子范围查询 O(log n + k)，无需回溯
完美平衡所有叶子在同一层最坏查找 O(log n)，无退化风险

1.2 本课 B+ 树规格 ​

ORDER  = 3           ← 阶数（每个节点最多 ORDER 个子节点）
MAX_KEY = ORDER - 1 = 2   ← 每个节个节点最多 2 个 key
MIN_KEY = ORDER / 2 = 1   ← 每个节点最少 1 个 key（根除外）

内部节点结构:
  is_leaf = 0
  keys[0], keys[1]           ← 最多 2 个路由键
  children[0], children[1], children[2]  ← 最多 3 个子节点
  例如: [15 | 20] → children[0] 管理 <15, children[1] 管理 [15,20), children[2] 管理 ≥20

叶子节点结构:
  is_leaf = 1
  keys[0], keys[1]           ← 最多 2 个键
  values[0], values[1]       ← 对应的值
  next → 下一个叶子           ← 链表指针
  例 例如: [5,v2 | 10,v0] → next → [15,v3 | 20,v1] → next → [25,v4] → NULL

**重要: 数组多 1 位（keys[MAX_KEY+1], values[MAX_KEY+1], children[ORDER+1]），用于在分裂前临时存放溢出元素。例如叶子在分裂前有 3 个 key —— keys[2] 是溢出位。

1.3 Union 内存布局 ​

BPTreeNode 的内存布局（ORDER=3, MAX_KEY=2）:

┌───────────┬──────────┬─────────────────────┬─────────────────────┬──────────┐
│ is_leaf  │ num_keys │ keys[0] keys[1]     │ values[0] values[1] │  next    │
│  (int)   │  (int)   │ keys[2] (溢出位)    │ values[2] (溢出位)  │ (ptr)    │
│          │          │                     │  或 children[0..3]  │          │
└──────────┴──────────┴─────────────────────┴─────────────────────┴──────────┘

union 让 values 和 children 共享同一块内存:
  - 叶子节点: 使用 values[0..2]，children 不使用
  - 内部节点: 使用 children[0..3]，values 不使用
  - 溢出位 keys[2] 在分裂前临时存放第 3 个 key

CAUTION

忘记数组 +1 会导致越界——keys[2] 写入 values[0] 位置（union），数据错乱极难排查。数组长度必须用 MAX_KEY+1（key/value）和 ORDER+1（children）。

2. 插入操作逐步跟踪 ​

以本题的插入序列为例：insert(10,v0), insert(20,v1), insert(5,v2), insert(15,v3), insert(25,v4)

步骤 1: insert(10, v0) ​

树为空 → create_node(1) 创建叶子节点:
  放入: keys[0]=10, values[0]=100, num_keys=1

[leaf] keys: 10 | values: 100

步骤 2: insert(20, v1) ​

从根（叶子）插入 20:
  insert_into_leaf: pos=1（20 > 10）
  结果: keys: 10 20 | values: 100 200

num_keys=2，未超过 MAX_KEY=2，无需分裂。
[leaf] keys: 10 20 | values: 100 200

步骤 3: insert(5, v2) —— 第一次分裂！ ​

从根（叶子）插入 5:

insert_into_leaf: pos=0（5 < 10）
  后移: keys[1]=5? 不对——是 keys[2]=keys[1], values[2]=values[1];
        keys[1]=keys[0], values[1]=values[0]
  写入: keys[0]=5, values[0]=50
  结果: keys: 5 10 20 | values: 50 100 200

num_keys=3 > MAX_KEY=2 → 溢出！

分裂过程（split_leaf_child）：

┌──────────────────────────────────────────────────┐
│ 分裂前: child = [5,v2 | 10,v0 | 20,v1]          │
│                                                    │
│ 1. new_leaf = create_node(1)                       │
│ 2. 右半复制: new_leaf->keys[0] = child->keys[2]   │
│             = 20                                  │
│             new_leaf->values[0] = child->values[2]│
│             = 200                                 │
│ 3. child->num_keys = 2（保留 [5,10]）             │
│    new_leaf->num_keys = 1（保留 [20]）            │
│ 4. 链表: new_leaf->next = child->next;            │
│          child->next = new_leaf                   │
│ 5. 上移: insert_into_inner(parent, idx, 20,       │
│                             child, new_leaf)      │
└──────────────────────────────────────────────────┘

根节点溢出 → insert() 创建新根：

insert() 检测 overflow → 创建内部节点 new_root:
  new_root = create_node(0)
  new_root->children[0] = root        ← 旧根成为第一个孩子
  split_leaf_child(new_root, 0, overflow)  ← 将溢出叶子分裂到新根下

结果:
        [inner] keys: 20
        /                \
  [leaf] keys: 5 10   [leaf] keys: 20
  values: 50 100      values: 200

内部节点路由规则（keys[pos] <= key 时 pos++）:
  - key=5:  5 <= 20 → pos=0, 走 children[0] ✓
  - key=10: 10 <= 20 → pos=0, 走 children[0] ✓
  - key=20: 20 <= 20 → pos=1, 走 children[1] ✓
  - key=25: 25 > 20  → pos=1, 走 children[1] ✓

步骤 4: insert(15, v3) —— 第二次分裂！ ​

从根（内部节点）开始:
  key=15, 根 keys=[20], 15 <= 20 → pos=0, 递归进入 children[0]

到达叶子 [5,v2 | 10,v0]，插入 15:
  insert_into_leaf: pos=2（15 > 10）
  结果: keys: 5 10 15 | values: 50 100 150
  num_keys=3 > MAX_KEY=2 → 溢出！

insert_rec 返回溢出节点 → 父节点调用 split_leaf_child:

┌──────────────────────────────────────────────────┐
│ 分裂前: child = [5,v2 | 10,v0 | 15,v3]          │
│                                                    │
│ 右半复制: new_leaf = [15,v3]                      │
│ child 保留: [5,v2 | 10,v0]                        │
│ 上移 key = 15（new_leaf->keys[0]）                │
│                                                    │
│ 父节点 [inner] keys: 20 在 idx=0 处插入 15:       │
│   insert_into_inner(parent, 0, 15, child, new_leaf)│
│   → [inner] keys: 15 20                           │
│      children[0]=[5,10], children[1]=[15],        │
│        children[2]=[20]                             │
└──────────────────────────────────────────────────┘

结果:
        [inner] keys: 15 20
        /        |        \
  [leaf]      [leaf]     [leaf]
  keys: 5 10  keys: 15   keys: 20
  vals:50 100 vals:150   vals:200

步骤 5: insert(25, v4) —— 无分裂 ​

从根开始: key=25, 根 keys=[15,20], pos:
  15 <= 25 → pos=1; 20 <= 25 → pos=2
  递归进入 children[2] = [20,v1]

到达叶子 [20,v1]，插入 25:
  insert_into_leaf: pos=1（25 > 20）
  结果: keys: 20 25 | values: 200 250

num_keys=2，未超过 MAX_KEY=2，无需分裂。

最终 B+树:
        [inner] keys: 15 20
        /        |        \
  [leaf]      [leaf]     [leaf]
  keys: 5 10  keys: 15   keys: 20 25
  vals:50 100 vals:150   vals:200 250
  next→      next→      next→NULL

IMPORTANT

内部节点路由规则必须统一——keys[pos] <= key 时 pos++。也就是说，key 大于等于当前分隔键时走右边。这个规则在 insert_rec 和 search 中必须一致，否则插入和查找会走不同的路径。

3. 分裂规则——高度增长的唯一途径 ​

3.1 叶子分裂（3 个 key → 2+1） ​

节点满（num_keys > MAX_KEY）时的分裂策略:

┌──────────┬──────────┬──────────┐
│ keys[0]  │ keys[1]  │ keys[2]  │
│ values[0]│ values[1]│ values[2]│
└──────────┴──────────┴──────────┘
       ↓
┌─ └─────────────────┐   ┌──────────┐
│ keys[0]   keys[1] │   │ keys[2]  │  ← 右半第一个 key = up_key
│ values[0] values[1]│   │ values[2]│
└───────────────────┘   └──────────┘
左半 (num_keys=2)       右半 (num_keys=1)
                             ↑
                     up_key = new_leaf->keys[0]

关键操作：insert_into_inner(parent, idx, up_key, child, new_leaf) 将上移 key 和左右孩子插入父节点。

3.2 根溢出——树高 +1 ​

根溢什么是 B+ 树高度增长的唯一途径唯一途径。insert() 函数检测 insert_rec 返回值：

root_overflow.c
c
BPTreeNode *insert(BPTreeNode *root, int key, int value) {
    if (root == NULL) {
        root = create_node(1);
        root->keys[0] = key;
        root->values[0] = value;
        root->num_keys = 1;
        return root;
    }

    BPTreeNode *overflow = insert_rec(root, key, value);
    if (overflow) {
        BPTreeNode *new_root = create_node(0);
        new_root->children[0] = root;
        split_leaf_child(new_root, 0, overflow);
        return new_root;
    }
    return root;
}

根溢出的三步走：

  1. 创建新的内部节点 new_root
  2. 将旧根设为 new_root 的第一个孩子
  3. 调用 split_leaf_child 将溢出的旧根分裂到新根中

NOTE

这个"创建新根 → 旧根降级为孩子 → 分裂"的过程，让树的高度在顶部增长，底层所有叶子保持在同一层——这正是"完美平衡"的来源。

4. 叶子链表与范围查询 ​

B+ 树的关键优势——叶子节点通过 next 指针形成有序链表：

[leaf] → next → [leaf] → next → [leaf] → next → NULL
keys: 5 10      keys: 15      keys: 20 25

范围查询 [12, 25]:
  1. 从根走到起始叶子: search(12) → 走到 [5,10] 叶子
     （找不到 12 但叶子 15 的链表在前方）
  2. 沿链表遍历:
     [5,10]: 5<12✗, 10<12✗ → 跳过
     next→[15]: 15≥12 ✓ → 输出 15→150
     next→[20,25]: 20≥12 ✓ → 输出 20→200, 25→250
     next→NULL → 结束

链表让范围查询只需 O(log n + k)，k 为结果数数量。
无链表则需要回溯遍历（或递归中序），复杂度高得多。

分裂时链表维护的关键代码：

leaf_list_maintenance.c
c
/* 分裂时维护链表——两行代码，但顺序至关重要 */
new_leaf->next = child->next;   // ① new_leaf 继承 child 的原后继
child->next = new_leaf;         // ② child 的 successor 变成 new_leaf

/* 错误示例：顺序颠倒 */
child->next = new_leaf;         // ✗ 先断了 child→next 的引用
new_leaf->next = child->next;   // ✗ 此时 child->next 已经是 new_leaf 了！
                                //   链表变成环！

5. 磁盘友好性——为什么数据库用 B+ 树 ​

5.1 二叉树 vs B+ 树：磁盘 I/O 天差地别 ​

二叉搜索树（磁盘不友好）:              B+树（磁盘友好）:
        50                               [20 | 50 | 80]    ← 一个节点多个 key
       /  \                              /    |    |    \
      20  80                          [5,10] [30,40] [60,70] [90,99]
     / \  / \
    ... ... ...                        一个节点 = 一个磁盘页（4KB~16KB）
                                       一次 I/O 读取多个 key
每个节点一次磁盘 I/O，               树高大幅降低，I/O 次数少
100 万数据 → 树高 ~20               100 万数据 → 树高 ~3（阶数=100）

核心洞察：

  • 数据库的瓶颈是磁盘 I/O，而非 CPU 比较次数
  • 一个磁盘页通常 4KB~16KB，可以容纳数百个 key
  • B+ 树内部节点只存 key（不存 value），让一个节点装更多路由键
  • 高分支因子 → 极低的树高 → 极少的磁盘 I/O
以 MySQL InnoDB 为例:
  页大小 = 16KB
  内部节点: key(4B) + child_ptr(6B) = 10B/record
            → 每页 ~1600 个 key → 分支因子 ~1600
  
  3 层 B+ 树可存储: 1600 × 1600 × 1600 ≈ 40 亿条记录
  查找任意记录只需 3 次磁盘 I/O！

5.2 B+ 树 vs 其他索引结构 ​

结构查找范围查询插入磁盘友好典型用户
B+ 树O(log n)O(log n + k)O(log n)极好MySQL, PostgreSQL
跳表O(log n)O(log n + k)O(log n)差(多指针)Redis, LevelDB
哈希表O(1)不支持O(1)差(随机)内存缓存
LSM 树O(log n)O(log n + k)O(1) 写入好(顺序写)RocksDB, HBase

TIP

B+ 树适合"读多写少"的 OLTP 场景（MySQL 默认）。LSM 树适合"写多读少"的场景（日志系统、时序数据）。选型取决于读写比例——没有银弹。

6. 常见错误与排查 ​

错误后果正确做法
忘记数组 +1 导致越界keys[2] 写入 values[0] 位置（union），数据错乱使用 MAX_KEY+1 和 ORDER+1 的数组
分裂时未维护 next 链表范围查询断裂new_leaf->next = child->next; child->next = new_leaf
内部路由用 < 而而非 <=key 等于分于分隔键时走错子树，查找失败使使用 keys[pos] <= key 判断
根溢出时未创建新根树高度不增长，数据丢失insert() 中检测 overflow 并建新根
insert_into_leaf 只移动 keyskeys 和 values 错位for 循环中同时移动 keys[i] 和 values[i]
叶子分裂后 num_keys 设置错后续插入越界或数据丢失3 个 key 时：左半 2 个，右半 1 个
search 路由规则与 insert 不一致查找与插入走不同路径统

参考解答 ​

练习1: create_node — 分配并初始化节点
solution_create_node.c
c
static BPTreeNode *create_node(int is_leaf) {
    BPTreeNode *node = malloc(sizeof(BPTreeNode));
    node->is_leaf = is_leaf;
    node->num_keys = 0;
    node->next = NULL;

    if (is_leaf) {
        for (int i = 0; i <= MAX_KEY; i++)
            node->values[i] = 0;
    } else {
        for (int i = 0; i <= ORDER; i++)
            node->children[i] = NULL;
    }
    return node;
}

要点：循环上界分别是 MAX_KEY 和 ORDER（包含溢出位）。叶子清零 values，内部节点置 NULL children。

练习2: insert_into_leaf — 有序插入到叶子
solution_insert_into_leaf.c
c
static void insert_into_leaf(BPTreeNode *leaf, int key, int value) {
    int pos = 0;
    while (pos < leaf->num_keys && leaf->keys[pos] < key)
        pos++;

    for (int i = leaf->num_keys; i > pos; i--) {
        leaf->keys[i] = leaf->keys[i - 1];
        leaf->values[i] = leaf->values[i - 1];
    }

    leaf->keys[pos] = key;
    leaf->values[pos] = value;
    leaf->num_keys++;
}

要点：keys[pos] < key（不是 <=），保证相同 key 时找到第一个大于等于的位置。后移时必须同时移动 keys 和 values。

练习3: split_leaf_child — 分裂溢出叶子
solution_split_leaf_child.c
c
static void split_leaf_child(BPTreeNode *parent, int idx,
                              BPTreeNode *child) {
    BPTreeNode *new_leaf = create_node(1);

    new_leaf->keys[0] = child->keys[MAX_KEY];
    new_leaf->values[0] = child->values[MAX_KEY];
    new_leaf->num_keys = 1;
    child->num_keys = MAX_KEY;

    new_leaf->next = child->next;
    child->next = new_leaf;

    insert_into_inner(parent, idx, new_leaf->keys[0], child, new_leaf);
}

要点：

  1. 右半复制 child->keys[MAX_KEY]（即 keys[2]）到 new_leaf
  2. child->num_keys = MAX_KEY（= 2，保留左半两个 key）
  3. 链表维护顺序：先继承 child->next，再重设 child->next
  4. up_key = new_leaf->keys[0] 上移到父节点
练习4: insert_rec — 递归插入
solution_insert_rec.c
c
static BPTreeNode *insert_rec(BPTreeNode *node, int key, int value) {
    if (node->is_leaf) {
        insert_into_leaf(node, key, value);
        return (node->num_keys > MAX_KEY) ? node : NULL;
    }

    int pos = 0;
    while (pos < node->num_keys && node->keys[pos] <= key)
        pos++;

    BPTreeNode *overflow = insert_rec(node->children[pos], key, value);
    if (overflow) {
        split_leaf_child(node, pos, overflow);
        if (node->num_keys > MAX_KEY)
            return node;
    }
    return NULL;
}

要点：

  1. 叶子节点直接插入，返回溢出标记
  2. 内部节点先路由到孩子，收到溢出后调用 split_leaf_child
  3. 分裂后检查自身是否溢出
  4. 路由规则 keys[pos] <= key 决定分支方向
练习5: insert — 插入入口（处理根溢出）
solution_insert.c
c
static BPTreeNode *insert(BPTreeNode *root, int key, int value) {
    if (root == NULL) {
        root = create_node(1);
        root->keys[0] = key;
        root->values[0] = value;
        root->num_keys = 1;
        return root;
    }

    BPTreeNode *overflow = insert_rec(root, key, value);
    if (overflow) {
        BPTreeNode *new_root = create_node(0);
        new_root->children[0] = root;
        split_leaf_child(new_root, 0, overflow);
        return new_root;
    }
    return root;
}

要点：空树直接创建叶子并返回。非空树调用 insert_rec，根溢出时创建新内部节点并返回（这是唯一返回新 root 的场景）。

练习6: search — 查找 key
solution_search.c
c
static int search(BPTreeNode *root, int key) {
    if (root == NULL)
        return -1;

    BPTreeNode *cur = root;
    while (!cur->is_leaf) {
        int pos = 0;
        while (pos < cur->num_keys && cur->keys[pos] <= key)
            pos++;
        cur = cur->children[pos];
    }

    for (int i = 0; i < cur->num_keys; i++) {
        if (cur->keys[i] == key)
            return cur->values[i];
    }
    return -1;
}

要点：内部节点路由规则与 insert_rec 完全一致（keys[pos] <= key）。到达叶子后线性遍历查找。

练习7: print_tree — 递归缩进打印
solution_print_tree.c
c
static void print_tree(BPTreeNode *root, int depth) {
    if (root == NULL) {
        printf("(empty tree)\n");
        return;
    }

    for (int i = 0; i < depth; i++)
        printf("  ");

    if (root->is_leaf) {
        printf("[leaf] keys: ");
        for (int i = 0; i < root->num_keys; i++)
            printf("%d ", root->keys[i]);
        printf("| values: ");
        for (int i = 0; i < root->num_keys; i++)
            printf("%d ", root->values[i]);
        printf("\n");
    } else {
        printf("[inner] keys: ");
        for (int i = 0; i < root->num_keys; i++)
            printf("%d ", root->keys[i]);
        printf("\n");
        for (int i = 0; i <= root->num_keys; i++)
            print_tree(root->children[i], depth + 1);
    }
}

要点：缩进用两个空格。内部节点递归打印所有 num_keys + 1 个子树。叶子打印全部 key 和 value。

对照检查：create_node 中循环上界是 MAX_KEY 和 ORDER 吗？insert_into_leaf 中 keys 和 values 同时移动了吗？split_leaf_child 中链表维护顺序正确吗？insert_rec 的路由规则和 search 一致吗？search 中 keys[pos] <= key 是 <= 而非 < 吗？

课堂讨论 ​

  1. B+ 树用 ORDER=3 其实很小——为什么？实际数据库（MySQL InnoDB）的 B+ 树阶数通常是几十到几百，一个节点正好填满一个磁盘页（16KB）。教学目标下 ORDER=3 的原因是什么？
  2. B+ 树和跳表（Skip List）都是有序索引结构——跳表实现简单但空间开销大（多层指针），B+ 树磁盘友好。Redis 用跳表，MySQL 用 B+ 树。它们分别在什么场景下更合适？
  3. 内部节点路由用 keys[pos] <= key 中的 <=（而非 <）——如果改成 <，当 key 恰好等于分隔键时会怎样？用 [inner] keys: 15 20 中 search(15) 为例分析。
  4. 叶子分裂时 num_keys 设为 2（左半）和 1（右半）——为什么不是 1+2 或平均分？分裂策略的设计思路是什么？
  5. B+ 树删除操作更复杂（可能合并节点），但原理类似——从叶子删除后，若节点太空（< MIN_KEY）则向兄弟借或合并。试思考删除 10（在 [5,10] 叶子）会触发什么？
  6. B+ 树的完美平衡依赖于分裂"自底向上"传播——如果某个内部节点分裂导致父节点溢出，程序如何处理？当前代码能正确支持多层分裂吗？

讨论答案 ​

Q1: ORDER=3 的教学目的

实际数据库中 B+ 树阶数很大（MySQL InnoDB 页大小 16KB，分支因子可达数百），但教学中用 ORDER=3：

  • 可追踪性：小阶数让每次分裂和查找都能手算验证。用 ORDER=100 时，插入 5 个元素不会触发任何分裂——学不到分裂机制。
  • 暴露边界：ORDER=3 时 MAX_KEY=2，只需 3 个 key 就触发分裂，分裂策略（3→2+1）清晰可见。
  • 完整性：ORDER=3 时在少数几次插入中就能完成"空树→根溢出→多层结构"的完整生命周期。

理解 ORDER=3 后，换用更大的阶数只是参数变化——核心逻辑（分裂上移、递归传播、叶子链表）完全一致。

Q2: B+ 树 vs 跳表
维度B+ 树跳表
实现复杂度高（分裂、合并逻辑）低（随机层数 + 链表操作）
磁盘友好好（节点连续存储，一次 I/O 多 key）差（指针跳跃，缓存 miss 多）
空间开销紧凑（数组连续）大（每层额外指针）
并发控制复杂（锁子树或 latch）简单（锁链表段）
范围查询好（叶子链表）好（本身就是有序链表）
典型场景磁盘数据库（MySQL, PostgreSQL）内存数据库（Redis sorted set）

Redis 用跳表而非 B+ 树的原因：Redis 是全内存数据库，无磁盘 I/O 问题，跳表的实现简洁性和并发友好性更有价值。

Q3: <= 改为 < 的后**：
[inner] keys: 15 20
  children[0]: [5,10]  children[1]: [15]  children[2]: [20]

search(15) 用 < 而非 <=:
  pos=0: keys[0]=15, 15 < 15? → false, pos 仍为 0
  走 children[0] = [5,10] ← 打不到 15！

search(15) 用 <=:
  pos=0: keys[0]=15, 15 <= 15? → true, pos=1
  走 children[1] = [15] ← 找到 15 ✓

结论：<= 让等于分隔键的 key 走到正确的子树。
     用 < 会导致 key == keys[pos] 时走左子树，找不到数据。
Q4: 分裂策略 3→2+1 的设计

分裂时 child->num_keys 设为 2（MAX_KEY），new_leaf->num_keys 为 1：

  • 最大化左半利用率：左半保留 MAX_KEY（=2）个 key，尽量让节点"吃饱"
  • 上移 key 保持正确：右半第一个 key（new_leaf->keys[0]）就是上移 key，路由规则 keys[pos] <= key 让所有 ≥ 此 key 的查找走右子树
  • 可扩展性：对于更大的 ORDER，策略统一为"左半 ┌MAX_KEY/2┘，右半 └MAX_KEY/2┘"，中间 key 上移

对于 ORDER=3: MAX_KEY=2, 左半=2, 右半=1, 上移 key = new_leaf->keys[0]

Q5: 删除操作分析

B+ 树删除的基本流程：

删除 10（在 [5,10] 叶子）:
  1. 找到叶子 [5,10]
  2. 删除 keys[1]=10, values[1]=100
  3. num_keys 从 2 变为 1（= MIN_KEY，不必合并）

但如果删除后 num_keys < MIN_KEY（=1）:
  情况 A: 左兄弟有富余 key → 借一个（旋转）
  情况 B: 右兄弟有富余 key → 借一个（旋转）
  情况 C: 兄弟都很穷 → 合并节点
         合并后父节点少一个 key，可能引发父节点合并
         → 递归向上，可能降低树高

本题聚焦插入与查找，删除的实现留给扩展学习。《算法导论》第 18 章有完整的 B 树删除算法。

Q6: 多层分裂传播

当前代码能正确处理多层分裂。原因在于递归设计：

multi_level_split.c
c
/* insert_rec 的递归结构天然支持多层分裂 */
BPTreeNode *insert_rec(BPTreeNode *node, int key, int value) {
    // ... 叶子情况 ...

    // 内部节点：
    BPTreeNode *overflow = insert_rec(node->children[pos], key, value);
    if (overflow) {
        split_leaf_child(node, pos, overflow);  // 在 node 层分裂
        if (node->num_keys > MAX_KEY)
            return node;  // ← 自身溢出，向上传播
    }
    return NULL;
}

每次 insert_rec 返回非 NULL 时，调用者会调用 split_leaf_child 并检查自身是否溢出——溢出的检测结果继续向上返回。这样，分裂信号可以从叶子一路传播到根，每层都可能触发分裂。

课后练习 ​

  1. 实现范围查询。在 B+ 树中添加 range_query(root, lower, upper) 函数，输出所有 lower <= key <= upper 的键值对。利用叶子链表遍历。

    知识点提示：先用 search 的逻辑找到最小叶子（不一定是精确匹配），然后沿 next 遍历直到 key > upper。

    参考解答
    ex1_range_query.c
    c
    void range_query(BPTreeNode *root, int lower, int upper) {
    if (root == NULL) return;

    /* 走到最小叶子 */
    BPTreeNode *cur = root;
    while (!cur->is_leaf) {
        int pos = 0;
        while (pos < cur->num_keys && cur->keys[pos] < lower)
            pos++;
        cur = cur->children[pos];
    }

    /* 沿链表遍历输出 */
    while (cur) {
        for (int i = 0; i < cur->num_keys; i++) {
            if (cur->keys[i] > upper) return;
            if (cur->keys[i] >= lower)
                printf("%d -> %d\n", cur->keys[i], cur->values[i]);
        }
        cur = cur->next;
    }
}

    注意内部节点路由用 < lower 而非 <=——我们要找的是第一个可能包含 ≥ lower 的叶子，小于 lower 的分隔键被跳过。

  2. 删除操作。实现 delete_key(root, key)——从叶子中删除 key，处理后可能触发合并（留给有挑战性的同学）。先用简单的"懒惰删除"——标记 flag 而非真正删除——来思考索引的生命周期。

    知识点提示：实际上数据库常使用"标记删除"（tombstone）+ 后台 compaction 而非立即合并，避免删除阻塞查询。思考为什么这样设计。

  3. 通用 ORDER。将代码中的 #define ORDER 3 改为宏参数，支持任意 ORDER。修改分裂策略使 split_leaf_child 对任意 ORDER 通用（左半 ┌MAX_KEY/2┘，右半 └MAX_KEY/2┘）。

    知识点提示：将 child->keys[MAX_KEY] 改为 child->keys[(MAX_KEY + 1) / 2]（右半起始位置），右半大小 = MAX_KEY - 起始位置 + 1。

    参考解答
    ex3_generic_order.c
    c
    /* 通用叶子分裂 */
static void split_leaf_child(BPTreeNode *parent, int idx,
                              BPTreeNode *child) {
    BPTreeNode *new_leaf = create_node(1);

    int split_point = (MAX_KEY + 1) / 2;  /* 右半起始 */
    int right_count = MAX_KEY + 1 - split_point;

    for (int i = 0; i < right_count; i++) {
        new_leaf->keys[i] = child->keys[split_point + i];
        new_leaf->values[i] = child->values[split_point + i];
    }
    new_leaf->num_keys = right_count;
    child->num_keys = split_point;

    new_leaf->next = child->next;
    child->next = new_leaf;

    insert_into_inner(parent, idx, new_leaf->keys[0], child, new_leaf);
}

    这样 ORDER 改为 5, 7, 甚至是 100，分裂逻辑都无需再改。

  4. B+ 树验证函数。编写 validate_bptree(root)，验证：

    • 所有叶子在同一深度
    • 内部节点的 key 是右子树的最小值
    • 叶子链表 next 正确连接
    • keys 有序

    知识点提示：用递归遍历，记录深度并在第一个叶子处记录期望深度。内部节点验证 keys[i] == 最左叶子的第一个 key（或遍历验证）。

  5. 统计节点利用率。编写 stats(root) 统计 B+ 树的：节点总数、叶子数、内部节点数、平均 key 填充率。用随机插入 100 个 key 观察 ORDER=3 vs ORDER=5 的填充率差异。

    知识点提示：填充率 = num_keys / MAX_KEY。ORDER 越大，填充率通常越高（分裂更均匀）。

参考资料 ​

  • 《算法导论》第 18 章 — B 树的完整定义、插入/删除的伪代码与复杂度分析
  • 《数据库系统概念》§11.3 — B+ 树索引在实际数据库中的应用，包括聚簇索引与二级索引
  • MySQL 官方文档：InnoDB Index Structures — B+ 树在 MySQL 中的具体实现（页组织、页分裂）
  • 《数据结构与算法分析——C 语言描述》§4.7 — B 树的 C 语言实现与分析
  • CMU 15-445 Database Systems — Lecture 8-9: Tree Indexes，含 B+ 树并发控制（latch crabbing）

Released under the MIT License.

Copyright © 2026-present OpenCamp C Team