[CMU15445] bustub 2023 Project2 作者: rin 时间: April 23, 2023 分类: 未分类 评论 Codes: [b_plus_tree.cpp](https://git.lo-li.net/rin/bustub/src/branch/master/src/storage/index/b_plus_tree.cpp "b_plus_tree.cpp") # Task1 B+Tree Pages ## Page types There are 4 types of headers (classes) named as `b_plus_*_page_.h` 1. `b_plus_tree_page.h` 2. `b_plus_tree_header_page.h` 3. `b_plus_tree_internal_page.h` 4. `b_plus_tree_leaf_page.h` Only `internal_page` and `leaf_page` are inherited from the base class defined in `b_plus_tree_page`. At first, I was confused by the words `RootPage` and `HeaderPage`. In fact, `header_page` does not belong to the inheritance tree. It stores the metadata of a `BPlusTree` object, which is `root_page_id` for now. `header_page` always exists in an initialized `BPlusTree`. But `root_page_id` may be `INVALID_PAGE_ID` at some time, meaning the tree is **empty** (tree exists but no data). --- ## Page structure Both 2 types of pages share the common member variables `page_type_`, `size_` and `max_size_` defined in `BPlusTreePage`. But the data area `MappingType array_[0]` is defined in `leaf_page.h` and `internal_page.h` separately. This is because the array is a *Flexible array* and it must be placed at the end of an object. But in `leaf_page`, there is an extra member `next_page_id_` after common members. The class structure is as below: ``` || page_type_ | size_ | max_size_ | next_page_id_ | array_....... || || page_type_ | size_ | max_size_ | array_....... || ``` In later codes, a pointer of `internal_page` will be `reinterpret_cast` to a point of `leaf_page`. And `page_type_` will be accessed to check the type of this page. Due to the common memory structure in both pages' headers, this operation is safe. ### Internal page ``` | KEY(0)+PAGE_ID(0) | KEY(1)+PAGE_ID(1) | KEY(2)+.... | ⬆[INVALID] ``` There are $$m+1$$ pairs of `<key, page_id_t>` in an internal page. The 0th pair has an invalid key. So an Internal Page stores **m** ordered keys and **m+1** child pointers. `max_size_ == m+1` The assignment specification recommends: > split an internal node when number of values reaches `max_size` before insertion ### Leaf page Every key in a leaf page is valid. > split a leaf node when the number of values reaches `max_size` after insertion So in any stable situation, max_size_ < size_