一、题目链接

二、准备工作

见 CMU 15-445 Project #0 - C++ Primer 中的准备工作。

三、部分实现

对于B+树的节点定义，通过节点类的命名 b_plus_tree_page 不难发现，每一个节点本质上都是从缓冲池中通过 Fetch 操作获得的一个页面（准确来说是缓冲池页面的数据部分，这个数据部分通过 reinterpret_cast 强制转换后就是B+树节点的全部内容），因此B+树节点中的 page_id 与缓冲池和磁盘上的页面的 page_id 是一致的。

对于分支节点（即内部节点），它保存的是 (BUSTUB_PAGE_SIZE - LEAF_PAGE_HEADER_SIZE) / sizeof(MappingType) 个 GenericKey 与 page_id_t 组成的键值对。而对于叶子结点，它保存的则是 (BUSTUB_PAGE_SIZE - LEAF_PAGE_HEADER_SIZE) / sizeof(MappingType) 个 GenericKey 与 RID 组成的键值对。源码中对于 RID 的定义是一个记录标识符，可见叶子结点中保存的不是实际数据，而是一个键值，因此这里实现的B+树索引是一个非聚簇索引。

1.查找操作

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::GetValue(const KeyType &key, std::vector<ValueType> *result, Transaction *transaction) -> bool {/* 获取可能包含key的叶子页面 */LeafPage *target_leaf_page = FindLeafPage(key);/* 查找key是否存在 */for (int i = 0; i < target_leaf_page->GetSize(); i++) {if (comparator_(target_leaf_page->KeyAt(i), key) == 0) {result->emplace_back(target_leaf_page->ValueAt(i));return true;}}/* 查找失败 */return false;
}INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::FindLeafPage(const KeyType &key) -> LeafPage * {page_id_t cur_page_id = root_page_id_;  // 标识页面遍历while (cur_page_id != INVALID_PAGE_ID) {/* 从缓冲池中获取cur_page_id对应的页面，并将该页面的数据部分强制转换为一个B+树页面。 */auto cur_page = reinterpret_cast<BPlusTreePage *>(buffer_pool_manager_->FetchPage(cur_page_id)->GetData());/* 如果当前B+树页面为叶子页面表明查找成功 */if (cur_page->IsLeafPage()) {return static_cast<LeafPage *>(cur_page);}/* 将当前B+树页面转换为一个分支页面 */auto internal_page = static_cast<InternalPage *>(cur_page);/* 查找下一层待处理的B+树页面，本质是查找最右侧的小于等于key的键值对。 */cur_page_id = internal_page->ValueAt(0);for (int i = 1; i < cur_page->GetSize() && comparator_(internal_page->KeyAt(i), key) <= 0; i++) {cur_page_id = internal_page->ValueAt(i);}/* 取消对缓冲池页面的引用 */buffer_pool_manager_->UnpinPage(cur_page_id, false);}return nullptr;
}

2.插入操作

如果将向B+树页面的插入操作全部交给页面（包括叶子页面和内部页面）自己来处理，那么就需要将缓冲池指针等其他变量也传给B+树页面，这无疑会增加逻辑上的复杂性，很有可能出现B+树页面对象和B+树对象重复执行 UnpinPage 操作等问题。而如果全部交给B+树来处理，对于页面的私有数据成员 array_ 的访问处理又会非常复杂。因此这里叶子页面和内部页面只负责单纯的数据插入和移动，而溢出处理（页面分裂）、根节点更新、递归向上插入等操作都交给B+树来实现，其中具体的内部页面的递归向上插入由 InsertToInternalPage 实现。

