CMU15-445 bustub Project2：B+ Tree

Project2是自己实现一个B+树，CMU对于本次项目一共给了两个checkpoint，首先就是对B+树的基本操作以及基本结构的实现，包括插入、删除、查找，第二个则是对于并发访问的支持。本次项目虽然只是实现一个B+树，但是由于涉及到了前一章的BufferPoolManger，需要注意的细节非常多，所以还是花了不少时间。

对于此类数据结构，可以参考一个网站，可以很好的使用图形化理解其变化过程:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

对于B+树的介绍就不在此赘述了，百度有很多解释，同时看了前两篇博客，源代码太多了反而影响阅读，因此本篇以讲解思路为主，记录遇到的问题和需要注意到的细节，接下来进入正题。

B+树的基本数据结构

B+树中有内部节点和叶节点两种结构，它们存储的数据格式和内容不同。在此项目中，CMU为我们提供了一个基类BPlusTreePage,包含节点类型、当前容量、父节点信息等，规定 parent_page_id_ 为 INVALID_PAGE_ID 表示根节点；内部节点BPlusTreeInternalPage和叶节点BPlusTreeLeafPage都继承自BPlusTreePage，节点利用pair<KeyType, ValueType>的数组来进行数据存储：

#define MappingType std::pair<KeyType, ValueType>
// Flexible array member for page data.
  MappingType array_[1];

对于内部节点，其储存的第一个键是无效的，即其理论结构为： <无效键，指针，键，指针，键…，键，指针>

而对于叶节点，其储存的键和指针都是有效的，即其理论结构为： <键，指针，键，指针，键…，键，指针>

内部节点虽然实现时存储的都是范式中的ValueType，但实际存储的就是叶结点的page_id，而叶节点存储的则是实际的数据的指针,这也对应B+树的性质，内部节点不保存实际数据，实际数据的相关信息都保存在叶结点中。由于要得到实际数据还需要利用BufferPoolManager来获取，因此该数据库中的索引均为非聚簇索引

array_[1] 等价于一个指针，但是其指向的数据并不需要我们new，而是由上一章我们实现的Buffer Pool Manager来分配，其分配的页的data即是我们需要的value，因此此处也需要用到reinterpret_cast(关于reinterpret_cast可以咨询gpt)。

节点对象的生命周期由我们上节实现的 BufferPoolManager 管理：取一个页面，用 FetchPage；使用结束归还一个页面，用 UnpinPage。因此，我们可以得到BPlusTreePage 中 page_id_ 成员的另一个含义：它不仅是 B+ 树中节点的编号，同时也是这个节点使用的 Page 在 BufferPool 中的编号，也可以理解为起到一个"指针"的效果。

写在前面：如果发现gradescope有一个测试总是过不了，大概率是Unpin和fetch的问题，没能保持一致导致空间溢出了，可以在BFM中相应的函数中打印日志来debug，这个过程是极其痛苦的。

了解了数据结构，接下来就是实现B+树的基本操作了，包括插入、删除、查找。

B+树基本操作

查找(GetValue)

查找的逻辑比较简单，给定一个键 x ，查找其是否在 B+ 树中存在。实现逻辑是先找到键可能在的叶节点，然后扫描一遍叶节点的内容确定是否存在。重点则是在找叶节点：

• 从根节点开始，每次在内部节点中查找 x 所在的指针即value，实际是一个page_id，直到叶节点
• 循环时找内部节点中第一个比 x 大的键，取其左侧的值即可（k[0]无效），而这样不能探测到 x 比所有 k 都大的情况，所以要将 next_page_id 初始化为最右侧的键,即next_page_id = internal_page->ValueAt(internal_page->GetSize() - 1);

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::FindLeaf(const KeyType &key) -> Page *{
  page_id_t next_page_id = root_page_id_;
  while (true) {
    Page* page = buffer_pool_manager_->FetchPage(next_page_id);
    auto next_page = reinterpret_cast<BPlusTreePage *>(page->GetData());
    if (next_page->IsLeafPage()) {
      return page;
    }
    auto internal_page = static_cast<InternalPage *>(next_page);

    // init next_page_id as the rightmost pointer
    next_page_id = internal_page->ValueAt(internal_page->GetSize() - 1);
    // if fount a greater key , set next_page_id as the pointer at its left
    for (int i = 1; i < internal_page->GetSize() ; i++) { // ignore first key
      if (comparator_(internal_page->KeyAt(i), key) > 0) {
        next_page_id = internal_page->ValueAt(i-1);
        break;
      }
    }
    buffer_pool_manager_->UnpinPage(internal_page->GetPageId(),false);
  }
}

