日常 代码

CMU 15-445 Project #2

Database Index review

Project #2 Database Index

时间跨度：2025-03-18 ~ 2026-07-21（约 16 个月，实际 coding 分散在若干密集时段）

总变更：18 个文件，+1875 / -71 行，15 个 commit

这段时间陆陆续续在做这门 2024 年的课程，从 2025-01-11 完成 P1 Buffer Pool Manager 之后便一直没什么闲暇来做，但至今也算是做完了。 那么按照惯例，本文只作为我思路历程的记录，不涉及代码，只记录我是如何使用递推的思路去实现 B+ Tree，然后提交 Gradescope 一次性通过的。

这次课程 PDF 的内容也是十分丰富和形象，首先介绍了由哈希冲突衍生的布谷鸟哈希等各种哈希方案，引出 HashTable，然后介绍了各种索引：B+ Tree、LSM-Tree、Skip List、Inverted Index 等等，配合绘图阅读起来还是挺有意思的。

哈希虽然看起来有一大堆实现，但哈希冲突本质上是无解的，一般像 HashMap 在每个桶里面用链表去解决，根据场景选择速度快、分散均匀的哈希函数即可。 带哈希索引一般用于 O(1) 的无序高性能场景，例如 Redis、Bloom Filter 等。 非哈希索引中的 B+ Tree 就是本次课程的核心。

B+ Tree 是一个平衡树，简单来说，每个内节点和叶子在初始化时设定 max_size 和半满阈值。 当叶子节点插入后超过 max_size 就会触发向上分裂，如果 root 也分裂了，那么 B+ Tree 树高度 +1。 当叶子节点删除后低于半满阈值就会触发 steal 先尝试从左右兄弟借一个，借不到就会触发向上合并，如果 root 也合并了，那么 B+ Tree 树高度 -1。

本次课程就是实现这样一个 B+ Tree，原课程拆分为了 4 个 Task：

  • Task #1 - B+Tree Pages
  • Task #2 - B+Tree Operations (Insertion, Deletion, and Point Search)
  • Task #3 - Index Iterator
  • Task #4 - Concurrency Control

但是这四个 Task 耦合性是非常高的，建议所有 Task 细节看完之后再开始着手实现。

Project Specification 几个重要概念需要牢记：

  • TreePage 是两种 B+ 树节点的基类
  • InternalPage 内节点派生类，每个实例包含了数个 direct key 和他们指向的下一级 page id
  • LeafPage 叶子节点派生类，每个实例包含了数个实际的 Key-Value

本文将根据实现顺序 Insert->Delete->Iterator 进行讲解，会穿插一些由 AI 转化为 SVG 的个人笔记。 另外，由于本人是用 递推 的方法实现的，也会讲解一下递推过程的状态转移原理，不一定适用所有人。

Pre-knowledge

在写代码之前，需要熟悉一些 C++ Codebase 相关的内容，比如内存布局、reinterpret_cast 等等。

在上次的 Buffer Pool Manager 中，每个内存单元 (frame) 大小都是 4KB，映射到 B+ Tree 就是每个 Page 的内存大小都是 4KB。

Page 头部静态内存布局计算 (0 padding)：

  • TreePage: sizeof(page_type_(4B) + size_(4B) + max_size_(4B)) = 12B
  • InternalPage: sizeof(TreePage) = 12B
  • LeafPage: sizeof(TreePage + next_page_id_(4B)) = 16B 其中 next_page_id 是实现 iterator 的相关字段

Page 动态内存布局计算每个节点能容纳多少插槽 (slot_cnt) 的方法就是 (4096B - sizeof(Page)) / sizeof(KeyType + ValueType)。

在没彻底搞懂这个逻辑之前，不要试图在 Page 上面添加任何拓展字段

Frame <—> Page 是互转的，reinterpret_cast 就是桥梁。 Frame 是一个 4KB 大小的 char[]，读取到内存之后就是一个可以被 reinterpret_cast 解释成 Page 对象的内存模型。 把对象操作理解成 memset 就行，期间没有任何的序列化操作或者压缩操作，内存模型就是存储序列。

搜索数据库页相关的定长压缩技术也能看到一些有意思的东西

最后看一眼 B+ Tree 的声明和一个构造示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

template <typename KeyType, typename ValueType, typename KeyComparator>
class BPlusTree {
  using InternalPage = BPlusTreeInternalPage<KeyType, page_id_t, KeyComparator>;
  using LeafPage = BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>;

