跳至主要内容

P2 - B+ Tree

在這個 project 中，我們需要實現 B+ tree index，總共有 4 個 task :

  • B+Tree Pages
  • B+Tree Operations (Insertion, Deletion, and Point Search)
  • Index Iterator
  • Concurrency Control

Background​

這個 project 的背景知識應該是相對好理解的，可以參考上課講義來熟悉 B+ tree 的結構以及操作方式。

Task 1 - B+Tree Pages​

B+ tree 中總共有四種 page，分別是 BPlusTreePage、BPlusTreeInternalPage、BPlusTreeLeafPage 以及 BPlusTreeHeaderPage。 這個 task 只需要按照要求讀懂這幾個 page 在幹麼以及實作一些如初始化 size 跟 type 之類的東西而已，這裡就不多說明了。

在 bustub 中，每一個 page 的大小都是 4 kb，下面是這四種 page 的結構 :

  • BPlusTreePage : B+ tree page 的 base class，包含了一些共用的方法及屬性 (page type, size, max size) 共 12 bytes
  • BPlusTreeInternalPage : B+ tree 的 internal page，包含了 key 跟 child page id 的 mapping，需要注意 key_array_[0] 是無意義的
  • BPlusTreeLeafPage : B+ tree 的 leaf page，包含了 key 跟 RID 的 mapping，並且有一個指向下一個 leaf page 的指標 next_page_id_
  • BPlusTreeHeaderPage : B+ tree 的 header page，目前只包含了 root_page_id_

Task 2 - B+Tree Operations​

除了上面提到的幾個 class 外，也可以看一下 Context 這個 class 來幫助我們管理 PageGuard。

Search 的部分應該是裡面最簡單的，從 root page 開始用 binary search 的方法一直往下搜尋，直到找到 leaf page 為止，可以把中途的節點都放到 Context 中的 read_set_ 中。

Insertion​

Insert 主要可以分成三種情況來討論 :

  • 如果是空的 B+ tree，直接建立 root page 並插入 key
  • 如果最後的節點沒有 overflow，直接插入 key
  • 如果最後的節點 overflow，則需要分裂節點並將新的 key 插入到 parent page 中，需要遞迴的做這件事直到沒有 overflow 為止，也有可能會需要建立新的 root page

Deletion​

Delete 的情況是三種操作裡面最複雜的，我是按照以下的順序實作的 :

  • 先刪除 key，如果沒有 underflow，則直接結束 (要特別注意是 root page 的情況，如果是 root page 並且沒有 key 了，則需要將整個 B+ tree 清空)
  • 如果有 underflow，則需要檢查 sibling page 是否可以借 key，如果可以借 key，則從 sibling page 中借一個 key 並更新 parent page 的 key，這種方式不需要繼續更新父節點
  • 如果 sibling page 不能借 key，則需要 merge sibling page，並將 parent page 中的 key 刪除，然後再檢查 parent page 是否 underflow，如果 parent page underflow，則需要繼續往上處理

Task 3 - Index Iterator​

這個部分感覺也沒什麼特別的，就是一直讀取下一個 page，需要自己決定一下 IsEnd() 想要實作成什麼樣子。

我自己的做法是表示成 read_page->GetNextPageId() == INVALID_PAGE_ID && index_ >= read_page->GetSize()。

Task 4 - Concurrency Control​

Latch crabbing 的部分可以參考上課講義，基本上就是檢查子節點是不是安全的，如果是安全的就可以放掉父節點的鎖，然後繼續往下走。

這裡我可以分享一個錯誤實作，這是我在實作 insert 的時候遇到的問題 :

if (IsEmpty()) {
  WritePageGuard header_guard = bpm_->WritePage(header_page_id_);
  auto header_page = header_guard.AsMut<BPlusTreeHeaderPage>();

  auto root_page_id = bpm_->NewPage();
  WritePageGuard root_guard = bpm_->WritePage(root_page_id);
  auto root_page = root_guard.AsMut<LeafPage>();
  return root_page->Insert(key, value, comparator_);
}

上面這個在 IsEmpty() 的時候是會去拿 header_guard 的，但是他跟下面的 header_guard 是不連續的，這中間就有可能產生錯誤。 因此要盡量避免使用 IsEmpty() 來檢查整個樹是否為空，改成直接在裡面拿 header_guard 判斷才是對的。

題外話，contention test 似乎只針對 Insert 的部分進行測試，因此在 Insert 的時候要特別注意 latch crabbing 的實作。

Submit​

這個 project 提供了線上的 B+ tree visualizer，可以用來檢查自己的 B+ tree 是否正確 :

make b_plus_tree_printer -j
./bin/b_plus_tree_printer

並透過這個線上 B+ tree visualizer 來檢查自己的 B+ tree 是否正確。

make b_plus_tree_insert_test -j$(nproc) && ./test/b_plus_tree_insert_test

make b_plus_tree_sequential_scale_test -j$(nproc) && ./test/b_plus_tree_sequential_scale_test

make b_plus_tree_delete_test -j$(nproc) && ./test/b_plus_tree_delete_test

make b_plus_tree_contention_test -j$(nproc) && ./test/b_plus_tree_contention_test

make b_plus_tree_concurrent_test -j$(nproc) && ./test/b_plus_tree_concurrent_test
make format && make check-format && make check-lint && make check-clang-tidy-p2
make submit-p2

Takeaways​

這個 project 在寫的時候感覺花了很多時間，但真的到要寫總結的時候，卻又發現好像都是一些小細節而已不知道要寫啥哈哈。

還有一個問題是在於 contention test 那邊我在 gradescope 上面一直到不了 [2.5,3.5] 的範圍 (大概都在 2.3 左右)，感覺應該有甚麼沒有注意到的細節但也有點懶得繼續 debug 下去了，總之這個 project 就是這樣。

References​