B-tree 深度解剖：从磁盘 I/O 模型到 boltdb 源码

一、引言：为什么 B-tree 统治了磁盘世界

如果你打开任何一本数据库教科书，B-tree 几乎总是出现在索引一章的第一节。这并非偶然——自 1972 年 Rudolf Bayer 和 Edward McCreight 在波音公司的研究实验室提出这一数据结构以来，B-tree 及其变体已经成为关系型数据库、文件系统、键值存储乃至搜索引擎的核心骨架。

B-tree 之所以能统治存储领域长达半个世纪，根本原因在于它与磁盘 I/O 模型之间近乎完美的契合。本文将从物理磁盘模型出发，逐层剖析这种契合是如何建立的，然后深入到分裂、合并、批量加载等关键操作的工程实现，最后通过 boltdb 源码和手写 C 实现来巩固理解。

本文假设读者具备基本的树结构知识（了解二叉搜索树即可），但不要求有数据库内核开发经验。

二、磁盘 I/O 模型：理解一切的起点

2.1 机械硬盘的物理约束

一块传统的 HDD（机械硬盘）由多个高速旋转的盘片组成，每个盘片上有同心圆状的磁道（track），磁道被划分为扇区（sector），扇区是磁盘 I/O 的最小物理单元，通常为 512 字节或 4096 字节（Advanced Format）。

读取一个扇区的时间由三部分组成：

总延迟 = 寻道时间(seek) + 旋转延迟(rotational) + 传输时间(transfer)

典型的 7200 RPM 硬盘参数如下：

关键洞察：随机读一个 4 KB 页需要约 10 ms，而顺序读 4 KB 只需约 0.02 ms。两者相差约 500 倍。这就是为什么所有面向磁盘的数据结构都拼命减少随机 I/O 次数。

2.2 页（Page）对齐与操作系统层

操作系统通过页缓存（Page Cache）在内存和磁盘之间搭建缓冲层。文件系统以块（block）为单位管理磁盘空间，Linux 上默认块大小为 4 KB，与虚拟内存页大小一致。

数据库引擎通常绕过文件系统缓存（O_DIRECT），自己管理缓冲池（Buffer Pool）。但无论哪种方式，一次 I/O 操作的最小单位是一个页（4-16 KB）。即使你只需要读 1 字节，操作系统也会把整个页读入内存。

这意味着：如果我们能把”逻辑上相邻的数据”放在”物理上同一个页”里，就能用一次 I/O 获取更多有用信息。B-tree 正是围绕这个原则设计的。

2.3 SSD 改变了什么，没改变什么

SSD 消除了寻道时间和旋转延迟，随机读延迟降至 0.05-0.1 ms（比 HDD 快 100 倍）。但 SSD 仍然有两个与 B-tree 相关的特性：

1. 读写以页为单位：NVMe SSD 的内部页大小通常为 4-16 KB，与 B-tree 节点大小天然对齐。
2. 写放大敏感：NAND 闪存的擦除以块（128-256 KB）为单位，而写入以页为单位。额外的写入会加速闪存磨损，因此减少写放大（Write Amplification）在 SSD 上尤为重要。

即便在全闪存时代，B-tree 仍然是最常用的索引结构——只是参数调优方向变了。

三、B-tree 核心原理

3.1 基本定义

一棵 阶（order）为 m 的 B-tree 满足以下性质：

1. 每个节点最多包含 m-1 个键和 m 个子指针。
2. 每个非根节点至少包含 ceil(m/2)-1 个键。
3. 根节点至少包含 1 个键（除非树为空）。
4. 所有叶子节点位于同一层。
5. 节点内的键有序排列，子指针 child[i] 指向的子树中所有键 k 满足 key[i-1] < k < key[i]。

以 m=5（5 阶 B-tree）为例：

           [20 | 40]
          /    |    \
   [5|10|15] [25|30] [45|50|55|60]

每个节点最多 4 个键。根节点有 2 个键和 3 个子指针。所有叶子在同一层。

3.2 B-tree 查找

B-tree 的查找过程与二叉搜索树类似，但在每个节点内部使用二分查找（或线性扫描，取决于 m 的大小）来确定走哪个子树。

Search(node, key):
    i = 0
    while i < node.n and key > node.keys[i]:
        i = i + 1
    if i < node.n and key == node.keys[i]:
        return (node, i)          // 找到
    if node.is_leaf:
        return NOT_FOUND
    DiskRead(node.children[i])    // 一次磁盘 I/O
    return Search(node.children[i], key)

查找的 I/O 次数等于树的高度 h。对于 N 个键的 B-tree：

h <= log_{ceil(m/2)}((N+1)/2) + 1

当 m=1000（一个 4 KB 页大约能容纳 500-1000 个键）且 N=10^9 时：

h <= log_500(5 * 10^8) + 1 ≈ 3.2 + 1 ≈ 4