 public:
  explicit BPlusTree(std::string name, page_id_t header_page_id, BufferPoolManager *buffer_pool_manager,
                     const KeyComparator &comparator, int leaf_max_size = LEAF_PAGE_SLOT_CNT,
                     int internal_max_size = INTERNAL_PAGE_SLOT_CNT);

  // Returns true if this B+ tree has no keys and values.
  auto IsEmpty() const -> bool;

  // Insert a key-value pair into this B+ tree.
  auto Insert(const KeyType &key, const ValueType &value) -> bool;

  // Remove a key and its value from this B+ tree.
  void Remove(const KeyType &key);

  // Return the value associated with a given key
  auto GetValue(const KeyType &key, std::vector<ValueType> *result) -> bool;

  // Return the page id of the root node
  auto GetRootPageId() const -> page_id_t;

  // Index iterator
  auto Begin() -> INDEXITERATOR_TYPE;

  auto End() -> INDEXITERATOR_TYPE;

  auto Begin(const KeyType &key) -> INDEXITERATOR_TYPE;
}

// create b+ tree
BPlusTree<GenericKey<8>, RID, GenericComparator<8>> tree("foo_pk", page_id, bpm, comparator, 2, 3);

注意 InternalPage 的 ValueType 不是泛型而是 page_id_t，因为内节点仅指向下一个节点。 而 LeafPage 的 ValueType 就是 RID (Record ID) 一个指针指向真实的 Database Row 的储存位置，这个也是我们常说的数据库隐藏的 rowid 字段。 GenericKey 就是一个抽象的 key 实现，可以兼容长度 8B 的各种数据类型，例如 int64 和 string。

Insert

Insert 主要是实现叶子节点和内节点的插入与分裂（就不展示具体函数签名了）：

  • LeafPage::BalancedInsert & InternalPage::BalancedInsert
  • LeafPage::InsertAndSplit & InternalPage::InsertAndSplit

latch crabbing 并不算复杂，按螃蟹锁逻辑将 PageGuard 推入课程提供的 write_set_ 队列就行。 大部分锁都封装在 PageGuard RAII 模式里面了，具体会在最后章节介绍，我这里实现的是普通版本，不是课程优化建议的乐观锁，感兴趣的也可以实现乐观锁。

实现的过程中可以自由写测试，参考其他测试案例即可，记得最后 delete bpm; 否则会报内存泄漏。

BalancedInsert

刚开始写可以先尝试实现 BPlusTree::Insert 简单插入不分裂。 在内节点和叶子节点定义一个 BalancedInsert 实现二分查找快速插入即可，处理 root 作为 LeafPage 的一些边界情况，保持有序即可。

注意 BalancedInsert 都是在节点内操作的，不涉及外部节点，也不用更新 direct key，不影响 B+ Tree 的不变性。

InsertAndSplit

建议先不要用 zero-copy 实现，边界情况比较麻烦

接下来介绍如何使用递推思路去实现插入和向上分裂。

举个例子，这是一个满叶子节点的树，这里展示的数值都是 key 值：

1
2

            6 (page3)
1 2 3 4 (page1) | 6 7 8 9 (page2)

插入 5 之后：

1
2

                    3 | 6 (page3)
1 2 0 0 (page1) | 3 4 5 0 (page4) | 6 7 8 9 (page2)

发生了三个步骤：

  1. 叶子节点 page1 拆成了 page1 + page4
  2. 叶子节点 page4 first key 上升作为内节点的 new direct key
  3. 内节点 page3 更新指向新的 page4，每棵树理应符合各自 key range，保持树的不变性

分裂时程序需要遵循一个约定，左子树永远是旧子树，右子树永远是新的子树，这样父节点才能正确处理。

BPlusTreePage::GetMinSize 可以自由定义，但是一定要保证分裂后 MinSize <= size <= MaxSize，保持树的不变性

由此可以推导状态 opt=(direct_key, left_page_id, right_page_id)：

分裂状态转换图示

这里是我写的一个测试，可以帮助理解这个过程：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95