插入函数

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::Insert(const KeyType &key, const ValueType &value, Transaction *transaction) -> bool {/* 如果当前B+树为一颗空树则需要创建一个叶子页面作为B+树的根页面，* 否则直接向可能的叶子节点进行插入。 */if (IsEmpty()) {/* 从缓冲池中获取页面并转换为叶子页面，这个叶子页面即新的根页面。 */Page *new_buffer_page = buffer_pool_manager_->NewPage(&root_page_id_);auto new_root_page = reinterpret_cast<LeafPage *>(new_buffer_page->GetData());/* 初始化根页面 */new_root_page->Init(root_page_id_, INVALID_PAGE_ID, leaf_max_size_);new_root_page->Insert(key, value, comparator_);new_root_page->SetNextPageId(INVALID_PAGE_ID);/* 取消缓冲区页面的固定 */buffer_pool_manager_->UnpinPage(root_page_id_, true);/* 更新header_page中的根页面信息 */UpdateRootPageId(true);return true;}/* 获取key应该被插入的叶子页面 */LeafPage *target_leaf_page = FindLeafPage(key);/* 如果叶子页面插入失败表明发生了键值重复，取消页面固定并返回false。 */if (!target_leaf_page->Insert(key, value, comparator_)) {buffer_pool_manager_->UnpinPage(target_leaf_page->GetPageId(), false);return false;}/* 如果叶子页面插入后仍未满，无需进行分裂操作，直接返回即可，否则需要进行分裂操作。 */if (target_leaf_page->GetSize() < target_leaf_page->GetMaxSize()) {return true;}/* 如果当前页面是根页面，需要新建一个根页面和分裂页面并更新相关信息;* 否则需新建一个分裂页面并进行相关信息更新，同时递归更新祖先页面的相关信息。 */if (target_leaf_page->IsRootPage()) {Page *new_buffer_page;/* 从缓冲池中获取页面并转换为叶子页面，这个叶子页面即新的分裂页面。 */page_id_t split_page_id;new_buffer_page = buffer_pool_manager_->NewPage(&split_page_id);auto split_leaf_page = reinterpret_cast<LeafPage *>(new_buffer_page->GetData());/* 从缓冲池中获取页面并转换为内部页面，这个内部页面即新的根页面。 */new_buffer_page = buffer_pool_manager_->NewPage(&root_page_id_);auto new_root_page = reinterpret_cast<InternalPage *>(new_buffer_page->GetData());/* 初始化分裂页面 */split_leaf_page->Init(split_page_id, root_page_id_, leaf_max_size_);split_leaf_page->SetNextPageId(target_leaf_page->GetNextPageId());target_leaf_page->MoveHalfDataTo(split_leaf_page);target_leaf_page->SetNextPageId(split_page_id);/* 初始化根页面 */new_root_page->Init(root_page_id_, INVALID_PAGE_ID, internal_max_size_);new_root_page->SetValueAt(0, target_leaf_page->GetPageId());new_root_page->Insert(split_leaf_page->KeyAt(0), split_page_id, comparator_);target_leaf_page->SetParentPageId(root_page_id_);/* 取消缓冲区页面的固定 */buffer_pool_manager_->UnpinPage(target_leaf_page->GetPageId(), true);buffer_pool_manager_->UnpinPage(split_page_id, true);buffer_pool_manager_->UnpinPage(root_page_id_, true);/* 更新header_page中的根页面信息 */UpdateRootPageId();} else {/* 从缓冲池中获取页面并转换为叶子页面，这个叶子页面即新的分裂页面。 */page_id_t split_page_id;Page *new_buffer_page = buffer_pool_manager_->NewPage(&split_page_id);auto split_leaf_page = reinterpret_cast<LeafPage *>(new_buffer_page->GetData());/* 初始化分裂页面 */split_leaf_page->Init(split_page_id, target_leaf_page->GetParentPageId(), leaf_max_size_);split_leaf_page->SetNextPageId(target_leaf_page->GetNextPageId());target_leaf_page->MoveHalfDataTo(split_leaf_page);target_leaf_page->SetNextPageId(split_page_id);/* 将分裂处的键值插入到父页面中 */KeyType insert_key = split_leaf_page->KeyAt(0);InsertToParentPage(target_leaf_page, split_leaf_page, insert_key);/* 取消页面固定 */buffer_pool_manager_->UnpinPage(target_leaf_page->GetPageId(), true);buffer_pool_manager_->UnpinPage(split_page_id, true);}return true;
}INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::InsertToParentPage(BPlusTreePage *old_child_page, BPlusTreePage *new_child_page, const KeyType &insert_key) {/* 如果旧页面是根页面，需要新建一个根页面并更新相关信息;* 否则向父页面插入，同时插入前需要判断父页面是否溢出。 */if (old_child_page->IsRootPage()) {/* 从缓冲池中获取页面并转换为内部页面，这个内部页面即新的根页面。 */Page *new_buffer_page = buffer_pool_manager_->NewPage(&root_page_id_);auto new_root_page = reinterpret_cast<InternalPage *>(new_buffer_page->GetData());/* 初始化根页面 */new_root_page->Init(root_page_id_, INVALID_PAGE_ID, internal_max_size_);new_root_page->SetValueAt(0, old_child_page->GetPageId());new_root_page->SetKeyAt(1, insert_key);new_root_page->SetValueAt(1, new_child_page->GetPageId());new_root_page->IncreaseSize(1);old_child_page->SetParentPageId(root_page_id_);new_child_page->SetParentPageId(root_page_id_);/* 取消缓冲区页面的固定 */buffer_pool_manager_->UnpinPage(root_page_id_, true);/* 更新header_page中的根页面信息 */UpdateRootPageId();return;}/* 从缓冲池获取父页面 */Page *parent_buffer_page = buffer_pool_manager_->FetchPage(old_child_page->GetParentPageId());auto parent_page = reinterpret_cast<InternalPage *>(parent_buffer_page->GetData());/* 如果父页面插入后仍未满，无需进行分裂操作，直接返回即可，否则需要进行分裂操作。 */if (parent_page->GetSize() < parent_page->GetMaxSize()) {parent_page->Insert(insert_key, new_child_page->GetPageId(), comparator_);return;}/* 从缓冲池中获取页面并转换为内部页面，这个内部页面即新的分裂页面。 */page_id_t split_page_id;Page *new_buffer_page = buffer_pool_manager_->NewPage(&split_page_id);auto split_internal_page = reinterpret_cast<InternalPage *>(new_buffer_page->GetData());/* 初始化分裂页面 */split_internal_page->Init(split_page_id, parent_page->GetParentPageId(), internal_max_size_);/* key和parent_page中的全部数据分裂到parent_page和split_internal_page中 */parent_page->InsertAndMoveHalfDataTo(split_internal_page, insert_key, new_child_page->GetPageId(), comparator_, buffer_pool_manager_);/* 将分裂处的键值插入到父页面的父页面中 */KeyType next_insert_key = split_internal_page->KeyAt(0);InsertToParentPage(parent_page, split_internal_page, next_insert_key);/* 取消缓冲区页面的固定 */buffer_pool_manager_->UnpinPage(parent_page->GetPageId(), true);buffer_pool_manager_->UnpinPage(split_page_id, true);
}

