ZonePG

CMU 15-445/645 PROJECT #2 - B+TREE

Posted on Aug 18, 2021

这一部分前前后后做了两周，到目前为止仍然有个并发的 bug 没有解决，没有拿到满分，准备先去去完成后面的内容回来再来看看。

遵循Andy Pavlo要求，代码存放在私有仓库。

Checkpoint 1

TASK #1 - B+TREE PAGES

这一部分大都是补全Get, Set函数即可。

需要注意的是，其中 GetSize() 就是 k-v 对数，根据 ppt 来看，对于一个page来说，能装的最多有效k-v 对数也就是 max_size - 1对。

  • 对于 internal_page 来说，第一个 key 也就是 array[0].first 是非法的 key，但是它的 value 是有效的，在计算 size 时我们仍然给它算作一对 k-v，它的 value 也就是 array[0].second 就是它孩子的page_id
  • 对于 leaf_page 来说，真正的 value 直接保存在 array[0].second 中，所以第一个 key(array[0]) 是有效的。

对于 GetMinSize() 也需要注意如下几点。

  • 如果当前结点是根结点
    • 如果根结点是叶子结点，那么它的 min_size 就是 1，表示没有有效的 key。
    • 如果根结点是internal page，那么它的 min_size 就是 2，需要至少一个有效的 key 来 route 到叶子结点。
  • 如果不是根结点
    • 是 inernal_page，那么 min_size 是 (max_size + 1) / 2
    • 是 leaf_page，那么 min_size 是 max_size / 2

以 max_size = 3 为例子，那么 leaf_page 的 min_size 就是 1，internal_page 的 min_size 就是2

TASK #2.A - B+TREE DATA STRUCTURE (INSERTION & POINT SEARCH)

这一部分要实现 Insert 与 GetValue 功能。

Insert

对于 Insert 部分，首先判断是否是空树，如果是空树，需要StartNewTree()。

如果它不是空树，应当考虑插入到某个叶子结点中，也就是InsertIntoLeaf()，通过FindLeafPage找到叶子结点，并将 k-v 插入到叶子结点中。

如果插入后 leaf_page->GetSize() >= leaf_page->GetMaxSize()，那么就应当 Split 一个新的 leaf_page 了，并各自保存原来叶子结点的一半值，通过InsertIntoParent 设置新的leaf_page的parent，并更新parent上相应的 k-v，来 route 新的 leaf_page。

InsertIntoParent时需要考虑原来的结点是否是 root_page，如果它是 root_page 那么就应当 NewPage 并设置新的 root_page； 如果不是 root_page，如果插入到当前 parent 时，parent 作为 internal_page 的 size 出现了 parent_page_size > parent_page->GetMaxSize() 的情况，那么需要 Split parent 后继续递归 InsertIntoParent。

GetValue

GetValue部分就十分简单了，直接根据 key 找到叶子结点，再在叶子结点中进行二分查找到真正的key。

CHECKPOINT #2

TASK #2.B - B+TREE DATA STRUCTURE (DELETION)

对于 Remove 部分，首先找到叶子结点，在该叶子结点中删除影响的 key-value，如果删除后 size 小于 min_size 了，那么就要做 CoalesceOrRedistribute()的工作。

CoalesceOrRedistribute()实现细节如下。

  • 如果它是根结点，那么需要 AdjustRoot()
    • 根结点是叶子的话，说明删除后就是一颗空树了。
    • 根结点是internal_page 的话，min_size 是2，删除后 min_size 为 1，还剩唯一的一个孩子route，将这个孩子结点作为根结点。
  • 如果不是根结点，需要获取当前结点的 parent，以及 sibling 结点。
    • 如果 sibling 结点的数量比 min_size 要小的话，那么可以作合并的操作。合并后删除 parent 上的相应 k-v，并检查 parent 的大小，决定是否递归CoalesceOrRedistribute。(Coalesce)
    • 如果 sibling 结点的数量比 min_size 大的话，那么就是可以将 sibling 的某个值分给当前结点。并更新 parent 的key。(Redistribute)

TASK #3 - INDEX ITERATOR

实现迭代器的操作，用来遍历树。

TASK #4 - CONCURRENT INDEX

这一部分课上讲的很详细，关于 Latch Crabing/Coupling。