起手就是一个错误的设计

我开始写 B+Tree 是因为一个数据库项目，用 Rust 实现，参考了 QuillSQL 和 CMU 的 Bustub。想法很简单：写一棵树，能插能查，有什么难的？

然后我就写下了第一版数据结构：

struct Node {
    key: String,
    value: String,
    children: Vec<Node>,
}

一个 key，一个 value，一堆 children。写完我还觉得挺合理的——你看，节点有键有值有子节点，一棵树不就是这样吗？

不是。大错特错。

B+Tree 根本不是这么玩的。内节点和叶节点完全是两种东西：内节点存的 key 是用来分隔范围的，不存实际数据；叶节点存的 key 才映射到真正的数据行。而且内节点的 key 不止一个——一个内节点可以存多个分隔 key，每个 key 指向一个子节点范围。

我那个一个 key 一个 value 的设计，连 B+Tree 的基本定义都没对上。

修正第一版：让结构体说真话

发现问题之后我把设计改成了这样：

enum NodeValue {
    Data(String),           // 叶节点：存实际数据
    Pointer(Box<Node>),     // 内节点：指向子节点
}

struct Node {
    keys: Vec<String>,
    values: Vec<NodeValue>,
    next: Option<Box<Node>>, // 叶节点链表
}

这次 keys 和 values 都是 Vec 了，value 用枚举区分数据和指针。叶节点通过 next 连成链表，方便范围扫描。

看起来不错。然后我写了 tree.insert("hello")——Rust 编译器直接炸了。

它期望的是 Value 类型，不是 &str。为了搞定这个我掉进了 From/Into trait、孤儿规则、covered type 和 uncovered type 的坑里。我甚至为此单独写了一篇文章。就因为我想要一个结构体同时表示叶节点和内节点。

但更大的问题还在后面。

根本问题：节点不是内存里的玩具

上面这个设计有一个致命假设：所有节点都在内存里。内节点通过 Box<Node> 直接持有子节点的内存指针。这在玩具实现里没问题，但在真实数据库里完全行不通。

B+Tree 的节点本质上是数据库页（page）。这些页可能在内存里，也可能在磁盘上。哪个页在哪儿、什么时候读进来、什么时候刷回去——这些是 Buffer Pool 的事，不是 B+Tree 自己的事。

所以内节点不能持有另一个节点的内存指针。它只能持有一个 page_id。

这意味着设计必须推倒重来。

第三次迭代：面向页的设计

内节点需要指向子节点所在的数据页：

struct InnerPage {
    keys: Vec<Key>,
    children: Vec<PageId>,
}

叶节点需要指向数据所在的精确位置——不光是哪个页，还要知道页里的哪个槽位（slot）：

struct RecordId {
    page_id: PageId,
    slot: u16,
}

struct LeafPage {
    keys: Vec<Key>,
    records: Vec<RecordId>,
    next_page_id: Option<PageId>,
}

每次要读一个内节点或叶节点，不是直接拿指针，而是通过 Buffer Pool：

// 从 buffer pool 拿一页
let guard = buffer_pool.fetch_page(page_id)?;

// 把原始字节转换成内节点或叶节点
let inner = InnerPage::from_bytes(guard.data());

// 用完 unpin
drop(guard); // guard drop 时自动 unpin

页大小是固定的 8192 字节（PAGE_SIZE）。Buffer Pool 决定一页是在内存的某个 frame 里还是需要从磁盘读。你的 B+Tree 代码不关心这个——它只跟 page_id 打交道。

内节点 key 从哪来？

设计到这一步，还有一个关键问题：内节点的 key 是怎么定的？

直觉上你可能觉得 key 是 B+Tree 自己选的。但实际上，内节点的 key 来自外部——具体来说，来自叶节点分裂（split）的过程。

当叶节点满了需要分裂时，分裂过程会从中取出一个 key 提升（promote）到父节点。这个被提升的 key 就成了内节点里分隔两个子节点范围的边界值。

这个事情在我看到 QuillSQL 的实现之后才彻底搞明白。QuillSQL 的 key 类型是这样的：

pub struct Tuple {
    pub schema: SchemaRef,
    pub values: Vec<ScalarValue>,
}

不是简单的 String，而是一个带着 schema 和 Vec<ScalarValue> 的元组。为什么？

因为数据库里的 key 可以是一个组合键——比如 (user_id, created_at)。你没法用单个 String 来表示这种复合索引。Tuple 是更通用的抽象，能适应任何索引键的定义。

我在自己的实现里用 String 当 key 其实只是一个占位符。等到要做复合索引或者类型感知的比较操作时，String 就会露馅。

现在的状态

B+Tree 的结构体有了，Buffer Pool 底层能跑——分配页、通过 guard 读写、刷回磁盘。insert 函数还是空的。

剩下来的工作清单：

  1. 二分查找：在节点内找到 key 的插入位置
  2. Buffer Pool 分配：用 buffer pool 分配新页，不走 OS 的 malloc
  3. 分裂逻辑：叶节点满了→分裂→提升 key 到父节点
  4. 锁机制：并发访问时的页级锁
  5. 根节点处理：根节点也可能是叶节点；当根节点也满了，树的高度才增加

总结：三个关键教训

第一，数据结构要反映真实的分工。内节点和叶节点是两种角色，一个结构体硬塞两种语义只会让自己痛苦。在 Rust 里尤其如此——类型系统不会让你蒙混过关。

第二，存储模型决定设计。如果节点是数据库页而不是内存对象，指针就得换成 page_id。这是一个你在写第一行代码之前就必须想清楚的问题。

第三，找参考实现。如果没有 QuillSQL 的代码可以对照，我自己折腾到 key 的设计那块可能还要绕更久。好的参考实现不仅能告诉你"怎么做"，更重要的是告诉你"为什么这么做"。

B+Tree 这个结构从 1970 年代就有了，但真正从头实现一遍，才会理解数据库教科书上那些一笔带过的句子到底在说什么。

本文基于作者在 Rust 数据库项目中使用 QuillSQL 作为参考实现 B+Tree 的经验。如果你想看更多 Rust 系统编程相关的内容，欢迎关注「梦兽编程」公众号。