找到叶结点后再GetValue中只需要遍历叶结点的键和key来比较就行了，同时一定要记得UnpinPage

插入(Insert)

B+树的插入流程如下：

• 如果树为空，则创建根节点，并将其作为叶节点插入，对于每次root_page_id_ 更新时都要调用一次 UpdateRootPageId。
• 利用查询中的函数从根节点向下查找到键值应该所在的叶节点。如果叶结点已经存在该值，则直接返回false即可。
• 如果叶节点 插入后 达到了 max_size，则要进行分裂（split），创建一个新的叶节点，将原节点的一半内容拷贝到新节点，分裂点的键插入父节点，该键对应的值指向新的叶节点。
• 如果父节点不存在，说明是第一个叶节点兼根节点，需要创建一个新的根
• 如果父节点（内部节点）插入前 达到了 max_size，也要递归进行分裂并向上插入，同时将原节点的一半子节点的 parent_id_ 指针指向新的内部节点。如果根节点满了，则要创建一个新的根节点，使得 B+ 树长高一层。
• 同时要注意叶结点和内部节点判断满的条件是不一样的，叶结点在插入后等于max_size则需要分裂，而内部节点在插入前等于max_size则需要分裂并向上插入。

核心代码如下：一些辅助函数就不给了，函数名字基本就彰显了其作用

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::Insert(const KeyType &key, const ValueType &value, Transaction *transaction) -> bool {
  if (IsEmpty()) {
    Page *page = buffer_pool_manager_->NewPage(&root_page_id_);
    UpdateRootPageId(1); // 1 means inserting a new root page
    auto leaf_page = reinterpret_cast<LeafPage *>(page->GetData());
    leaf_page->Init(root_page_id_,INVALID_PAGE_ID,leaf_max_size_);
    leaf_page->SetKeyValueAt(0,key,value);
    leaf_page->IncreaseSize(1);
    leaf_page->SetNextPageId(INVALID_PAGE_ID);
    buffer_pool_manager_->UnpinPage(root_page_id_,true);
    return true;
  }

  Page *page = FindLeaf(key);
  auto leaf_page = reinterpret_cast<LeafPage *>(page->GetData());
  for (int i = 0; i < leaf_page->GetSize() ; i++) {
    if (comparator_(leaf_page->KeyAt(i), key) == 0) {
      buffer_pool_manager_->UnpinPage(leaf_page->GetPageId(),false);
      return false;
    }
  }

  leaf_page->Insert(key,value,comparator_);
  if (leaf_page->GetSize() < leaf_max_size_) {
    buffer_pool_manager_->UnpinPage(leaf_page->GetPageId(),false);
    return true;
  }

  //leaf page is full , split it
  page_id_t new_page_id;
  Page *new_page = buffer_pool_manager_->NewPage(&new_page_id);
  auto new_leaf_page = reinterpret_cast<LeafPage *>(new_page->GetData());
  new_leaf_page->Init(new_page_id,leaf_page->GetParentPageId(),leaf_max_size_);
  new_leaf_page->SetNextPageId(leaf_page->GetNextPageId());
  leaf_page->SetNextPageId(new_page_id);
  //move half data to new leaf page
  leaf_page->MoveDataTo(new_leaf_page,(leaf_max_size_ + 1)/2);

  BPlusTreePage *old_tree_page = leaf_page;
  BPlusTreePage *new_tree_page = new_leaf_page;
  KeyType split_key = new_leaf_page->KeyAt(0);

  // recursively insert 
  while (true) {
    // if the old page is root , create a new parent internal page as root
    if (old_tree_page->IsRootPage()) {
      Page *new_page = buffer_pool_manager_->NewPage(&root_page_id_);
      auto new_root_page = reinterpret_cast<InternalPage *>(new_page->GetData());
      new_root_page->Init(root_page_id_,INVALID_PAGE_ID,internal_max_size_);
      // split_key next is not used , just a placeholder
      new_root_page->SetKeyValueAt(0,split_key,old_tree_page->GetPageId());
      new_root_page->SetKeyValueAt(1,split_key,new_tree_page->GetPageId());
      new_root_page->IncreaseSize(2);
      old_tree_page->SetParentPageId(root_page_id_);
      new_tree_page->SetParentPageId(root_page_id_);
      UpdateRootPageId();
      buffer_pool_manager_->UnpinPage(root_page_id_,true);
      break;
    }

    // otherwise
    page_id_t parent_page_id = old_tree_page->GetParentPageId();
    Page *parent_page = buffer_pool_manager_->FetchPage(parent_page_id);
    auto parent_internal_page = reinterpret_cast<InternalPage *>(parent_page->GetData());
    parent_internal_page->Insert(split_key,new_tree_page->GetPageId(),comparator_);
    new_tree_page->SetParentPageId(parent_internal_page->GetPageId());
    if (parent_internal_page->GetSize() <= internal_max_size_) {
      buffer_pool_manager_->UnpinPage(parent_page_id,true);
      break;
    }

    // parent is also full
    page_id_t new_page_id;
    Page *new_page = buffer_pool_manager_->NewPage(&new_page_id);
    auto new_internal_page = reinterpret_cast<InternalPage *>(new_page->GetData());
    new_internal_page->Init(new_page_id,parent_internal_page->GetParentPageId(),internal_max_size_);
    int new_page_size = (internal_max_size_ + 1) / 2;
    int start_index = parent_internal_page->GetSize() - new_page_size;
    for ( int i = start_index, j = 0 ; i < parent_internal_page->GetSize(); ++i,++j) {
      new_internal_page->SetKeyValueAt(j,parent_internal_page->KeyAt(i),parent_internal_page->ValueAt(i));
      Page *page = buffer_pool_manager_->FetchPage(parent_internal_page->ValueAt(i));
      auto tree_page = reinterpret_cast<BPlusTreePage *>(page->GetData());
      tree_page->SetParentPageId(new_page_id); // modify child's parent
      buffer_pool_manager_->UnpinPage(tree_page->GetPageId(),true);
    }
    parent_internal_page->SetSize(internal_max_size_ - new_page_size + 1);
    new_internal_page->SetSize(new_page_size);

    buffer_pool_manager_->UnpinPage(old_tree_page->GetPageId(),true);
    buffer_pool_manager_->UnpinPage(new_tree_page->GetPageId(),true);
    old_tree_page = parent_internal_page;
    new_tree_page = new_internal_page;
    split_key = new_internal_page->KeyAt(0);
  }

  buffer_pool_manager_->UnpinPage(old_tree_page->GetPageId(),true);
  buffer_pool_manager_->UnpinPage(new_tree_page->GetPageId(),true);
  return true;
}