TEST(BPlusTreeTests, My_TreeInsert_Basic_Test) {
  // create KeyComparator and index schema
  auto key_schema = ParseCreateStatement("a bigint");
  GenericComparator<8> comparator(key_schema.get());

  auto disk_manager = std::make_unique<DiskManagerUnlimitedMemory>();
  auto *bpm = new BufferPoolManager(50, disk_manager.get());
  // allocate header_page
  page_id_t page_id = bpm->NewPage();
  // create b+ tree
  BPlusTree<GenericKey<8>, RID, GenericComparator<8>> tree("foo_pk", page_id, bpm, comparator, 5, 3);

  GenericKey<8> index_key;
  RID rid;
  auto do_insert = [&](int64_t key) {
    int64_t value = key & 0xFFFFFFFF;
    rid.Set(static_cast<int32_t>(key), value);
    index_key.SetFromInteger(key);
    tree.Insert(index_key, rid);
  };
  auto do_delete = [&](int64_t key) {
    int64_t value = key & 0xFFFFFFFF;
    rid.Set(static_cast<int32_t>(key), value);
    index_key.SetFromInteger(key);
    tree.Remove(index_key);
  };

  // Insert 5 items to reach leaf max size
  for (int64_t key = 40; key < 45; key++) {
    do_insert(key);
  }
  std::cout << "========================\n";
  tree.Print(bpm);
  /*
  Leaf Page: 1    Next: -1
  Contents: 40, 41, 42, 43, 44
  */

  do_delete(33);  // delete key not exists
  do_delete(44);  // delete right side
  do_insert(44);
  do_delete(40);  // delete left side
  // tree.Print(bpm);
  do_insert(40);

  // Make root leaf split
  do_insert(45);
  std::cout << "========================\n";
  tree.Print(bpm);
  /*
  Internal Page: 3
  Contents: 1, 43: 2

  Leaf Page: 1    Next: -1
  Contents: 40, 41, 42

  Leaf Page: 2    Next: -1
  Contents: 43, 44, 45
  */

  do_insert(46);
  do_insert(47);
  std::cout << "========================\n";
  tree.Print(bpm);
  /*
  Internal Page: 3
  Contents: 1, 43: 2

  Leaf Page: 1    Next: -1
  Contents: 40, 41, 42

  Leaf Page: 2    Next: -1
  Contents: 43, 44, 45, 46, 47
  */

  do_insert(48);
  std::cout << "========================\n";
  tree.Print(bpm);
  /*
  Internal Page: 3
  Contents: 1, 43: 2, 46: 4

  Leaf Page: 1    Next: -1
  Contents: 40, 41, 42

  Leaf Page: 2    Next: -1
  Contents: 43, 44, 45

  Leaf Page: 4    Next: -1
  Contents: 46, 47, 48
  */

  ...
}

实现简单 Insert 对项目有了大概的了解之后，就可以写 Search 了。

Search 是最简单的函数，实现 B+ Tree Point Search 就行，拿到 ReadGuard 释放父节点，一路往下找到叶子节点就行。

Delete

Delete 是本课程最复杂的操作，虽然看起来和 Insert 差不多，但是 Insert 只需要处理目标叶子节点和上级 +N 内节点就可以了，而 Delete 需要 Steal、Merge 还需要涉及两个兄弟节点的读取和操作。 由于过于复杂，不建议封装函数，直接在 BPlusTree 类里面操作节点就行。

内节点操作关联节点图示：

内节点图示

BalancedDelete 不再赘述，需要注意的是我们删除的是 key 和其对应的右子树。 如果删除后 size < MinSize，就将当前叶子节点设为 “under-filled” 状态，然后进入递推流程开始 Steal 判定 sibling，如果无法 Steal 则进行 Merge。

Delete 状态图示：

删除全流程图示

Steal

进入 Steal 首先获取当前 “under-filled” 节点，搜索其左右子兄弟，有左兄弟就用左边，没有就选择右边。

左右子兄弟还有个方案是根据是否 half-full 去选择，不过略复杂而且不一定有意义

如果可以 Steal，进行两个相邻节点的 Rebalancing，将右子树第一个值移到左子树最后，或者将左子树最后一个值移到右子树开头。

  • 叶子节点 Rebalancing 完成，更新 parent direct key 即可
  • 内节点 Rebalancing 一定要和 parent key 旋转，这是整个 P2 最精髓的部分

内节点旋转示例，按照我的笔记原样粘贴更形象：

1
2
3
4
5

          40 (parent key)   ->           30 (parent key)
0 10 20 30 0 | 0 50 60 0 0  ->  0 10 20 0 0 | 0 40 50 60 0
v  v  v  x 0 | v  v  v 0 0  ->  v  v  v 0 0 | x  v  v  v 0
         ↑ 30的右子树[30,40)
                                              ↑ [30,40)范围不能变，要和parent key旋转

这里的操作就是将 direct key 30 和它的右子树从左节点移到右节点，首先我们知道一个 direct key 两个子树分别只能得出 (-oo,30) [30,+oo) 这两个区间范围，结合 30 和 parent direct key 40 才能得出 30 的右子树最终的范围是 [30,40)。

