前言 #

首先对这门课的 lab 做一下总结：

• P1 要求实现一个 buffer pool 管理器，作为读写磁盘的中介
• P2 实现 B+ 索引
• P3 实现查询算子与优化器
• P4 实现 MVCC 机制，用于版本回溯

P3、P4 更侧重对框架代码与设计架构的理解，后期我使用了 AI 辅助生成代码，coding 并不难

相比之下，P1 引入了 RAII 对象 PageGuard ，P2 又引入了复杂的并发情境

这些 Modern C++ 的理念是我觉得最受用的东西，因此我选择 P2 作为整个课程的回顾

一 #

作为存储在磁盘上的数据结构，B+ 树以页面作为存储单元，下面称为 Page

这种设计，要求设计对象成员时，必须精确到字节，这里倒不是难点
真正的难点在于，我们通过 P1 的存储 API 进行磁盘交互，必须准确维护 page 对应的闩锁与引用数目

这种算是简单重复的脏活累活，如果每行代码都要自己写，那就太复杂了

因此我们选用 P1 提供的 RAII 对象 PageGuard 自动管理资源释放，大大减少了思维负担

我们本应该事无巨细地手动管理 page 的一切变量，而现在只需考虑 PageGuard 的生命周期即可

这是针对并发读写的第一层设计，简化资源管理

二 #

存储的问题简化了，下面针对树型结构进行讨论

查询时，我们只需要自顶向下访问，因此找到目标 Page 时不需要多余操作

然而，增删内容时，可能发生内部节点的分裂与合并，这就需要自底向上依次处理

因此我们需要一个数据结构 context 来维护访问路径的 PageGuard，用 deque 维护即可

我们把 context 传入参数，进行操作时就可以得知上下文了

这是针对读写路径的第二层设计，简化状态检测

三 #

到这里，我们才进入 B+ 树的正题，实验要求实现三个功能：Insert，Delete，Search

先从插入讲起，抽象为三个步骤：

1. 找到 key 对应的 LeafPage
2. 插入 Page 内部
3. 如果分裂，递归向上插入 page_id

可以发现操作分为两种，针对 Page 内容的，与针对 B+树 整体结构的

因此 Page 内部的操作，如二分查找 value、插入 key-value 等相对独立的操作函数，放在 Page 类的内部即可

查找和插入是相互独立的，因此分开实现，从而在后面的功能复用 search 功能

那么我们在这里将操作分为三类：

1. 有关页面查找的过程，传递 page_id 为参数，将路径存入 context
2. 涉及结构处理的过程，使用 context 获取 guard，不传递 page 参数，逐个处理 context 中的 Page
3. 对于页面内部的过程，使用 page* 传递具体指针，进行数据读写

根据操作的行为模式进行分类后，再逐个实现就方便了

同时将 Page 的处理函数进行二次封装，增加可读性

四 #

到这里，我们完成了函数特性的设计，对每个 function 要做什么事情有了很好的规范，下面我们考虑底层处理的细节

Search 功能很简单，向下递归地二分查找即可

Search(key)
  leaf_page = FindLeafPage(key, root_page, context)
  return GetValue(leaf_page, key)

FindLeafPage(key, now_page, context)
  context->PushBack(now_page)
  if (now_page is LeafPage) 
    return
  next_page = FindNextPageId(now_page, key)
  FindLeafPage(key, next_page, context)

而 Insert 需要考虑分裂节点的问题，一般用 vector 临时存储 KV 对，插入到有序 vector，然后将 vector 分配到两个 Page 即可

注意到 插入 和 重分配 是两个独立的操作，因此又可以将 Redistribute 操作分离出来，在 Remove 时进行复用

Insert(key, value) 
  FindLeafPage(key, root_page, context) 
  # 此时 LeafPage 就在 context 末尾
  return InsertFromBottomLeaf(key, value, context)
  
InsertFromBottomLeaf(key, value, context)
  now_page = context.Pop()
  if (now_page is full)
    temp_vector = GetVector(now_page)
    temp_vector = Append(temp_vector, key-value)
    new_split_page = NewLeafPage()
    new_split_key = Redistribute(temp_vector, now_page, new_split_page)
    InsertFromBottomInternal(key, new_split_key, context)
  else 
    InsertLeaf(now_page, key, value)

InsertFromBottomInternal() 
  ...

Redistribute(vector, page1, page2)
  将 vector 平分后，分别插入 page1 和 page2 即可、
  注意 next_page_id 指针的设置

五 #

再解决 Remove 的问题，当页面内容少于阈值时，进行合并操作 Merge

与谁合并呢？我们只需要找到一个相邻的 Page 即可，找前驱或者后继

此时我们需要获取 context 上一层的父节点，寻找相邻 Page，可以证明一定有这样的相邻 Page

那么这里的 Merge 分两种情况：

1. 可以重新分配内容，直接复用 Redistribute 即可
2. 否则只能合并到同一个节点，此时需要向上进行递归 Remove，同时释放 Page 空间

Remove 的实现框架与前面一致，只不过需要更多的辅助函数

六 #

我们已经完成了基本功能，下面考虑一些边界条件：

1. 空树：在外层函数进行特判
2. 合并/分裂到根节点：递归函数中，检查 context 是否为空，从而判断是否要更新根节点

这里要注意的是对 root 状态的保护，在 Remove 之后需要及时保证 Empty 检查的结果正确

七 #

现在讨论迭代器的实现

我们用 page_id 与 key_index 表示迭代器状态，以此重载运算符，通过 next_page_id 指针进行 Leaf 间的移动

但是一个 iterator 必须长期持有 page 的读锁，才能保证内容安全，因此我们用 read_page_guard 来代替 page_id

八 #

最后我们来审视并发控制

context 中必须按照自顶向下的顺序释放 PageGuard，方便其他线程及时进入，通过调整 context 的析构函数来实现

每次我们都会获取 head_page 的写锁，属于悲观锁机制

可以采用乐观锁机制进行优化，因为发生树结构变化的操作非常少，我们可以先一路获取读锁，只在 Leaf 用写锁，如果检查到有结构变化，再回来一路获取写锁

也可以采用墓碑机制延迟 Remove，定期清理

结束 #

没有做优化的情况下，我的提交在 24fall 的 leaderboard 上排在 7/168

一方面是人少，另一方面，我觉得在反复推翻尝试后，迭代出的顶层设计，更有利于思考线程间的交互，也就自然写出高质量的代码，这是我从本实验中收获的实践