写个 B+Tree

Projbect2 B+ Tree

• [Review] B-Trees (playlist) in 26 minutes (video)
• Yet Another B+ Tree Visualization
• b+ trees

有意思的Flexible array member

  // Flexible array member for page data.
  MappingType array_[1];

静态检测 flexible array 时 index out of bound，可以写个 Set 函数，

error: array index 1 is past the end of the array (which contains 1 element) [clang-diagnostic-array-bounds,-warnings-as-errors] array_[1].first = new_key;
 
INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::SetEle(int index, const KeyType &key, const ValueType &value) {
  array_[index].first = key;
  array_[index].second = value;
}
 
SetEle(1, x, x);

[[C++4种cast]]

Split

注意时机

You should correctly perform splits if insertion triggers the splitting condition (number of key/value pairs **AFTER** insertion equals to max_size for leaf nodes, number of children **BEFORE** insertion equals to max_size for internal nodes.).
如 5 degree B+ tree 代表 B+ 树节点最多能容纳五个 KV 对
对于 internal page，max 4 key，5 value 相当于 5 个 KV 对。
对于 leaf page, max 4KV 对。

在插入后检测 leaf page 是否需要分裂，插入后有 5 个，仍能容纳。

在插入前检测 internal page，若插入后再检测，插入的第 6 个 KV 对会造成越界。

但是我觉得可以开辟空间的时候多搞一个，统一都是先插入后分裂，由于这里使用的是 flexible array,长度是被确定的，

checkpoint1

checkpoint1 先完只能先手动的用工具 debug 下效果

make b_plus_tree_printer -j$(nproc)
```bash
./bin/b_plus_tree_printer

生成 dot 文件，可以在此看图。就一步一步的插入删除，测试所有场景。
BusTub B+Tree Printer

3 3
i 11
i 22
i 33
i 44
i 10
i 23
i 55
i 66
d 22
d 10
d 33
d 55
d 66
d 23
d 11

5 5
i 11
i 22
i 33
i 44
i 10
i 23
i 55
i 66
i 13
i 14
i 24
i 25
i 77
i 88
i 99
i 110
i 120
d 10
d 11
d 13
d 23
d 24

checkpoint 2

# CMU 15445-2022 P2 B+Tree Concurrent Control
## MySQL · 引擎特性 · B+树并发控制机制的前世今生

Debug

多线程只能打 log，打出 thread_id

  auto this_id = std::hash<std::thread::id>{}(std::this_thread::get_id());
  LOG_DEBUG("%lu: Unlock W start %d", this_id, page->GetPageId());

cmake -DCMAKE_BUILD_TYPE=DEBUG ..

Test

make b_plus_tree_insert_test -j$(nproc)
make b_plus_tree_delete_test -j$(nproc)
make b_plus_tree_concurrent_test -j$(nproc)
make b_plus_tree_contention_test -j$(nproc)

./test/b_plus_tree_insert_test
./test/b_plus_tree_delete_test
./test/b_plus_tree_concurrent_test
./test/b_plus_tree_contention_test

benchmark

Running main() from gmock_main.cc
[==========] Running 2 tests from 1 test suite.
[----------] Global test environment set-up.
[----------] 2 tests from BPlusTreeTest
[ RUN      ] BPlusTreeTest.BPlusTreeContentionBenchmark
This test will see how your B+ tree performance differs with and without contention.
<<< BEGIN
Normal Access Time: 3624 3798 3738 3749 3743 3815 3720 3737 3747 3759
Serialized Access Time: 1696 1721 1719 1737 1733 1689 1842 1705 1746 1714
Ratio: 2.16333
>>> END
If your above data is an outlier in all submissions (based on statistics and probably some machine-learning), TAs will manually inspect your code to ensure you are implementing lock crabbing correctly.
[       OK ] BPlusTreeTest.BPlusTreeContentionBenchmark (54743 ms)
[ RUN      ] BPlusTreeTest.BPlusTreeContentionBenchmark2
This test will see how your B+ tree performance differs with and without contention.
<<< BEGIN2
Normal Access Time: 2341 2345 2323 2348 2353 2335 2347 2384 2348 2336
Serialized Access Time: 1113 747 747 724 730 736 756 816 752 725
Ratio: 2.99006
>>> END2
If your above data is an outlier in all submissions (based on statistics and probably some machine-learning), TAs will manually inspect your code to ensure you are implementing lock crabbing correctly.
[       OK ] BPlusTreeTest.BPlusTreeContentionBenchmark2 (31314 ms)
[----------] 2 tests from BPlusTreeTest (86057 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test suite ran. (86057 ms total)
[  PASSED  ] 2 tests.