叶子节点的插入和数据移动操作

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_LEAF_PAGE_TYPE::Insert(const KeyType &key, const ValueType &value, const KeyComparator &comparator) -> bool {assert(GetSize() < GetMaxSize());int insert_pos = 0;  // 用于记录插入位置/* 查找插入位置 */while (insert_pos < GetSize() && comparator(array_[insert_pos].first, key) < 0) {insert_pos++;/* 键值不能重复 */if (comparator(array_[insert_pos].first, key) == 0) {return false;}}/* 增加键值对数量 */IncreaseSize(1);/* 插入位置后面的元素后移 */for (int i = GetSize() - 1; i > insert_pos; i--) {array_[i] = array_[i - 1];}/* 在插入位置插入 */array_[insert_pos].first = key;array_[insert_pos].second = value;return true;
}INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_LEAF_PAGE_TYPE::MoveHalfDataTo(B_PLUS_TREE_LEAF_PAGE_TYPE *des_page) {for (int i = 0; i < (GetMaxSize() + 1) / 2; i++) {des_page->array_[i] = array_[GetMaxSize() / 2 + i];}des_page->SetSize((GetMaxSize() + 1) / 2);SetSize(GetMaxSize() / 2);
}

内部节点的插入和数据移动操作

INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::Insert(const KeyType &key, const ValueType &value, const KeyComparator &comparator) {assert(GetSize() < GetMaxSize());int insert_pos = 1;  // 用于记录插入位置/* 查找插入位置 */while (insert_pos < GetSize() && comparator(array_[insert_pos].first, key) < 0) {insert_pos++;}/* 增加键值对数量 */IncreaseSize(1);/* 插入位置后面的元素后移 */for (int i = GetSize() - 1; i > insert_pos; i--) {array_[i] = array_[i - 1];}/* 在插入位置插入 */array_[insert_pos].first = key;array_[insert_pos].second = value;
}INDEX_TEMPLATE_ARGUMENTS
void B_PLUS_TREE_INTERNAL_PAGE_TYPE::InsertAndMoveHalfDataTo(B_PLUS_TREE_INTERNAL_PAGE_TYPE *des_page, const KeyType &key, const ValueType &value, const KeyComparator &comparator,  BufferPoolManager *buffer_pool_manager) {/* 将源页面中的数据和待插入的数据整合在一个vector中 */std::vector<MappingType > tmp_array(GetMaxSize() + 1);int i = 0;int j = 0;while (i < GetMaxSize()) {if (comparator(array_[i].first, key) < 0) {tmp_array.at(i) = array_[i];i++;} else {break;}}tmp_array.at(i++) = std::make_pair(key, value);while (i < GetMaxSize() + 1) {tmp_array.at(i) = array_[i - 1];i++;}/* 将整合好的数据对半分配到两个子页面中，其中目标页面的首个key值用作哨兵，以保存要向两个页面的父页面中插入的key值。 */for (i = 0; i < (GetMaxSize() + 1) / 2; i++) {array_[i] = tmp_array.at(i);}for (i = (GetMaxSize() + 1) / 2; i < GetMaxSize() + 1; i++, j++) {des_page->array_[j] = tmp_array.at(i);auto child_page =reinterpret_cast<BPlusTreePage *>(buffer_pool_manager->FetchPage(des_page->ValueAt(j))->GetData());child_page->SetParentPageId(des_page->GetPageId());buffer_pool_manager->UnpinPage(child_page->GetPageId(), true);}des_page->SetSize((GetMaxSize() + 1) / 2);SetSize((GetMaxSize() + 1) / 2);
}