Index Manager 讲解

核心结构：本项目索引用 B+ 树实现，索引键是 Row 按索引列序列化后的 GenericKey，叶子节点保存 key -> RowId，内部节点保存分隔 key 和 child page id。真正数据仍在 TableHeap，索引只定位 RowId。

插入流程：

1. 如果树为空，StartNewTree 创建一个叶子页作为 root。
2. 否则 FindLeafPage(key) 从 root 逐层查找到目标叶子。
3. 叶子内二分定位插入位置，若重复 key 则拒绝。
4. 插入后如果未溢出，直接结束。
5. 如果叶子溢出，Split(LeafPage) 分裂，并把新叶子的第一个 key 插入父节点。
6. 父节点也可能溢出，递归 InsertIntoParent，必要时创建新 root。
7. root 变化后写入 IndexRootsPage，保证重启后能恢复 root page id。

删除流程：

1. 找到叶子并删除 key。
2. 若删除后节点仍不少于最小大小，结束。
3. 否则进入 CoalesceOrRedistribute。
4. 如果兄弟节点能借，执行 redistribute。
5. 如果不能借，执行 merge，并递归调整父节点。
6. root 特殊处理：内部 root 只剩一个 child 时降高；叶子 root 空时整棵树变空。

范围查询：

• B+ 树叶子节点有 next_page_id 链表。
• Begin() 找最左叶子。
• Begin(key) 找第一个大于等于 key 的位置。
• IndexIterator 沿叶子链表向后扫。

高频追问：

• 为什么 internal page 第一个 key 无效？
  因为 internal page 有 n 个 child pointer，但只有 n-1 个分隔 key。第 0 个 value 表示小于第一个有效 key 的子树，所以第 0 个 key 作为 dummy。

• leaf split 后为什么把新叶子的第一个 key 插入 parent？
  因为这个 key 是右侧新叶子的最小 key，可作为父节点中区分左右子树的分隔 key。

• internal split 时 push up 的 key 怎么处理？
  分裂后新 internal 的第一个 key 代表从父节点下推/分隔出来的边界，插入父节点时要用它作为 separator，同时移动 child 后要更新 child 的 parent page id。

• 删除时 merge 和 redistribute 怎么选？
  如果当前节点和兄弟节点总大小能放进一个节点，就 merge；否则从兄弟借一个元素 redistribute。

• root 为什么要单独处理？
  root 可以不满足半满约束。删除后 root 如果只有一个 child，可以把 child 提升为新 root；如果 root leaf 空了，整棵树为空。

Recovery Manager 讲解

这个 Recovery 是实验简化版，底层不是实际表页，而是测试用的内存 unordered_map<KeyType, ValType>。思想接近 ARIES 的 redo/undo，但没有 CLR、pageLSN、真正磁盘页。

日志类型：

• Begin
• Insert
• Delete
• Update
• Commit
• Abort

每条日志有：

• lsn_：当前日志序号
• prev_lsn_：同一事务上一条日志
• txn_id_
• old/new key/value

checkpoint 里保存：

• checkpoint_lsn_
• 当时的 active transaction table
• 当时已经持久化的数据快照

恢复流程：

1. Init(checkpoint)
   从 checkpoint 恢复 persist_lsn_、活跃事务表和持久化数据。

2. RedoPhase()
   按 lsn 从小到大扫描日志。
   小于等于 checkpoint lsn 的跳过。
   对 insert/delete/update 重做数据变化。
   对 begin/update/insert/delete 更新 active txns。
   对 commit 从 active txns 移除。
   对 abort 立即沿 prev_lsn undo 该事务，并从 active txns 移除。

3. UndoPhase()
   Redo 后仍在 active txns 里的事务都是 loser transaction。
   从每个 loser 的最后一条 lsn 沿 prev_lsn 反向 undo。

Undo 规则：

• Undo insert：删除新 key。
• Undo delete：恢复 old key/value。
• Undo update：删除 new key，恢复 old key/value。

高频追问：

