CMU 15-445 Bustub Project 2 - B+Tree - Note

前言

一个 Lab 怎么能这么难...

Task 2 的难度简直了，给我写出玉玉症了。导致我后面基本上手写很少，都在指挥 Agent（虽然我自认为还算是 fine-grained 了），不过也不是什么光彩的事情。

所以鉴于我也是一知半解地写完，所以这份笔记大概就是罗列一下我印象深刻的一些点，而不是说系统地、线性地梳理完各个 Task 并阐明具体实现。

Task 1

虽然说是 Task 1，不过一些不得不理清楚的概念也会在这里讲清楚。

internal page 的键和孩子对应关系

• 第一个 key 无效，但第一个 child 有效；
• 查找等于分隔键时走右侧孩子
• 因此，int KeyIndex(const KeyType& key) 函数，不能照搬同一种二分逻辑：
  • internal page 需要 std::upper_bound() 之后 -1
  • leaf page 直接 std::lower_bound() 即可

tombstone 让「逻辑删除」和「物理删除」分离

• 记删除不一定减少 GetSize()；
• 缓冲区满了（GetTombstoneSize() == TOMBSTONE_CNT）才清理最旧槽位（覆盖）。

Task 2

header page 和 root page 的区别

header_page_id_ 指向保存树元信息的页，其中的 root_page_id_ 才指向树根。

• 空树仍然可以有 header；
• 根也可能是叶页。

Init() 要传树配置的大小

默认参数不能直接用，要因节点种类而异的。

用 SplitResult 表达分裂结果

将左页号、提升键、右页号放在一个结构体里，减少散落的临时变量。

提升键永远对应的是右边的（即下标是一致的）

叶页分裂和内部页分裂的区别

• 叶页的分隔键来自右页，记录仍保留在叶子；
• 内部页要把分隔键提升给父页，还要正确处理右页第一个无效 key（即 IsTombstone()

内部页借位、合并必须经过父页分隔键

因为这两个操作必然涉及到父页的改变，所以属于悲观的。

搬入的 tombstone 一律视为更新，同时保留各自内部顺序

按 spec，接收页原有的待删除记录应先处理，搬入页的待删除记录后处理。

因此，MergeFrom(right) 的处理方式是：

1. 先计算左右两页的墓碑总数。超过缓冲区容量时，提前处理接收页队首最旧的几个墓碑，给右页的墓碑腾出空间。
2. 一次性压缩接收页的 key/value 数组，并建立旧下标到新下标的映射，修正剩余墓碑的下标。避免反复 EraseAt()，把数组移动好多遍。
3. 把右页的记录追加过来，再按右页原来的墓碑队列顺序追加标记；下标统一加上接收页清理后的长度。

最终队列就是「接收页剩余的墓碑 → 搬入页的墓碑」，双方内部的先后顺序都保留。不能按 key 的顺序重新登记墓碑，因为键的大小和删除时间没有关系。

借位只搬一个条目，MoveEntryTo() 会先记录它是否已删除，再搬到接收页；如果是墓碑，就调用接收页的 RemoveAt()，把它登记为最新的待删除记录。

根节点和单孩子父页是特殊情况

• 根允许不足普通节点的最低大小；
• 需要更新 header：根叶页删空、内部根只剩一个孩子（upfloat）。

Task 3

迭代器跨页不只是跳到下一页

还要跳过 tombstone、空页、整页都已删除的情况。

增加 prev_page_id_

单纯维护还好，但是横向扫描容易出死锁（见 Lect 10 的最后一点内容）。

加上反向指针后，分裂、合并还得修改后继页。例如 L ↔ R ↔ S 合并为 L ↔ S，就需要把 S.prev 改成 L。

这就引入了横向取锁：一个线程拿着 L 等 R，另一个线程拿着 R 等 L，就可能互相卡住。原来的自顶向下取锁顺序，管不到这种相邻叶页之间的访问。

处理方式是 no-wait：尝试取得相邻页的 latch，拿不到就结束本次尝试。底层用到的 API 是：

std::unique_lock<std::shared_mutex> lock(latch, std::try_to_lock);
if (!lock.owns_lock()) {
  // 没有取得写锁，不能继续访问页面。
}

读锁对应 std::shared_lock。成功后把这个已经持锁的对象 std::move() 给 PageGuard，不能再让 guard 重复加一次锁；失败则撤销本次 pin。