为了在移动过程中，保持 B+ Tree 的不变性，这里需要用到一个 旋转 特性，把 parent key 置换下来，保证每颗子树区间不变。

最后如果无法 Steal，进入下一步 Merge。

Merge

Merge 是删除流程递推的最后一步。

对于叶子节点：

  1. 把右子树 KV 搬到左子树后面
  2. 删掉上一级内节点的 direct key

对于内节点：

  1. 把右子树 KV 搬到左子树后面
  2. 搬完会发现少了一个 key，需要把 parent direct key 拉下来放中间
  3. 删掉上一级内节点的 direct key
  4. 回收右子树，一定要 Drop 之后再 DeletePage

DeletePage 对于 pin_count > 0 会静默返回的，建议改成直接抛异常，更好排查问题

到这里基本上就可以完成所有 remove tests 了，后续再讲 concurrent 相关的问题。

Iterator

首先科普一下原生的 C++ Iterator 协议，Iterator 可以让一个类实现鸭子类型（duck typing）接口，从而让 for-loop 可以直接迭代这个类的实例。 类似 Python 等各个语言的迭代器协议，C++ 主要实现 begin() 和 end()，大多数情况都会实现一个迭代器类去承接迭代过程中的状态变化（很少会直接返回 this）。

本次课程的 B+ Tree Iterator 也是参考原生协议做的：

  • Begin(): 往下搜索最左边的叶子，创建迭代器
  • End(): 无效迭代器，用于终止迭代（这个和标准协议一致，比如我们常用的 it != x.end()）
  • INDEXITERATOR_TYPE: 迭代器类，需要持有 ReadGuard，同时维护当前迭代中叶子节点对应的索引位置，迭代完当前叶子就找下一个叶子

叶子节点链表在 Insert & Remove 中维护就可以，其实做起来没有想象中复杂，就是在触发分裂、合并的时候，处理相邻节点关联就行。

Concurrency & Tests

写完 B+ Tree 所有操作之后，理论上除了 MixTest 其他 tests 都可以通过了。

接下来就是逐个分析 MixTest 出现的并发问题：

CheckedWritePage failed to bring in page 407

排查思路：没法获取 PageGuard -> replacer 无法淘汰 frame -> SetEvictable 有并发问题。

最后确实发现了我的 BPM 写法存在的问题，主要在 PageGuard Drop 回收的时候要用 pin_count_.fetch_sub(1) 去减少引用计数，如果计数归 0 要上锁进行 double-check SetEvictable，避免另一个线程创建了新的 PageGuard。（课程注释写了两个 VERY careful 警告是有道理的）

Expected equality of these values

MixTest 出现了断言错误，很明显数据脏了，锁有问题。

这个地方出动了 DeepSeek 找到了问题所在，在 GetValue 中 GetRootPageId 是我单独写的方法，方法返回后 header page ReadGuard 已经被释放了，再去获取 root 对应 ReadGuard 有个时差，导致了这个 TOCTOU（time-of-check-time-of-use）竞态。

算是一个小失误吧，警告我们不要提前封装代码。

其他地方的并发大多数都没什么问题，因为 B+ Tree 本身的设计就足够简洁，管理好了父节点的写锁基本上就没什么问题。

Submit

Submit 的时候遇到一个究极无语的大坑，来说结论：gradescope sign 的时候 Affiliation (School/Company): none 这样填会导致 Gradescope 超时。

本以为超时是代码问题，卡了足足两天在尝试修复。 后来查了 相关 Issue 里面提到可以提交 Original file 验证一下，于是我试了下还是超时… 很明显就是 sign 有问题了，把 Affiliation (School/Company): none 的 none 改成其他字符就可以了 😡

最后美美提交，一次性 AC：

My Benchmark

这个比分在中游水准吧，不过我已经很满足了。

这个时间点去做 2024 年的课程，gradescope 剩余的提交时间只有 5 个月了，剩下的 P3 Query Execution 和 P4 Concurrency Control 说实话都挺有意思的。 但是我太懒了，随缘做吧。

之前发布 P1 的博文之后，陆陆续续收到了好几个人的来信，希望这篇文章也能帮助到更多的人吧！

最近察觉到了一个事情，就是性能优化是一个非常广泛的领域，仅盯指标是很难去想象卡点在哪里的。

更好的方向，或许是学习更多不同的基建原理，各种 IO、memory、disk 相关的优化，各种背压机制，将各种系统性原理转化为对性能分析的观察力。

CC BY-NC-SA 4.0 License