标签：Index cmu15445 Tree page merge 节点 root id 页面

CMU15445 2022 PROJECT #2 B+Tree Index

前前言

本地测试通过是真的比较简单，因为有数据可以单步debug，很快就能定位错误。但是要通过在线评测还是比较痛苦的，没有数据，没办法单步调试，痛苦面具。
由于本次实验比较新，很少有现成的博客参考思路以及踩坑（有些坑真的很蠢，但是要花费很多很多很多时间，甚至2/3的时间都花在一个非常蠢的坑上面），因此我建了一个群，大家一起来讨论交流，共同学习，共同进步吧。
687463684

前言

最近太摆烂了，没啥写代码的动力。没有bug的时候真的不想动代码，有了bug恨不得不睡觉死磕bug。。。。这种状态需要改变一下。
言归正传，时隔一个多月，终于写完了lab2了。本次实验没有任何步骤的提示了，因此全靠个人写了，比以往两次实验挑战性更大。本次lab要求拆分锁，不能一把大锁保平安了，因此并发方面会出现很多奇奇怪怪的错误，并且并发也是比较难以调试的，需要借助一些特殊的工具才能找出“死锁”以及“数据竞争”。本次lab主要实现一个b+树的索引，分为leaf_page，internal_page, b_plus_tree 以及b+树迭代器四个部分。leafpage和internalpage大同小异，b_plus_tree是最折磨的地方，由于迭代器不要求线程安全，因此迭代器比较好写，可能是最好写的一部分了。

B+树的定义或性质(节选自算法导论，非常重要)

一棵B+树是具有以下性质的有根树(根为 \(T.root\) )

每个节点 \(x\) 具有下面属性
- x.n, 当前存储在节点x中关键字的个数
- x.n个关键字本身以非降序存放
- x.leaf 一个布尔值，如果x是leaf node，则为true；如果x是internal node，则为false
每个内部节点x还包含x.n+1个指向其孩子的指针。叶节点没有孩子。
每个leaf node具有相同的深度
每个节点所包含的关键字个数有上界和下界。用一个被称为B+树的最小度数的固定整数t>=2来表示这些界。
- 除了根节点意外，每个节点必须至少包含t-1个关键字。因此，除了根节点以外的每个internal node至少有t个孩子（即t个entry）。
- 每个节点至多可以包含2t-1个关键字。因此，一个internal node至多可有2t个孩子。

本次lab所需要实现的lab和以上定义大同小异。
（注意，测试样例中节点的最大孩子数（即internal_page_max_ 以及 leaf_page_max_）可以根据你自己的需求调整，比如我会向上取整到偶数。声明为3的时候我会将最大孩子数量变为4，因为这样子实现起来方便一些）。
以及实验中其实要求叶节点不能为满（为了实现insert更加便捷）

b_plus_internal_page 以及 b_plus_leaf_page

这个主要是实现节点的一些逻辑，比如在内部节点里面crud（增删改查）key和value。也可以实现不同node之间（通常是兄弟node）的孩子的传递（用于merge以及distribute）。
以实现能多简单就多简单的目的，我直接线性查key了。对性能有需求的同学可以使用二分（虽然我感觉差距不大就是了，因为一页最多也就那么点key，考虑到cpu缓存的影响，二分还有可能比线性还慢）
下面这张图有助于理解节点的构成（摘自lab要求页面）

B_PLUS_TREE

重头戏来了。这个文件实现了b+树的主要逻辑，即增删改查。

查

根据所给的KEY，在每个节点找到对应的入口，直到叶节点为止。查还是比较简单的。

增

增有很多细节。增之前首先需要知道insert到哪里。因此需要先得到对应的叶节点，然后进行插入。如果当前树为空，则增加一个叶子节点，并将这个叶子节点设为根节点。
细节主要是在去向叶节点的过程中，如果遇到满的内部节点，需要将内部节点拆分；如果在插入后，叶子节点满了，则需要将叶子节点拆分。

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.).
这样子做的原因是简单化实现，因为每次叶节点拆分的时候能够保证其父亲节点不满，因此不用递归拆分，拆一次即可。
在叶节点拆分的时候保证拆分出来的节点是原节点的右兄弟节点，因为这样才能方便更新next_page_id_指针（因为是单向链表）。同样的，在之后的merge中，也需要将右节点merge到左节点中。

删

删也是比较难写的，因为涉及到比较多的逻辑。比如是优先merge还是优先distribute。在这里我选择了优先distribute。merge的之后，清零的节点别忘了删除。
以及在增中提到的：merge中，需要将右节点merge到左节点中，然后删除右节点（仅针对叶节点，因为有next_page_id_这一单向链表指针）。
当根节点只剩下一个孩子并且根节点不为叶子节点时，需要将根节点变为当前根节点的第一个孩子也是唯一一个孩子，并删除根节点。

改

删了之后再插入新的即可

并发