• prev_lsn_ 有什么用？
  用来按事务维度反向遍历日志。Undo 不需要扫描全日志，只要从该事务最后一条日志沿链回滚。

• 为什么 redo 后还要 undo？
  Redo 是 repeat history，把 checkpoint 后所有已经发生的修改重放出来；然后 undo 没提交的 loser transaction，恢复事务原子性。

• commit 和 abort 的区别？
  Commit 表示事务完成，redo 后保留其结果。Abort 表示事务已经回滚，redo 过程中需要 undo 它的历史修改。

• checkpoint 为什么能跳过一部分日志？
  checkpoint 记录了某个 lsn 时刻已经持久化的数据和活跃事务状态，因此 lsn <= checkpoint_lsn 的日志不用 redo。

• 这个 Recovery 和真实数据库恢复有什么差别？
  这里是测试用 KV 模型，没有 pageLSN、dirty page table、CLR、physiological logging；真实 ARIES 会更复杂。

Lock Manager 死锁检测讲解

Lock Manager 维护每个 RowId 上的锁请求队列。请求有三种状态：

• 请求共享锁
• 请求独占锁
• 已授予或等待中

兼容规则：

• S 和 S 兼容。
• S 和 X 冲突。
• X 和任何其它锁冲突。

等待时，事务会在条件变量上阻塞。后台死锁检测线程周期性构建 waits-for graph。

等待图构建：

• 图中节点是事务 id。
• 边 T1 -> T2 表示 T1 正在等待 T2 释放锁。
• 对每个 RowId 的锁队列：
  • 找等待中的请求。
  • 找已经 granted 且与它冲突的 holder。
  • 加边 waiter -> holder。
• 已 abort 的事务不应继续作为有效等待对象。

死锁检测：

1. 后台线程定期执行 RunCycleDetection。
2. 每次先清空并重建 waits-for graph。
3. 用 DFS 检测环。
4. 遍历节点和邻居时按事务 id 从小到大，保证 deterministic。
5. 找到环后，选择环中 txn id 最大的事务作为 victim。
6. 将 victim 状态设为 Aborted。
7. 删除图中 victim 相关边。
8. notify_all 唤醒等待线程。
9. 等待线程醒来后 CheckAbort 发现事务 aborted，清理请求并抛 TxnAbortException。

高频追问：

• 为什么要 abort 最大 txn id？
  实验要求 abort youngest transaction。这里 txn id 越大表示越年轻，所以选择环中最大 id。

• 为什么每次检测都重建图？
  锁等待关系是动态的。重建可以避免维护增量图的复杂性，也符合实验要求。

• 怎么保证 DFS 结果确定？
  当前实现把节点排序，并用 std::set 存邻居，因此遍历顺序从小到大。这样测试中同一个图总能找到同一个环和 victim。

• 锁升级怎么避免两个事务同时升级死锁？
  每个锁队列有 is_upgrading_。如果已有事务在升级，第二个升级请求直接 abort，抛 UpgradeConflict。

• waiting 事务怎么知道自己被死锁检测 abort 了？
  死锁线程把事务状态设为 Aborted 并 notify_all。等待线程醒来后调用 CheckAbort，清理自己的请求并抛异常。

• 2PL 怎么体现？
  事务解锁后从 growing 进入 shrinking。LockPrepare 如果发现事务已经 shrinking 又申请新锁，会 abort 并抛 LockOnShrinking。

答辩时可以这样总述

Index Manager 我们实现的是唯一键 B+ 树索引。通过 BufferPool 管理 B+ 树节点页，root page id 持久化在 IndexRootsPage 中。插入时自底向上分裂，删除时处理 borrow/merge/root adjust，范围扫描依赖叶子链表。

Recovery Manager 是实验简化版 ARIES。日志按 lsn 串起来，并用 prev_lsn 维护事务链。恢复时先从 checkpoint 初始化，再 redo checkpoint 后的历史，最后 undo 未提交事务。

Lock Manager 的死锁检测用 waits-for graph。后台线程周期性从锁表重建图，用确定性 DFS 找环，选择环中最年轻事务 abort，并唤醒等待线程完成清理。