删除(Remove)

在实现删除之前需要先将迭代器实现了，主要是完成IndexIterator这个类的数据，我设计的成员变量如下：

private:
 // add your own private member variables here
 Page *page_ = nullptr;
 B_PLUS_TREE_LEAF_PAGE_TYPE *leaf_page_ = nullptr;
 int index_in_leaf_ = 0;
 BufferPoolManager * buffer_pool_manager_ = nullptr; 

具体的代码我就不写了，比较简单，主要就是找index_in_leaf_这个索引的值，同时注意在析构函数中UnpinPage，在++操作中要完成跳页的处理(利用GetNextPageId)

在BPlusTree 类，实现三个函数，对于Begin(),我们一路向下找到最左边的叶节点即可，也不赘述了

重点则是B+树的删除操作:

• 如果是空树，返回。否则找到键所在叶节点，从叶节点中删除键值。如果删除后没有下溢出或该叶节点是根节点，返回。
• 如果删除后叶节点下溢出（键值对个数小于 min_size , min_size = ( max_size + 1 ) / 2 ，考察兄弟节点：如果兄弟节点键值对个数大于 min_size ，从兄弟节点借一个键值对（左侧兄弟就借尾，右侧兄弟就借头），同时用借的键替换父节点中该节点位置的键。
• 如果兄弟节点键值对数不够借出，将该节点与兄弟节点合并，更新 next_page_id_，同时删除父节点中该位置的键值。
• 如果删除后父节点（内部节点）下溢出，仍然是借&修改或合并&删除两种方法处理，但规则与叶节点不同：借&修改时，要把兄弟节点的键上移，父节点的键下移给该节点，同时把一个兄弟节点的值给该节点；合并&删除时，要把父节点的键和兄弟节点的键值一块和该节点合并。
• 如果下溢出达到根节点，而且根节点只剩下一个子节点，说明树应该减少一层，将唯一的子节点设为新的根。