本次lab最逆天的地方。因为不能一把大锁锁住了，将面对的是真正的并发所带来的无序性以及数据竞争以及奇怪的死锁。很多奇怪的错误都会在这里出现。因此建议进行防御性编程，多用assert。

并发获取根节点

万事开头难，增删改中，每次获取根节点不仅仅只是Fetch一下，我们需要保证根节点（root_page_id_）的有效性（因为存在root_page_id_的更新，不用锁保护的话会产生数据竞争）以及Fetch出来页面的有效性（在获取root_page_id以及获取页面锁的时候，root_page_id_可能已经改变了）。
首先是保证root_page_id_的有效性，开一把新的锁，每次使用root_page_id_都需要获取这把锁才能读写root_page_id_；其次是每次得到根页面并且上锁之后，需要保证该根页面真的是根页面（通过判断该页面的父节点是否为INVALID_PAGE_ID）。如果不是真的根节点，那么继续获取root_page_id_,循环往复，直到获取到真正的根节点。

并发搜索

针对增，删，查，有很多不同的并发方案。

对于查，不修改数据，因此获取一个节点后，即可释放上一个获取的节点。
对于增加，当获取完一个节点，如果该节点不为满，并且是内部节点，那么就可以释放以前所锁住的节点。
对于删，当获取一个节点后，如果该节点数量大于半满，则可以释放之前所锁住的节点（保证之后删除key之后最多会在这里停止）。

并发细节

在解锁之后unpin，如果在解锁之前unpin，可能会导致页面在解锁之前被evit了，导致页面指针失效。
注意锁的获取顺序。

迭代器

由于迭代器的实现不要求线程安全，因此就比较简单了，这里不多赘述了。

测试

由于自带的本地测试样例过弱，因此建议自己多造一些数据。
也可以写一个Check自检函数，每次插入或者删除后都根据B+树的定义，dfs一遍b+树，检查一下是否有错误。下面我贴一下我的Check函数。

INDEX_TEMPLATE_ARGUMENTS
auto BPLUSTREE_TYPE::CheckTheTree(const page_id_t page_id, const page_id_t parent_page_id) const -> bool {
  BPlusTreePage *page = GETBPAGE(buffer_pool_manager_->FetchPage(page_id));
  // check
  bool chk1 = ((page->GetPageId() == root_page_id_) ||
               (page->GetSize() >= page->GetMinSize() && page->GetSize() <= page->GetMaxSize()));
  bool chk2 = (page->GetParentPageId() == parent_page_id);
  bool chk3 = (page->GetPageId() == page_id);
  bool chk4 = GETPAGE(page)->GetPinCount() == 1;
  bool chk5 = true;
  for (int i = 2; i < page->GetSize(); i++) {
    if (page->IsLeafPage()) {
      if (comparator_(GETLPAGE(page)->KeyAt(i), GETLPAGE(page)->KeyAt(i - 1)) <= 0) {
        chk5 = false;
        break;
      }
    } else {
      if (comparator_(GETIPAGE(page)->KeyAt(i), GETIPAGE(page)->KeyAt(i - 1)) <= 0) {
        chk5 = false;
        break;
      }
    }
  }
  bool res = (chk1 && chk2 && chk3 && chk4 && chk5);
  //  BUSTUB_ASSERT(page->GetPageId() == root_page_id_ || (page->GetSize() >= page->GetMinSize() && page->GetSize() <=
  //  page->GetMaxSize()),"size error" ); LOG_DEBUG("in check %d %d",page->GetParentPageId(), parent_page_id);
  //  BUSTUB_ASSERT(page->GetParentPageId() == parent_page_id, "parent_page_id error");
  //  BUSTUB_ASSERT(page->GetPageId() == page_id, "page_id not match");
  if (!res) {
    buffer_pool_manager_->UnpinPage(page_id, false);
    return false;
  }
  if (page->IsLeafPage()) {
    buffer_pool_manager_->UnpinPage(page_id, false);
    return true;
  }
  for (int i = 0; i < page->GetSize(); i++) {
    if (!CheckTheTree(GETIPAGE(page)->ValueAt(i), page->GetPageId())) {
      return false;
    }
  }
  buffer_pool_manager_->UnpinPage(page_id, false);
  return true;
}

苦逼的提交记录

一个调试的代码忘了删，导致死锁的整整两天（太折磨了）。因为在线测试的数据并不是固定的，因此有时候会死锁，有时候不会。就很折磨

解锁之后再锁上，然后再解锁。。直接导致了死锁。。。。

leaderboard

运行时间不算快。

小敲门之面向OJ编程

在代码中使用LOG_DEUBG(...), 能够在OJ上也输出相应信息。绝活

标签：Index,cmu15445,Tree,page,merge,节点,root,id,页面
From： https://www.cnblogs.com/alyjay/p/16885958.html

[已满分在线评测] cmu15445 2022 PROJECT #2 B+Tree Index