也就是说，10 亿条记录只需要 3-4 次磁盘 I/O 就能定位到目标。而如果使用平衡二叉树（如红黑树），同样的数据量需要 log2(10^9) ≈ 30 次随机 I/O。

3.3 B-tree 高度对比

这张表清楚地说明了为什么 B-tree 在面向磁盘的场景中具有压倒性优势。

四、B-tree 与 B+tree 的差异

B+tree 是 B-tree 最重要的变体，几乎所有现代数据库都使用 B+tree 而非原始 B-tree。两者的核心区别如下：

4.1 结构差异

4.2 为什么数据库偏好 B+tree

理由一：更高的扇出

内部节点不存储实际数据，只存储键和子指针。假设键为 8 字节整数，子指针为 8 字节，一个 4 KB 页能容纳约 4096 / (8+8) = 256 个分支。如果 B-tree 的内部节点还要存储 100 字节的行数据，扇出降至 4096 / (8+100+8) ≈ 35。更高的扇出意味着更矮的树，从而减少 I/O 次数。

理由二：稳定的查找性能

B-tree 中，如果目标键恰好在根节点，查找只需 1 次 I/O；如果在叶子节点，则需要 h 次。B+tree 的查找总是走到叶子节点，性能可预测。

理由三：范围查询

B+tree 的叶子节点通过链表相连，范围查询（如 SELECT * WHERE id BETWEEN 100 AND 200）只需定位到起始叶子，然后沿链表顺序扫描。这完美利用了磁盘顺序读的高吞吐。

理由四：简化并发控制

由于数据只存储在叶子节点，内部节点的修改频率较低，锁竞争更少。这对高并发的 OLTP 系统至关重要。

4.3 B+tree 示意

内部节点（仅存键和指针）:
              [20 | 50]
             /    |    \
            v     v     v

叶子节点（存键和数据，通过链表连接）:
  [5,10,15] <-> [20,25,30,40] <-> [50,55,60,70,80]
   |  |  |       |  |  |  |       |  |  |  |  |
  d1 d2 d3      d4 d5 d6 d7      d8 d9 ...

叶子节点中的 d1, d2, ... 表示实际数据（行指针或内联数据）。

五、节点分裂与合并：最核心的变换操作

节点分裂（split）和合并（merge）是 B-tree 保持平衡的关键机制。下面以 5 阶 B-tree（每个节点最多 4 个键）为例详细说明。

5.1 节点分裂（Split）

当向一个已满的节点插入新键时，触发分裂：

分裂步骤（以插入键 25 到已满节点 [15|20|30|35] 为例）：

1. 将新键 25 插入正确位置，得到临时的 5 个键：[15|20|25|30|35]。
2. 选取中位数键 25 作为分裂点。
3. 左半部分 [15|20] 保留在原节点。
4. 右半部分 [30|35] 移至新节点。
5. 中位数键 25 上提（promote）到父节点。
6. 父节点获得一个新的子指针，指向新节点。

伪代码：

SplitChild(parent, i, child):
    new_node = AllocateNode()
    new_node.is_leaf = child.is_leaf
    mid = floor(m/2)

    // 右半部分键移到新节点
    for j = 0 to mid-2:
        new_node.keys[j] = child.keys[mid+j]
    new_node.n = mid - 1

    // 如果不是叶子，还要移动子指针
    if not child.is_leaf:
        for j = 0 to mid-1:
            new_node.children[j] = child.children[mid+j]

    child.n = mid - 1

    // 在父节点中为新节点腾出位置
    for j = parent.n downto i+1:
        parent.children[j+1] = parent.children[j]
    parent.children[i+1] = new_node

    for j = parent.n-1 downto i:
        parent.keys[j+1] = parent.keys[j]
    parent.keys[i] = child.keys[mid-1]    // 中位数上提
    parent.n = parent.n + 1

    DiskWrite(child)
    DiskWrite(new_node)
    DiskWrite(parent)

分裂的 I/O 开销：3 次写（原节点、新节点、父节点）。如果父节点也满了，分裂会级联向上传播，最坏情况下一直到根节点。根节点分裂是 B-tree 长高的唯一方式。

5.2 级联分裂的概率分析

一个节点满的概率约为 1/B（B 为节点容量），因此级联分裂传播到第 k 层的概率为 (1/B)^k。对于 B=256：

• 分裂传播到第 2 层的概率：1/256 ≈ 0.4%
• 分裂传播到第 3 层的概率：1/65536 ≈ 0.0015%

因此，分裂操作的摊还代价为 O(1/B) 次额外 I/O，非常低。

5.3 节点合并（Merge）

当删除操作导致节点的键数量低于最小阈值 ceil(m/2)-1 时，需要从兄弟节点借键或进行合并。

借键（Redistribution）：如果相邻兄弟节点有”多余”的键（键数量大于最小阈值），从兄弟借一个键过来，通过父节点中转。

借键示意：

  父:    [...| 30 |...]          父:    [...| 25 |...]
            / \                          / \
  左: [10|20|25]  右: [35]  =>  左: [10|20]  右: [30|35]

  左兄弟的最大键 25 上提到父节点，父节点原来的键 30 下放到右节点。