还有一个提交上的限制：原来的提交清单（CMakeList.txt）不包含 TracedBufferPoolManager，不能依赖给它增加 TryReadPage() / TryWritePage()。

因此，利用它原本就会转发的 AccessType 参数，增加 IndexNoWait：

bpm_->ReadPage(next_page_id, AccessType::IndexNoWait);

调用仍然经过 TracedBPM，读写次数也照常统计；真正的 try-lock 在底层 BPM 完成。这个模式遇到 latch 冲突时抛出 PageLatchUnavailable，它继承自 std::runtime_error，也就是一种 std::exception。

迭代器的 ++、-- 跨页都这样处理：失败就 guard_.reset()，把当前迭代器置为 end，再把异常抛给调用者。

因为 guard 是共享的，这里不能直接 Drop()，否则会把其他迭代器副本仍在用的锁释放掉。

总结一下什么时候使用 AccessType::IndexNoWait：

不通过父页获得叶锁，而是横向获取的时候。

向下取得普通孩子锁仍然可以等待，no-wait 用在这些横向叶页访问上。

Task 4

读锁升级为写锁的间接办法

到叶子时保留父页读锁，释放叶页读锁，再取得叶页写锁，最后释放父页读锁。

关键是没有「原地升级」的 API，也不能拿着自己的读锁，再等待同一页的写锁。

下降过程中，用 parent_guard 和 guard 交替保存父页与当前页。到达叶子之后：

page_id_t leaf_page_id = guard.GetPageId();
guard.Drop();
auto leaf_guard = bpm_->WritePage(leaf_page_id);
parent_guard.Drop();

中间虽然暂时没有叶页锁，但父页读锁还在：其他线程无法取得父页写锁来修改这里的结构关系。根本身是叶页时，这个 parent 就是 header。

对乐观 Remove 来说：

• 如果墓碑缓冲区还有空间，删除不会减少物理槽位，可以直接处理；
• 如果需要物理删除，就检查删后是否仍满足最低大小。
• 可能下溢时返回 false，释放锁后从根走悲观路径。

悲观 Remove 的 pop_ancestors_if_safe()

这个 lambda 判断的是：当前节点能不能承受下层传来的一次删除影响，保证变化不会继续传到它的父页。

先计算最低大小，再判断 GetSize() > min_size：

节点	判断中使用的 min_size	原因
普通节点	GetMinSize()	少一个槽位或孩子后，仍不能下溢
根叶页	1	从 1 删到 0，需要更新 header
内部根页	2	从 2 个孩子变成 1 个，需要缩根并更新 header

叶页还多一个条件：墓碑缓冲区没满时，也算 safe。因为这次删除只会登记墓碑，不会减少物理槽位。没有墓碑缓冲区时，不会走这个特例。

如果 safe，就先释放 header_page_，再从 write_set_ 的队首释放祖先，同时弹出对应的 child_idx_，只留下当前节点的写锁。后续继续向下获取孩子锁，再做同样的判断。

所以 write_set_ 保存的可能只是路径的后半段。不能再用「只剩一个 guard」判断当前页是不是根，要通过 ctx.IsRootPage(page_id) 比较实际页号。

允许重试的取锁失败，必须发生在修改页面之前

如果先执行 RemoveAt()，删到下溢了才去尝试锁兄弟，失败后就没法直接「从头再来」：key 已经删了，树却还没有修复。

因此，悲观 Remove 在确认本次删除可能引起叶页下溢后，会先准备好横向叶页锁：

1. 优先选左兄弟；当前是最左孩子时，选择右兄弟。
2. 用 IndexNoWait 取得兄弟写锁，放进 Context。
3. 再取得可能需要修改的后继页写锁：和左兄弟合并时是当前页的下一页；和右兄弟合并时是右兄弟的下一页。
4. 都成功后，才执行 RemoveAt()，然后按原来的逻辑借位或合并。

这里会提前锁住可能合并时需要的后继页，即使最终借位成功、不需要合并。

取锁失败会抛出 PageLatchUnavailable，Context 析构释放路径上的锁；最外层 Remove() 捕获这个特定异常，再从根重新尝试。

Insert 同理：叶页要分裂时，先尝试锁住旧后继，再插入和分裂，之后才能安全修改旧后继的 prev_page_id_。