Project #2 - B+Tree

Task #1 - B+Tree Pages

这一部分没什么好说的，把他给的函数写出来就行，基本都是一两行的事

Task #2 - B+Tree Data Structure (Insertion, Deletion, Point Search)

逆天 Task 之一

B+Tree 这东西看着原理简单，在内存池上写起来怪恶心的

比较简单的是查找，直接顺着往下定位到叶子节点就行。关于每个节点上的定位可以直接遍历或者二分定位。我用的二分，不过估计效率差别不大，瓶颈不应该在这一块

至于插入，最好先画个图仔细想清楚再写，不然就会向我一样改了好几版，10 天才摸出来这个 Task，感觉 DSA 白学了（ 我在向上更新的时候用的递归，感觉比较好理解。需要注意 Split 时也要更新子节点的 parent_page_id

然后是删除。因为课件讲得不是很细致，有些细节也稍微卡了一会。在 Merge 时需要给右边节点的第一个子节点增加一个对应的 Key，这个 Key 可以直接取父节点对应的 Key，然后删除父节点中的内容。

在操作中若根节点改变，需要调用它给出的 UpdateRootPageId 函数。这个函数的参数只表示是否需要在 Buffer Pool Manager 中新建 Page，所以还需要手动更新 PageID。因为它没有删除 Page 的逻辑，因此在根节点 Size = 0 的情况我选择依然保留根节点。

同时也可以在 Tree 和 Tree Page 的类中增加一些自定义内容，方便写代码。另外写的时候也可以注意一下，最好给后面增加并发时留出一些操作余地

写完之后调了一会儿通过了本地测试，交上去竟然一发过了 Checkpoint 1（其实格式检查挂了）

Task #3 - Index Iterator

比起 B+Tree 本身来说显得非常小清新的一个 Task。Iterator 里面记录当前叶节点和点上位置就行，Task 不要求支持并发所以非常简单~

Task #4 - Concurrent Index

逆天 Task 之二

因为不能一把大锁直接锁住了，就需要用课件上的 Latch Crabbing Protocol。

Fall2022 的页管理、锁管理全部是手动的，听说 Spring2023 全改成 RAII 了，后悔没跟 2023（

如果 Checkpoint 1 写的没问题的话就是在之前的基础上加锁，注意对根节点需要单独设一个额外的锁，对根节点进行相关操作的时候需要获取这把锁

在修改相关操作中，如果需要访问当前链以外的节点，最好也获取锁，防止和其他正在进行的操作冲突

写完之后交上去，结果发现 Checkpoint 1 的部分有 bug。。改得想死

发现自己理解有问题，内部节点的 min_size 是 (max_size + 1) / 2，所以一定有兄弟节点，我说怎么没讲 min_size == 1 的情况，弱智 bug

关于函数提供的 transaction，主要用到的功能是里面的 page_set，可以存储当前线程获取到的 page。不过事实上也完全可以自己写？

写的时候一直在想如果 buffer pool 满了会不会死锁，不过看起来似乎不容易满

最后不知道为什么卡在 45 points，后来搞期末和其他东西去了，拖了很长时间，因为主要目标还是先学原理，之后想自己写一个完整的，本来想直接跳过，到后面一看 Project3 也依赖 Project2，于是照着别人的思路重写了一部分，感觉效率还可以的样子

Time: mean=2.86697, stddev=0.76940