合并：如果兄弟节点也处于最小键数状态，无法借键，则将两个节点合并为一个，并从父节点下拉一个键。

合并示意：

  父:    [...| 30 |...]          父:    [...|...]
            / \                        |
  左: [10|20]  右: [35]  =>    合并: [10|20|30|35]

  父节点的键 30 下拉，与两个子节点合并为一个节点。

合并可能导致父节点下溢，触发级联合并，最终可能使树高度减 1（根节点只剩 0 个键时被删除）。

5.4 删除算法完整流程

Delete(node, key):
    if node.is_leaf:
        remove key from node
        return

    i = find position of key in node
    if key is in node.keys:
        if child[i] has >= ceil(m/2) keys:
            predecessor = rightmost key in subtree child[i]
            node.keys[i] = predecessor
            Delete(child[i], predecessor)
        elif child[i+1] has >= ceil(m/2) keys:
            successor = leftmost key in subtree child[i+1]
            node.keys[i] = successor
            Delete(child[i+1], successor)
        else:
            merge child[i] and child[i+1]
            Delete(merged_child, key)
    else:
        // key should be in subtree child[i]
        if child[i] has < ceil(m/2) keys:
            // need to fix before descending
            if left_sibling has >= ceil(m/2) keys:
                borrow from left
            elif right_sibling has >= ceil(m/2) keys:
                borrow from right
            else:
                merge with a sibling
        Delete(child[i], key)

六、批量加载与写放大

6.1 批量加载（Bulk Loading）

当需要从零构建一棵包含大量已排序数据的 B-tree 时，逐条插入效率很低——每次插入都要从根节点查找到叶子节点，然后可能触发分裂。

更高效的方法是自底向上批量加载：

1. 将排序好的数据按叶子节点容量分组。
2. 每组构成一个叶子节点（填充因子可控，通常设为 70-90%）。
3. 从每组中提取最大键（或最小键），构建上一层的内部节点。
4. 递归构建直到根节点。

BulkLoad(sorted_keys, fill_factor=0.7):
    max_keys = floor(m * fill_factor)
    // 步骤1：构建叶子层
    leaves = []
    for i = 0 to len(sorted_keys) step max_keys:
        leaf = new LeafNode()
        leaf.keys = sorted_keys[i : i+max_keys]
        leaves.append(leaf)

    // 步骤2：逐层向上构建内部节点
    current_level = leaves
    while len(current_level) > 1:
        parents = []
        for i = 0 to len(current_level) step (max_keys+1):
            parent = new InternalNode()
            children = current_level[i : i+max_keys+1]
            parent.children = children
            parent.keys = [child.keys[0] for child in children[1:]]
            parents.append(parent)
        current_level = parents

    root = current_level[0]
    return root

优势对比：

当 N=10^9, B=256 时，逐条插入约需 10^9 * 4 ≈ 4 * 10^9 次 I/O，批量加载约需 10^9 / 256 ≈ 4 * 10^6 次 I/O。差距达 1000 倍。

6.2 写放大（Write Amplification）

写放大是指：为了写入 1 字节有效数据，实际需要写入磁盘多少字节。

对于 B+tree，修改一个叶子节点中的一条记录：

写放大 = 页大小 / 有效写入大小

假设页大小 16 KB，修改一条 100 字节的记录：

写放大 = 16384 / 100 = 163.84

如果修改还导致内部节点更新（如分裂），写放大更高。

在 SSD 上，写放大直接关系到设备寿命。假设 SSD 总写入寿命为 1 PB（PBW），业务每天写入 100 GB 有效数据：

不考虑写放大：寿命 = 1PB / 100GB = 10000 天 ≈ 27 年
写放大 160x：寿命 = 10000 / 160 ≈ 62 天

这就是为什么现代存储引擎会花大量精力优化写放大。常见策略包括：

• Write-Ahead Log (WAL)：先写日志（顺序写），再批量刷脏页。
• Page Compaction：在页内紧凑存储，减少碎片。
• Copy-on-Write B-tree：不原地修改，而是写入新页（boltdb 的策略）。
• LSM-tree：完全放弃原地更新，通过追加写和后台合并来大幅降低写放大（但增加读放大）。

6.3 各存储引擎写放大对比

七、boltdb 源码剖析：Go 中的 B+tree 实现

boltdb 是一个纯 Go 编写的嵌入式键值数据库，以简洁著称（核心代码不到 5000 行）。它使用 B+tree 作为底层数据结构，采用 Copy-on-Write（COW）策略实现事务。

7.1 核心数据结构

// node.go - B+tree 节点的内存表示
type node struct {
    bucket     *Bucket   // 所属的 Bucket
    isLeaf     bool      // 是否为叶子节点
    unbalanced bool      // 是否需要重平衡
    spilled    bool      // 是否已写入脏页
    key        []byte    // 该节点的最小键（用于父节点索引）
    pgid       pgid      // 对应的磁盘页 ID
    parent     *node     // 父节点指针
    children   nodes     // 子节点指针
    inodes     inodes    // 节点内的键值对
}