INDEX_TEMPLATE_ARGUMENTS
void BPLUSTREE_TYPE::Remove(const KeyType &key, Transaction *transaction) {
  if (IsEmpty()) {
    return;
  }
  Page *page = FindLeaf(key);
  LeafPage *leaf_page = reinterpret_cast<LeafPage *>(page->GetData());
  leaf_page->Remove(key,comparator_);
  if (leaf_page->IsRootPage()) {
    buffer_pool_manager_->UnpinPage(leaf_page->GetPageId(),true);
    return;
  }
  if (leaf_page->GetSize() < leaf_page->GetMinSize()) {
    HandleFlow(leaf_page,transaction);
  }
}

处理溢出的代码就不贴了，太多了，可以看云服务器上的源代码，主要是优先考虑右侧的节点，首先是尝试借，借不到就和兄弟节点合并。

对于叶结点，父节点中更新的键，如果兄弟在左边，则用该节点新的第 0 个键（也就是刚借过来的），在右边用兄弟的第 0 个键即可（兄弟原来的第 1 个键，0 号被借走）。

对于内部节点：

• 如果兄弟节点在左边：父节点中对应的键下移到该节点的key[1]处，兄弟节点的key[size-1]上移变为父节点的key，该节点 value[1] 改为原 value[0]，value[0] 改为兄弟 value[size-1]，兄弟节点 key,value[size-1] 删除。
• 如果兄弟节点在右边：父节点中对应的值右侧的key下移到该节点最右侧，对应value为兄弟节点的value[0]，父节点的key改为兄弟节点的key[1],然后删除兄弟节点的value[0]和key[1]。

对于合并：

• 把右侧节点的键值对插入左侧节点
• 将左侧节点的 next_page_id_ 指针更新为右侧节点的
• 在父节点中移除右节点值位置的键值
• 对于内部节点，我们需要将父节点中右节点位置的 key与右节点 value[0]作为一个键值对插入到左节点的尾部。

并发控制

在cmu的课件当中有针对该部分的知识做讲解，主要是有两种策略，一种是悲观锁，另外一种则是乐观锁。由于查找只需读锁，所以下面悲观锁与乐观锁的区别都是在插入与删除上。
悲观锁：总是先对祖先上写锁，然后对子节点上写锁，如果子节点是安全节点，那么就可以将其祖先结点的所有写锁释放，否则继续持有。
安全节点：

• 如果操作为插入，则没有满的节点为安全节点；
• 如果操作为删除，则超过半满的节点为安全节点；
• 如果操作为读取，则所有节点均为安全节点。

乐观锁：乐观地认为插入/删除不会发生分裂或合并，于是只需沿路径像读取一样获取和释放读锁，然后检查叶节点：如果叶节点安全，那么假设正确，对其更新只需要叶节点的写锁；而如果不安全，说明假设错误，重新像悲观锁一样加一遍锁。

在该项目中，我们需要用到cmu给我们提高的一个参数：transaction，它携带了一个数据库事务的所有信息，这里我们只需要关注其两个成员 std::shared_ptr<std::deque<Page *>> page_set_ 和 std::shared_ptr<std::unordered_set<page_id_t>> deleted_page_set_，分别可以记录 B+ 树查找过程中访问的页面集合和删除的页面集合。同时要注意一个细节，对于根节点的访问我们需要在BPlusTree这个类中定义一个root_latch_来保护，而这个独立定义的锁如何放入 transaction 的 page_set 集合呢？我们规定：在 page_set 中放入一个 nullptr，表示锁定 root_latch_

同时要注意cmu项目任务介绍有提到需要先 Unlock 后 Unpin，因为 Unpin 后这个 Page 的 pin_count_可能降为 0，buffer_pool_manager 可能会将该 Page 指针的内容改写为另一个 Page 的，导致 Unlock 错误

对于确定为安全节点的 Page，我们只需要遍历transaction的page_set，然后释放这里面的祖先的锁即可。