CMU 15-445/645 fall2024 p2

在服务器内按照 bustub 文档完成开发环境配置后，P2 主要实现了 B+ Tree Index 的核心路径：页面结构操作、迭代器、插入/删除（含分裂与合并），以及并发访问下的稳定性处理。和 P0/P1 一样，public 指模板仓库远程，origin 指我自己的远程仓库，日常开发在本地仓库完成。

Git 命令

  git pull public master # 拉取模板更新
  git push origin main   # 推送本地提交

b_plus_tree_page.cpp

b_plus_tree_page.cpp 实现了 B+Tree 页面公共元数据接口：

IsLeafPage / SetPageType 在 src/storage/page/b_plus_tree_page.cpp:21、src/storage/page/b_plus_tree_page.cpp:22 区分页类型。
GetSize / SetSize / ChangeSizeBy 在 src/storage/page/b_plus_tree_page.cpp:28 维护页内元素数量。
GetMaxSize / SetMaxSize 在 src/storage/page/b_plus_tree_page.cpp:35 管理容量上界。
GetMinSize 在 src/storage/page/b_plus_tree_page.cpp:43 返回最小占用阈值（用于删除时借位/合并判定）。

b_plus_tree_internal_page.cpp

b_plus_tree_internal_page.cpp 实现内部节点的 key-child 管理：

Init 在 src/storage/page/b_plus_tree_internal_page.cpp:35 初始化页类型和容量。
KeyAt / SetKeyAt 在 src/storage/page/b_plus_tree_internal_page.cpp:49、src/storage/page/b_plus_tree_internal_page.cpp:61 访问与更新分隔键。
ValueAt / SetValueAt 在 src/storage/page/b_plus_tree_internal_page.cpp:84、src/storage/page/b_plus_tree_internal_page.cpp:90 访问与更新子指针。
ValueIndex 在 src/storage/page/b_plus_tree_internal_page.cpp:67 查找子页在当前节点中的位置。
InsertAt / RemoveAt 在 src/storage/page/b_plus_tree_internal_page.cpp:96、src/storage/page/b_plus_tree_internal_page.cpp:110 支持分裂/合并时的数组搬移。

b_plus_tree_leaf_page.cpp

b_plus_tree_leaf_page.cpp 实现叶子节点的数据与墓碑（tombstone）语义：

Init 在 src/storage/page/b_plus_tree_leaf_page.cpp:37 初始化叶子页。
GetNextPageId / SetNextPageId 在 src/storage/page/b_plus_tree_leaf_page.cpp:63、src/storage/page/b_plus_tree_leaf_page.cpp:66 维护叶子链表。
KeyAt / ValueAt / SetValueAt 在 src/storage/page/b_plus_tree_leaf_page.cpp:73 起提供槽位访问。
InsertAt / RemoveAt 在 src/storage/page/b_plus_tree_leaf_page.cpp:117、src/storage/page/b_plus_tree_leaf_page.cpp:136 进行有序插入和删除。
GetTombstones / AddTombstone / ClearTombstones 在 src/storage/page/b_plus_tree_leaf_page.cpp:50、src/storage/page/ b_plus_tree_leaf_page.cpp:174、src/storage/page/b_plus_tree_leaf_page.cpp:196 实现延迟删除相关逻辑。

index_iterator.cpp

index_iterator.cpp 提供顺序扫描能力：

构造函数在 src/storage/index/index_iterator.cpp:31 接管当前叶子页 guard，并调用推进逻辑。
operator* 在 src/storage/index/index_iterator.cpp:44 返回当前 key-value。
operator++ 在 src/storage/index/index_iterator.cpp:52 前进到下一个可见元素。
AdvanceToNextVisible 在 src/storage/index/index_iterator.cpp:75 负责跨叶子页推进，并处理边界与结束状态。
IsEnd 在 src/storage/index/index_iterator.cpp:41 判断迭代器是否到尾。

b_plus_tree.cpp

b_plus_tree.cpp 是 P2 主体，实现了查询、插入、删除与扫描：

构造函数在 src/storage/index/b_plus_tree.cpp:183 初始化树对象与 header 页信息。
IsEmpty 在 src/storage/index/b_plus_tree.cpp:198 判断树是否为空（从 header/root 出发）。
GetValue 在 src/storage/index/b_plus_tree.cpp:234 执行点查：内部节点二分下探到叶子页后匹配 key。
Insert 在 src/storage/index/b_plus_tree.cpp:261 执行插入流程：定位叶子、插入、必要时分裂并向上更新父节点，最终可能生成新根。
Remove 在 src/storage/index/b_plus_tree.cpp:433 执行删除流程：删除后若低于最小占用则尝试借位，否则触发合并并向上调整。
Begin / Begin(key) / End 在 src/storage/index/b_plus_tree.cpp:903、src/storage/index/b_plus_tree.cpp:923、src/storage/index/ b_plus_tree.cpp:946 提供全表和范围扫描入口。
GetRootPageId 在 src/storage/index/b_plus_tree.cpp:949 返回当前根页编号（调试/测试常用）。

实现上主要依赖 ReadPageGuard / WritePageGuard 做页面访问控制，保证并发场景下 latch 与 pin/unpin 生命周期正确，避免死锁与悬挂引用。

生成提交包

打包（与这次通过的文件列表一致）

rm -f project2-submission.zip zip project2-submission.zip
src/storage/page/page_guard.cpp
src/include/storage/page/page_guard.h
src/include/buffer/lru_k_replacer.h
src/buffer/lru_k_replacer.cpp
src/include/buffer/buffer_pool_manager.h
src/buffer/buffer_pool_manager.cpp
src/storage/disk/disk_scheduler.cpp
src/include/storage/disk/disk_scheduler.h
src/include/storage/page/b_plus_tree_page.h
src/storage/page/b_plus_tree_page.cpp
src/include/storage/page/b_plus_tree_internal_page.h
src/storage/page/b_plus_tree_internal_page.cpp
src/include/storage/page/b_plus_tree_leaf_page.h
src/storage/page/b_plus_tree_leaf_page.cpp
src/include/storage/index/index_iterator.h
src/storage/index/index_iterator.cpp
src/include/storage/index/b_plus_tree.h
src/storage/index/b_plus_tree.cpp

把签名文件加进 zip（首次会交互生成 GRADESCOPE.md）

python3 gradescope_sign.py

检查提交包内容（避免 Build.Prepare 因缺文件直接失败）

unzip -l project2-submission.zip