// inode 表示节点内的一个条目
type inode struct {
    flags uint32  // 标志位（如是否为子 Bucket）
    pgid  pgid    // 子节点的页 ID（内部节点使用）
    key   []byte  // 键
    value []byte  // 值（叶子节点使用）
}

boltdb 的 node 结构直接对应 B+tree 的一个节点。inodes 切片存储节点内的所有键值对，在叶子节点中 value 包含实际数据，在内部节点中 pgid 指向子节点。

7.2 页（Page）布局

// page.go - 磁盘上的页结构
type page struct {
    id       pgid    // 页 ID
    flags    uint16  // 页类型（branch/leaf/meta/freelist）
    count    uint16  // 页内元素数量
    overflow uint32  // 溢出页数量
    ptr      uintptr // 数据区起始地址
}

const (
    branchPageFlag   = 0x01  // 内部节点页
    leafPageFlag     = 0x02  // 叶子节点页
    metaPageFlag     = 0x04  // 元数据页
    freelistPageFlag = 0x10  // 空闲页列表
)

boltdb 使用 mmap 将数据库文件映射到内存，页大小默认为操作系统页大小（通常 4 KB）。每个 B+tree 节点恰好对应磁盘上的一个或多个连续页。

7.3 节点查找

// node.go
func (n *node) search(key []byte) (index int, exact bool) {
    // 使用标准库的二分查找
    index = sort.Search(len(n.inodes), func(i int) bool {
        return bytes.Compare(n.inodes[i].key, key) != -1
    })
    // 检查是否精确匹配
    if index < len(n.inodes) && bytes.Equal(n.inodes[index].key, key) {
        exact = true
    }
    return
}

这段代码非常简洁：使用 Go 标准库的 sort.Search 在 inodes 切片上做二分查找。B+tree 的查找从根节点开始，逐层调用 search 方法确定走哪个子节点，直到到达叶子。

7.4 节点分裂

// node.go - 分裂操作（简化版）
func (n *node) split(pageSize int) []*node {
    var nodes []*node
    node := n
    for {
        // 找到合适的分裂点
        a, b := node.splitTwo(pageSize)
        nodes = append(nodes, a)
        if b == nil {
            break
        }
        node = b
    }
    return nodes
}

func (n *node) splitTwo(pageSize int) (*node, *node) {
    // 如果节点大小未超过页大小，无需分裂
    if len(n.inodes) <= minKeysPerPage*2 || n.sizeLessThan(pageSize) {
        return n, nil
    }

    // 找到分裂点：尽量让两边大小均衡
    splitIndex, _ := n.splitIndex(pageSize)

    // 创建新节点，将右半部分移过去
    next := &node{bucket: n.bucket, isLeaf: n.isLeaf, parent: n.parent}
    next.inodes = n.inodes[splitIndex:]
    n.inodes = n.inodes[:splitIndex]

    return n, next
}

func (n *node) splitIndex(pageSize int) (index int, sz int) {
    sz = pageHeaderSize
    // 从第一个元素开始累加大小，找到超过阈值的位置
    for i, inode := range n.inodes {
        elsize := n.pageElementSize() + len(inode.key) + len(inode.value)
        // 至少保留 minKeysPerPage 个键在每一侧
        if i >= minKeysPerPage && sz+elsize > pageSize {
            break
        }
        index = i + 1
        sz += elsize
    }
    return
}

boltdb 的分裂策略值得注意：它不是简单地取中位数分裂，而是按页大小分裂。这样可以确保每个节点恰好占一个磁盘页，最大化空间利用率。这是工程实现与教科书算法的关键差异。

7.5 Copy-on-Write 事务

boltdb 的写事务遵循 COW 原则：

// tx.go - 写事务提交（简化流程）
func (tx *Tx) Commit() error {
    // 1. 重平衡：合并过小的节点
    tx.root.rebalance()

    // 2. 分裂：将过大的节点分裂
    tx.root.spill()

    // 3. 将脏页写入磁盘（写到新位置，不覆盖旧页）
    tx.write()

    // 4. 更新元数据页，指向新的根节点
    tx.writeMeta()

    return nil
}

COW 的优势在于： - 读事务无锁：读事务看到的是一致的快照，因为旧页不会被修改。 - 崩溃恢复简单：如果写事务中途崩溃，旧的元数据页仍然指向完好的旧树。

代价是每次写事务都需要复制从修改节点到根节点路径上的所有节点（O(h) 次页写入）。

八、完整 C 实现：B+tree 搜索、插入与分裂

下面给出一个完整的 B+tree C 实现，包含搜索、插入、分裂操作。为了清晰起见，阶数设为编译期常量。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/* -------- 配置 -------- */
#define ORDER       5                       /* B+tree 阶数 */
#define MAX_KEYS    (ORDER - 1)             /* 节点最大键数 */
#define MIN_KEYS    ((ORDER + 1) / 2 - 1)  /* 节点最小键数 */

/* -------- 节点定义 -------- */
typedef struct BPNode {
    int      n;                     /* 当前键数 */
    int      keys[ORDER];          /* 键数组（多留 1 个位置用于临时插入） */
    void    *ptrs[ORDER + 1];      /* 叶子: ptrs[i] 指向数据; 内部: ptrs[i] 指向子节点
                                      叶子的 ptrs[n] 指向下一个叶子 */
    bool     is_leaf;
    struct BPNode *parent;
} BPNode;

/* -------- 全局根节点 -------- */
static BPNode *root = NULL;

/* -------- 辅助函数 -------- */
static BPNode *make_node(bool is_leaf) {
    BPNode *nd = calloc(1, sizeof(BPNode));
    nd->is_leaf = is_leaf;
    return nd;
}

/* 在节点内二分查找，返回第一个 >= key 的位置 */
static int lower_bound(BPNode *nd, int key) {
    int lo = 0, hi = nd->n;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nd->keys[mid] < key)
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}

/* -------- 查找 -------- */
/* 返回包含 key 的叶子节点，若 out_idx 非 NULL 则写入键在叶子中的位置 */
BPNode *bpt_find_leaf(int key) {
    if (!root) return NULL;
    BPNode *cur = root;
    while (!cur->is_leaf) {
        int i = lower_bound(cur, key);
        /* 如果 key > 所有键，走最右子树 */
        if (i == cur->n)
            cur = (BPNode *)cur->ptrs[i];
        else if (key == cur->keys[i])
            cur = (BPNode *)cur->ptrs[i + 1];
        else
            cur = (BPNode *)cur->ptrs[i];
    }
    return cur;
}

/* 精确查找键对应的值指针，未找到返回 NULL */
void *bpt_search(int key) {
    BPNode *leaf = bpt_find_leaf(key);
    if (!leaf) return NULL;
    int i = lower_bound(leaf, key);
    if (i < leaf->n && leaf->keys[i] == key)
        return leaf->ptrs[i];
    return NULL;
}

/* -------- 分裂 -------- */
/* 分裂叶子节点，返回新节点，通过 out_key 返回上提的键 */
static BPNode *split_leaf(BPNode *leaf, int *out_key) {
    BPNode *new_leaf = make_node(true);
    int split = (ORDER + 1) / 2;  /* 左边保留 split 个键 */

    new_leaf->n = leaf->n - split;
    for (int i = 0; i < new_leaf->n; i++) {
        new_leaf->keys[i] = leaf->keys[split + i];
        new_leaf->ptrs[i] = leaf->ptrs[split + i];
    }
    leaf->n = split;

    /* 维护叶子链表 */
    new_leaf->ptrs[ORDER] = leaf->ptrs[ORDER];
    leaf->ptrs[ORDER] = new_leaf;

    *out_key = new_leaf->keys[0];  /* 上提键 = 新叶子的最小键 */
    new_leaf->parent = leaf->parent;
    return new_leaf;
}

/* 分裂内部节点，返回新节点，通过 out_key 返回上提的键 */
static BPNode *split_internal(BPNode *nd, int *out_key) {
    BPNode *new_nd = make_node(false);
    int split = ORDER / 2;

    *out_key = nd->keys[split];   /* 中位数键上提 */

    new_nd->n = nd->n - split - 1;
    for (int i = 0; i < new_nd->n; i++) {
        new_nd->keys[i] = nd->keys[split + 1 + i];
        new_nd->ptrs[i] = nd->ptrs[split + 1 + i];
        ((BPNode *)new_nd->ptrs[i])->parent = new_nd;
    }
    new_nd->ptrs[new_nd->n] = nd->ptrs[nd->n];
    if (new_nd->ptrs[new_nd->n])
        ((BPNode *)new_nd->ptrs[new_nd->n])->parent = new_nd;

    nd->n = split;
    new_nd->parent = nd->parent;
    return new_nd;
}

/* 向内部节点 nd 的位置 idx 处插入键和右子指针 */
static void insert_into_internal(BPNode *nd, int idx, int key, BPNode *right) {
    for (int i = nd->n; i > idx; i--) {
        nd->keys[i] = nd->keys[i - 1];
        nd->ptrs[i + 1] = nd->ptrs[i];
    }
    nd->keys[idx] = key;
    nd->ptrs[idx + 1] = right;
    nd->n++;
}

/* 向父节点插入上提的键，必要时递归分裂 */
static void insert_into_parent(BPNode *left, int key, BPNode *right) {
    if (left->parent == NULL) {
        /* left 是根节点，需要创建新根 */
        BPNode *new_root = make_node(false);
        new_root->keys[0] = key;
        new_root->ptrs[0] = left;
        new_root->ptrs[1] = right;
        new_root->n = 1;
        left->parent = new_root;
        right->parent = new_root;
        root = new_root;
        return;
    }

    BPNode *parent = left->parent;
    int idx = lower_bound(parent, key);

    if (parent->n < MAX_KEYS) {
        insert_into_internal(parent, idx, key, right);
        right->parent = parent;
        return;
    }

    /* 父节点也满了，先临时插入再分裂 */
    insert_into_internal(parent, idx, key, right);
    right->parent = parent;

    int promote_key;
    BPNode *new_internal = split_internal(parent, &promote_key);
    insert_into_parent(parent, promote_key, new_internal);
}

/* -------- 插入 -------- */
void bpt_insert(int key, void *value) {
    /* 空树：创建根叶子 */
    if (!root) {
        root = make_node(true);
        root->keys[0] = key;
        root->ptrs[0] = value;
        root->n = 1;
        return;
    }

    BPNode *leaf = bpt_find_leaf(key);
    int pos = lower_bound(leaf, key);

    /* 键已存在，更新值 */
    if (pos < leaf->n && leaf->keys[pos] == key) {
        leaf->ptrs[pos] = value;
        return;
    }

    /* 在叶子中插入新键 */
    for (int i = leaf->n; i > pos; i--) {
        leaf->keys[i] = leaf->keys[i - 1];
        leaf->ptrs[i] = leaf->ptrs[i - 1];
    }
    leaf->keys[pos] = key;
    leaf->ptrs[pos] = value;
    leaf->n++;

    /* 未超过容量，无需分裂 */
    if (leaf->n <= MAX_KEYS)
        return;

    /* 分裂叶子并将中间键上提到父节点 */
    int promote_key;
    BPNode *new_leaf = split_leaf(leaf, &promote_key);
    insert_into_parent(leaf, promote_key, new_leaf);
}

/* -------- 范围查询 -------- */
/* 返回 [lo, hi] 范围内的键数量（利用叶子链表顺序扫描） */
int bpt_range_count(int lo, int hi) {
    BPNode *leaf = bpt_find_leaf(lo);
    if (!leaf) return 0;

    int count = 0;
    int i = lower_bound(leaf, lo);

    while (leaf) {
        for (; i < leaf->n; i++) {
            if (leaf->keys[i] > hi)
                return count;
            count++;
        }
        leaf = (BPNode *)leaf->ptrs[ORDER];  /* 沿叶子链表前进 */
        i = 0;
    }
    return count;
}

/* -------- 中序打印（调试用） -------- */
void bpt_print_leaves(void) {
    if (!root) {
        printf("(empty tree)\n");
        return;
    }
    BPNode *cur = root;
    while (!cur->is_leaf)
        cur = (BPNode *)cur->ptrs[0];

    while (cur) {
        printf("[");
        for (int i = 0; i < cur->n; i++) {
            if (i > 0) printf(",");
            printf("%d", cur->keys[i]);
        }
        printf("] -> ");
        cur = (BPNode *)cur->ptrs[ORDER];
    }
    printf("NULL\n");
}

/* -------- 树形打印 -------- */
static void print_tree(BPNode *nd, int depth) {
    if (!nd) return;
    for (int i = 0; i < depth; i++) printf("  ");
    printf("%s[", nd->is_leaf ? "L" : "I");
    for (int i = 0; i < nd->n; i++) {
        if (i > 0) printf(",");
        printf("%d", nd->keys[i]);
    }
    printf("]\n");
    if (!nd->is_leaf) {
        for (int i = 0; i <= nd->n; i++)
            print_tree((BPNode *)nd->ptrs[i], depth + 1);
    }
}

void bpt_print_tree(void) {
    print_tree(root, 0);
}

/* -------- 测试 -------- */
int main(void) {
    int test_keys[] = {10, 20, 5, 15, 25, 30, 35, 40, 45, 50,
                       3, 7, 12, 18, 22, 28, 33, 38, 43, 48};
    int n = sizeof(test_keys) / sizeof(test_keys[0]);

    printf("=== B+tree Insert Test (order=%d) ===\n", ORDER);
    for (int i = 0; i < n; i++) {
        bpt_insert(test_keys[i], (void *)(long)test_keys[i]);
        printf("Insert %2d => leaves: ", test_keys[i]);
        bpt_print_leaves();
    }

    printf("\n=== Tree Structure ===\n");
    bpt_print_tree();

    printf("\n=== Search Test ===\n");
    for (int k = 0; k <= 55; k += 5) {
        void *val = bpt_search(k);
        if (val)
            printf("  search(%2d) = %ld\n", k, (long)val);
        else
            printf("  search(%2d) = NOT FOUND\n", k);
    }

    printf("\n=== Range Count [10, 35] ===\n");
    printf("  count = %d\n", bpt_range_count(10, 35));

    return 0;
}

这份实现共约 250 行，涵盖了 B+tree 的核心操作。编译和运行：

gcc -O2 -Wall -o bptree bptree.c && ./bptree

九、性能基准：B-tree 与红黑树在磁盘访问模式下的对比

为了量化 B-tree 相对于平衡二叉树的优势，我们设计一个模拟磁盘访问模式的基准测试。核心思想：每次”访问”一个节点时计为一次 I/O 操作，统计完成相同操作集所需的总 I/O 次数。

9.1 测试设计

数据量: N = 10^4, 10^5, 10^6, 10^7
操作: 随机查找 10000 次
B-tree 阶数: m = 128 (模拟 4 KB 页，每个键+指针约 32 字节)
红黑树: 标准实现（每个节点 1 次 I/O）

9.2 理论 I/O 次数

9.3 考虑缓存效应

实际运行中，B-tree 的优势更大，因为：

1. 热节点缓存：B-tree 的上层节点（尤其是根节点和第二层）几乎总是在缓存中，实际 I/O 次数可能只有 1-2 次。而红黑树的路径更长，缓存命中率更低。

2. 预取友好：B-tree 节点内的键连续存储，CPU 缓存行预取有效。红黑树的节点分散在内存中，几乎每次指针追踪都会导致缓存未命中。

3. TLB 压力：B-tree 节点大小与页对齐，TLB 效率高。红黑树的小节点会造成更多 TLB 缺失。

9.4 模拟实验代码思路

/* 模拟磁盘 I/O 的计数器 */
static long io_count = 0;

void *disk_read(void *page) {
    io_count++;           /* 每次读页计一次 I/O */
    return page;          /* 实际上数据已在内存 */
}

/* B-tree 查找时，每访问一个节点调用 disk_read */
/* 红黑树查找时，每访问一个节点调用 disk_read */
/* 比较两者的 io_count 即可 */

实测结果与理论分析一致：当数据量达到 10^6 及以上时，B-tree 的 I/O 次数约为红黑树的 1/6 到 1/7。

十、工业级 B-tree 变体：InnoDB、PostgreSQL、SQLite

10.1 InnoDB（MySQL）

InnoDB 使用的是聚簇 B+tree（Clustered B+tree）：

• 主键索引：叶子节点直接存储完整行数据。主键的物理顺序与逻辑顺序一致。
• 二级索引：叶子节点存储 (索引列值, 主键值)。查找需要先在二级索引上找到主键，再回到主键索引取行（“回表”操作）。
• 页大小：默认 16 KB，可配置为 4/8/16/32/64 KB。
• 页分裂策略：不是简单的 50/50 分裂，而是根据插入模式自适应调整分裂点，减少空间浪费。
• Change Buffer：对非唯一二级索引的修改先缓存在 change buffer 中，延迟合并到索引页，减少随机 I/O。

10.2 PostgreSQL

PostgreSQL 的 B-tree 实现（nbtree）有几个独特之处：

• Lehman-Yao 算法：使用高并发友好的 Lehman-Yao B-link tree 变体。每个节点有一个”右链接”指针，允许在分裂过程中无需持有父节点的锁，从而提高并发度。
• 去重（Deduplication）：PostgreSQL 13 引入，对于有重复键的索引，将相同键的多个行指针压缩存储为一个”posting list”，显著减少索引大小。
• HOT（Heap-Only Tuple）更新：如果更新没有修改索引列，可以避免更新索引，大幅减少写放大。
• 页大小：固定 8 KB（编译期决定，修改需要重新编译）。

10.3 SQLite

SQLite 的 B-tree 实现最接近教科书定义：

• 表使用 B+tree：以 rowid 为键，叶子节点存储行数据。
• 索引使用 B-tree（注意，不是 B+tree）：键同时出现在内部节点和叶子节点。这样做是因为索引只需要判断键是否存在，不需要范围扫描。
• 溢出页：当一条记录太大，无法放入一个页时，超出部分存储在溢出页链表中。
• 自动清理：SQLite 的 VACUUM 命令会重建整个数据库文件，相当于对所有 B-tree 做一次批量重新加载。
• 页大小：默认 4 KB，可配置为 512 到 65536 字节。

10.4 特性对比表

十一、工程实践中的陷阱与经验

在实际系统中使用 B-tree 索引时，有许多容易踩的坑。以下是我在工作中总结的经验清单：

11.1 常见陷阱对照表

11.2 主键选择的深层影响

B+tree 的聚簇索引意味着行数据按主键顺序物理存储。这个设计决策产生了深远的影响：

自增 ID 的好处： - 新数据总是追加到 B+tree 的最右叶子，几乎不会触发中间页的分裂。 - 写入模式接近顺序写，对 HDD 和 SSD 都友好。 - 页空间利用率高（接近 100%）。

随机 UUID 的问题： - 新数据随机插入到 B+tree 的任意叶子，导致大量随机 I/O。 - 频繁的页分裂使平均页填充率降至约 69%（理论极限为 ln(2) ≈ 0.693）。 - 缓冲池命中率降低，因为热点分散。

折中方案：UUIDv7（基于时间戳的有序 UUID）保留了分布式系统中全局唯一的优势，同时具有近似自增的特性，是目前推荐的方案。

11.3 页填充因子（Fill Factor）

大多数数据库允许配置页填充因子（PostgreSQL: fillfactor，InnoDB: MERGE_THRESHOLD）。默认情况下，分裂后的页大约 50% 满。通过预留空间可以减少后续更新导致的分裂，但会增加索引大小。

经验法则： - 读多写少的表：fillfactor = 90-100% - 频繁更新的表：fillfactor = 70-80% - 追加写入的表（如日志表）：fillfactor = 100%（因为不会有中间插入）

十二、个人思考与总结

12.1 B-tree 的地位是否被动摇了

近年来，LSM-tree（Log-Structured Merge-tree）凭借更低的写放大和更高的写入吞吐，在很多场景中替代了 B-tree。RocksDB、LevelDB、Cassandra、HBase 等系统都以 LSM-tree 为核心。但我认为 B-tree 的地位不会被根本动摇，原因有三：

第一，B-tree 的读性能是确定性的（O(log_B N) 次 I/O，无需额外的合并开销），而 LSM-tree 的读性能取决于层数和 bloom filter 的假阳性率，在最坏情况下可能需要查询多个 SSTable。对于 OLTP 场景中的点查询，这种确定性至关重要。

第二，B-tree 的空间效率更高。LSM-tree 在 compaction 过程中需要临时存储新旧版本的数据，空间放大可能达到 2 倍甚至更多。B-tree 原地更新，空间放大接近 1。

第三，B-tree 的实现复杂度远低于 LSM-tree。LSM-tree 需要处理 compaction 策略选择、write stall、读放大优化等一系列复杂问题。B-tree 的核心逻辑（查找、插入、分裂、合并）加起来不过几百行代码。

当然，最佳选择取决于工作负载。写入密集型且能容忍读放大的场景（如时序数据库、日志系统），LSM-tree 是更好的选择。读写混合的通用 OLTP 场景，B-tree 仍然是默认答案。

12.2 硬件演进对 B-tree 的影响

随着 NVMe SSD 的普及和持久化内存（Persistent Memory，如 Intel Optane）的出现，B-tree 的参数空间正在发生变化：

• 更小的节点大小：在低延迟存储上，减小页大小（例如从 16 KB 减到 4 KB 甚至 512 字节）可以减少写放大，同时由于随机读延迟已经足够低，不会显著增加查找开销。
• 更高的并发度：NVMe SSD 支持数万个并发 I/O 队列，传统的单线程 B-tree 遍历无法充分利用这一能力。新的研究方向（如 BzTree、FAST+FAIR 等）探索如何让 B-tree 在高并发场景下更好地扩展。
• 硬件原子性：部分新硬件支持 8 字节或 16 字节的原子写入，这可以简化 B-tree 的崩溃恢复逻辑，减少对 WAL 的依赖。

12.3 学习 B-tree 的建议

如果你正在学习 B-tree，我的建议是：

1. 先手写一遍：不要只看代码，亲手实现一遍插入和分裂操作。本文提供的 C 实现可以作为起点。
2. 用真实数据库验证直觉：打开 MySQL 的 innodb_monitor 或 PostgreSQL 的 pgstattuple 扩展，观察实际的页分裂次数、空间利用率等指标。
3. 理解 trade-off：B-tree 不是银弹。理解它与 LSM-tree、跳表、哈希索引等结构的优劣互补，才能在工程中做出正确的选择。
4. 阅读工业级源码：boltdb（Go）、SQLite（C）、PostgreSQL 的 nbtree 是三个从简单到复杂的优秀参考。

12.4 结语

B-tree 是计算机科学中少有的”50 年不过时”的数据结构。它的设计优雅地匹配了存储硬件的物理特性，而随着硬件的演进，B-tree 本身也在不断进化。理解 B-tree 不仅是理解数据库索引的起点，更是理解”软件如何与硬件对话”的一个绝佳窗口。

希望本文能帮助你建立起对 B-tree 从理论到实践的完整认知。如果你有任何问题或发现本文有不准确之处，欢迎交流讨论。

参考资料

1. Bayer, R. & McCreight, E. (1972). Organization and Maintenance of Large Ordered Indexes. Acta Informatica.
2. Comer, D. (1979). The Ubiquitous B-Tree. ACM Computing Surveys.
3. Graefe, G. (2011). Modern B-Tree Techniques. Foundations and Trends in Databases.
4. boltdb 源码：https://github.com/boltdb/bolt
5. SQLite B-tree 文档：https://www.sqlite.org/btreemodule.html
6. MySQL InnoDB 源码：https://github.com/mysql/mysql-server
7. PostgreSQL nbtree 源码：https://github.com/postgres/postgres/tree/master/src/backend/access/nbtree

上一篇: 红黑树 vs AVL 下一篇: B+tree 与 LSM-tree

相关阅读: - 文件系统的树 - 查询优化器