锐游网
您的当前位置：首页CMU15-445 Project 2 B+Tree 详解

CMU15-445 Project 2 B+Tree 详解

来源：锐游网

本系列文章将以倒序的顺序回顾自己在写Spring23的Projects时的主要思路以及遇到的问题，往期文章：

前言

根据课程组以及相关网友的反馈，Project 2是CMU15-445中最难的一个Project。我个人做下来的感觉是这个Project是所有Project中最喜欢的一个：不仅是因为从Project2中从零实现了一个完整的B+树结构，更是因为完成这个Project后确实会给人一种微微的成就感。同时从这个Project中还学习到了C++多线程的Log的写法，锻炼到了很多代码结构设计的能力，非常有收获。

Project 2 的主要目标是实现一个支持多线程并发的B+树索引，支持节点的单点查询、区间查询、插入、删除等操作，并使用“螃蟹步伐”的加锁方式实现多线程安全。在编写过程中，可以参考课程组提供的与自己实现的B+树进行对比以debug。

在开始写Project 2之前，建议观看课程组的Lecture7-9视频以及参考书Database System Concepts 中14.3的内容，了解B+树的结构以及特性。

再次强调，不要公开自己的作业代码，尊重Mr.Pavlo与助教们的劳动成果～本文也仅会展示主要思路，不会展示个人代码（课程组Starter Code除外）。

需要了解的内容

B+树

在Project 2，我们只考虑unique key的情况，关于duplicate key的讨论可以参考TextBook。此外，在课程视频中，Andy曾提到B+树的命名由来众说纷纭，这里也就不去纠结，直接先介绍一下B+树的结构，之后再介绍与B树、HashIndex的对比。

B+树首先是一个多路平衡树，即任何叶节点到根节点的距离均相等，有如下的性质：

以上就是B+树的主要结构，在Project 2中，以上提到的values均是指针。相比之下，B树（也称B-树，这里的-主要是连接符的作用，但也有人因此称其为B减树，与B树是一个概念）在非叶子节点中也会存储data，并且叶子节点之间没有指向下一个的指针。

相比于B树，B+树有如下优点：

  1. 非叶子节点不存储data，所以一页能够装入的节点数更多，内存能命中的概率更高，索引效率也就更高。
  2. 查询时间稳定，所有的查询肯定都会遍历到叶子节点。（个人感觉这个不能算是优点，在我看来对于单点查询而言，遍历到叶节点反而没有有可能只遍历到非叶子节点的B树快？）
  3. 支持区间查询。

相比于Hash索引，B+树索引虽然可能在单点查询上速度没有哈希索引快（前提是要查找的index在内存中），但同样具有以上优势。

本地可视化：

在Starter Code中，课程组为我们提供了可视化的一些代码（不要更改这些代码）。我们在实现过程中可以利用这一工具可视化我们自己构建的B+树，以便及时fix bug。具体使用上可见Handout，这里提几点使用技巧：对于以文件形式插入/删除的节点，txt文件里只需写对应的key即可，无需指明操作。

此外，注意本地可视化与的区别：本地的节点上所标注的page id可能会大于在线可视化中的page id，如下图所示：

区间查询的支持

在P2的测试中，并没有涉及到区间查询的内容。但是，由于Task3里实现了相关的迭代器，所以要实现区间查询功能其实并不困难。

debug方法

由于P2的测试用例中涉及到多线程测试，所以参考码呆茶的文章中打log的方式（见参考），自己在完成全部代码后，使用宏定义的方法进行了Log的输出，并在每一行输出前均先输出对应的线程号，以区分不同的线程。

#ifdef MY_P2_DEBUG_LOG
  auto debug_log = std::stringstream();
  debug_log << "thread: " << std::this_thread::get_id() << " , Insert"
            << ": " << key << ": " << value << " ";
  LOG_DEBUG("%s", debug_log.str().c_str());
#endif

Project 4 B+Tree

Handout中有这样一句话：

即所有涉及到page的操作均使用bpm，不要使用new、delete等操作，避免内存泄漏。这也是为什么我自己的实现中可视化后一些节点的Page Id会大于在线可视化。

Task1

实际实现中，所有的node都是通过page的形式实现，并通过BPM进行读写。Task1的主要任务就是完善一下三个Tree page的代码，其中b_plus_tree_page为internal page与leaf page的父类，可以认为是后两者的header，包含了max_size_，size_以及page_type_信息，分别表示当前页节点的节点value的最大size、当前size以及节点类别（叶节点、非叶节点）。

对于b_plus_tree_internal_page，则主要是一些Get与Set函数，这里有两个地方需要特别注意一下：

  1. 考虑到internal page的keys数量与values不一样，BusTub在实现时让internal page第一个{key, value}键值对的key始终为空。所以，在对internal page初始化时，需要Init size为1。
  2. b_plus_tree_internal_page有这么一个成员：MappingType array_[0];，其中MappingType就是键值对，而array_[0]是什么？
    实际上，array_[0]是Flexible array，直译过来叫灵活数组，通常在顺序上为最后一个定义的成员。我们知道，bpm fetch的page并不是tree page，拿到对应的page后需要将其中的data reinterpret cast为对应的tree page。而tree page里的键值对数量会变，这就导致我们在定义时无法知道键值对数组的大小应该定义为多少。但我们能够确定bpm fetch的page大小是一个定值，所以这里使用Flexible array，将page转换为tree page后，其内部空间的头部地址会自动对齐header（即b_plus_tree_page中的成员），剩下的空间则由Flexible array自动填充。更详细的介绍可以看十一的文章（见参考），里面对于Flexible array的图文讲解非常清晰。

了解了b_plus_tree_internal_page后，b_plus_tree_leaf_page的结构大同小异，多了一个成员next_page_id_用于指向下一个叶节点。

除了以上三种page，P2中还会涉及到b_plus_tree_header_page。这个page的作用主要是存放root_page_id_，以便在后续的task中上锁，具体的我们放在Task4详解。

这里还有这么几点需要注意：

  1. internal page 与 leaf page的values不同，前者为指向子节点的指针（其实就是page id），后者为RID，所以两者的max size可能不同。这一点在Handout中也有指出，但我自己在实现时没有过多关注这一点，基本上max_size_都通过外部直接Set了。
  2. 与书中伪代码结构上的区别：TextBook中internal page的键值对结构是{value, key}，与实际实现中的{key, value}结构并置首个key为空的结构不同，后面需要注意区分，不要混淆。
  3. b_plus_tree_page的GetMinSize函数需要根据page type进行返回，这里不用考虑为根节点的情况（可以思考一下为什么）。

总体而言，Task1主要就是以上内容，没有什么特别繁琐复杂的地方。

Task2A

在开始Task2之前，再次强调，所有对page的存取操作均使用我们在P1例实现的Buffer Pool Manager完成（下文简称bpm），并且使用P1里实现的pageguard相关函数。

Task2a的主要内容是实现Insert与Search，即{key, value}的单点插入与单点查询，我们先分析一下Context类。

class Context {
 public:
  // When you insert into / remove from the B+ tree, store the write guard of header page here.
  // Remember to drop the header page guard and set it to nullopt when you want to unlock all.
  std::optional<WritePageGuard> header_page_{std::nullopt};

  // Save the root page id here so that it's easier to know if the current page is the root page.
  page_id_t root_page_id_{INVALID_PAGE_ID};

  // Store the write guards of the pages that you're modifying here.
  std::deque<WritePageGuard> write_set_;

  // You may want to use this when getting value, but not necessary.
  std::deque<ReadPageGuard> read_set_;

  auto IsRootPage(page_id_t page_id) -> bool { return page_id == root_page_id_; }
};

Context的作用主要是在对B+树进行遍历时，保留当前节点的祖先节点。具体的就是将祖先节点push至对应的set里，并自动加上对应的read/write lock。同时这里的header_page_成员也会对header page自动上锁。当我们需要获得当前节点的父节点时，直接从set的back即可拿到。

Search

Search的思路比较明了，从根节点出发，在每一层使用二分找到对应的value向下遍历，直到叶子节点。具体的伪代码如下，这部分建议脱离书上的伪代码自己动手实现。

图片来源：Database System Concepts

这里的while循环里的条件就是使用ctx + As<BPlusTreePage>()->IsLeafPage()完成的，并且当我们拿到internal page的某一个value（page id）时，可以调用bpm的fetch相关函数获取对应的page。此外，二分可以直接调用std::lower_bound，但需要自定义一下比较函数。注意array_中存放的是MappingType，而我们二分查找的是KeyType，这里需要进行额外的处理。

建议每拿到一个page，都将其push至read_set_并pop_front()以对祖先节点解锁。最后返回前可以检查ctx的set是否已清空。

Insert

Insert相对复杂一些，因为可能涉及到递归：当向一个节点插入一对{key, value}时，value的size有可能大于max_size_，此时就需要对该节点进行分裂，产生两个节点以及一个中间的key，并将这个key插入至父节点，递归向上。这部分具体的伪代码同样在TextBook中有给出，这里结合我自己的实现简单介绍一下：

  • Insert{key k, value v}：

    1. 首先判断当前树是否为空，若是，创建一个空的叶节点作为根节点并插入。
    2. 使用Search中的方法找到待插入的叶子节点。这一步我封装为了一个FindLeaf函数，在函数内部需要维护ctx的write_set_，保存叶节点在遍历路径上的祖先节点。
    3. 判断key是否已存在，若是，返回false。
    4. 如果当前叶节点的size小于max，那么直接将{key, value}插入至对应位置并返回true。
    5. 否则，我们需要对当前叶节点进行分裂：
      1. 记当前节点为L，使用bpm创建一个新节点L'，创建一个临时节点Temp。
      2. 将L的所有键值对拷贝至Temp，并将{k,v}插入至Temp。这里的Temp我们可以视为足够容纳所有待插入的键值对。
      3. 令L'的next_page_id_为L的next_page_id_，L的next_page_id_改为指向L'.
      4. 抹去L上的所有键值对，并将前⌈N / 2⌉（N为Temp中键值对个数）拷贝至L，余下的拷贝至L'。
        这一步实际实现中，我仅仅修改了L的size，省去了来回拷贝的麻烦。 对于size后的键值对，我不去care，因为我的实现能保证访问array时不会访问到超过size的地址，并且size增加时必定伴随着数据的写入。
      5. 记L'中的最小key为K'，（即L与L'中间的Key）调用Insert_Parent递归将其插入至祖先节点，之后返回true。

  • Insert_Parent(L, k’, L’):

    1. 如果L为根节点
      创建一个新的internal类型根结点，使其具有两个value、一个key，对应Insert_Parent的参数，之后返回。
    2. 否则，记L的父节点为P，可以通过ctx得到。
    3. 如果P的value数量小于max_size，直接插入键值对{k', L'}；否则，split P：
      1. 创建一个临时节点Temp，将P的所有键值对拷贝至Temp，并将{k',L'}插入至Temp。
      2. 抹去P的所有键值对，创建新的节点P'。
      3. 记k''为T中第⌈(n+1) / 2⌉个key（向上取整，从1开始计数）。
      4. 将Temp中的{null, v1}, {k1, v2}, ... , {k(⌈(n+1) / 2⌉-1), v⌈(n+1) / 2⌉}拷贝至P；{null, v(⌈(n+1) / 2⌉+1)}, {k(⌈(n+1) / 2⌉+1), v(⌈(n+1) / 2⌉+2)}, ... , {k(n), v(n+1)}拷贝至P'。这一段可能比较复杂，简单说就是以k''为界，前面的拷贝至P，后面的拷贝至P', k''不进行拷贝。实际实现时方法同Insert函数。
      5. 递归调用Insert_Parent(P, k'', P')。

第四步中Temp里的value比key多一个，由于拷贝时没有拷贝k''，所以对于拷贝的数据，value会比key多两个，满足要拷贝给两个internal pages的要求。注意第一个key均为null。

以上函数的参数中，L可以用page id表示，同时省略了ctx参数。记得维护ctx的write_set_、header_page_与root_page_id_，并及时释放。此外，注意及时dropTemp的page guard。

完成Insert后，就可以在gradescope上提交CheckPoint One的在线测试了。这部分测试没有什么非常复杂的地方，建议一定通过在线测试后再进行后续的实现，因为后续的实现都是基于CheckPoint One的实现进行的。

Task2 B

Delete

Delete（代码里是Remove）应该是P2里最复杂的一个，不是Insert的逆过程那么简单。当某个节点删除了一个键值对后，size可能会不满足min要求，因此我们需要merge或者redistribute。TextBook中同样有相对的伪代码，但并不完整，有几处地方需要额外添加一些内容。与Insert一样，这里我根据自己的实现，记录一下思路。

Delete首先调用上文中提到过的FindLeaf方法找到对应的leaf page，并判断是否存在需要delete的key。若不存在，直接返回；否则，调用递归函数delete_entry。

delete_entry(L, k, v):

  1. 首先，在L的array_中删除k, v。
  2. if L为根结点
    1. if L只有一个value，即size == 1，将唯一的这个child作为新的根结点，删除L并返回。
    2. if L没有value，即size为0，直接删除L并返回。（相当于成为了一棵空树）
    3. 以上均不满足，直接返回。
  3. 如果L此时的size小于min
    1. 记与L相邻的节点为L'。这里取左右均可，我的实现里优先取左兄弟节点。
    2. 记k'为父节点P中L与L'之间的key。
    3. 若L与L'的键值对数量之和满足限制条件，即在[min, max]内部，则合并两个节点。
      1. 这里我们的策略为将右边的节点data合并至左边，所以称左边的节点为Left，右边的为Right。
      2. 若Left为叶子节点，将right所有的键值对追加至left尾部，并将left的next_page_id_设为right的next_page_id_。若Left为非叶子节点，将k'与right的所有键值对追加至left尾部。
      3. 删除节点right，递归调用delete_entry(P, k', L)，返回。
    4. 若不满足限制条件，说明需要redistribute，即从兄弟节点borrow一个节点过来。
      1. 如果L'为左兄弟，且为叶子节点：
        1. 从L'中删除最后一对键值对{kn, vn}，并将这对键值对加至L的开头
        2. 使用L中现存的第一个key，即kn替换P中的k'。返回，不递归调用。
      2. 如果L'为左兄弟，且为非叶子节点：
        1. 从L'中删除最后一对键值对{k(n-1), vn}，并将键值对{vn, k'}加至L的开头，注意这里加的是k'！
        2. 使用刚刚从L'中移除的key，即k(n-1)替换P中的k'。返回，不递归调用。
      3. 如果L'为右兄弟，且为叶子节点：
        1. 从L'中删除第一对键值对{k0, v0}，并将这对键值对加至L的末尾
        2. 使用L'中现存的第一个key，即k1替换P中的k'。返回，不递归调用。
      4. 如果L'为右兄弟，且为非叶子节点：
        1. 从L'中删除第一个keyk0以及第一个valuev0，注意这里v0的位置在k0前面。将键值对{k', v0}加至L的末尾，注意这里加的是k'！
        2. 使用刚刚删除的key，即k0替换P中的k'。返回，不递归调用。

这里实际判断某个节点是否为叶子节点时使用了template，而对节点的删除则用的是bpm的DeletePage，同时drop对应的page guard。此外，兄弟节点也要加锁，防止两个delete同时选择里同一个兄弟节点。TextBook中没有给出4.3、4.4的伪代码，这里补充的为个人实现思路，仅供参考。同样，记得维护ctx以及及时drop。

以上，完成delete并通过相关的测试后，个人认为P2的主要内容就完成了，剩下的两个Tasks远没有上面的复杂。

Task3 - An Iterator for Leaf Scans

Task3的内容就是实现一个叶节点内键值对的迭代器，在初始化时指向第一个节点的第一个键值对，++时则向后遍历，当到达当前leaf page的末尾时，遍历下一个leaf（如果有）即可。

Task4 - Concurrent Index

我自己在实现Task2的Findleaf时（注意与Search的GetValue函数是不同的），便已经维护好ctx里面的write队列，所以这个task做起来也比较顺手。简单说，这里使用的策略是latch crabbing technique，我个人将其翻译为“蟹步”，即螃蟹步伐。其具体内容为对于Read，每当获得一个子节点的read latch时，立刻释放父节点的锁；而对于write，每当获得一个子节点的write latch时，如果当前节点为安全的，那么立刻释放所有的祖先节点的锁，否则，继续向下遍历。那么，何为安全状态？

  1. 对于Insert，如果当前节点插入一个键值对后不发生Split，则认为其是安全的。
  2. 对于Delete，如果当前节点删除一个键值对后不发生Merge或者Redistribute，则认为其是安全的。

显然，安全不安全可以通过节点的size进行判断。而对节点的加锁解锁只需对ctx对应的set进行push和pop操作即可。我们需要修改的代码其实也主要集中在Findleaf函数中。想象一下，每次进行加锁时，先获取子节点的锁，一条腿往下探了一步；之后再根据情况对祖先节点解锁，另外的腿再往回收，着实很像螃蟹😂。

这里再回顾一下为什么要有header page：因为insert/delete里有递归，而这个递归的参数是page id，主要作用于父节点有效；如果不锁住父节点那么很可能对当前节点进行改动，而root无父节点，所以需要header page来锁住root。

个人注意事项

这一节总结了个人实现过程的注意点以及遇到的一些BUG，有比较强的个人主观性，建议跳过

  • 对于LeafNode，自己直接将max_size_设置为了阶数N而非N-1，在调用GetMaxSize时会对返回值-1进行判断是否超出上限。对于最小值，则直接返回max_size_ / 2，其值与⌈(N-1)/2⌉相等。
  • 及时Drop以Unpin bpm里的page，否则会造成无法Fetch的情况。
  • 代码冗余造成了很多bug。。。(;´༎ຶД༎ຶ`)

总结

总结下来，P2的思路似乎非常清晰。但P2真正的难点在于细节上，例如什么时候该将节点push至ctx，什么时候pop，节点内部array_拷贝时具体应该拷贝哪几个data、拷贝到哪里，诸如此类的各种细节，都隐藏着大大小小的bug。这里也由于篇幅的原因，无法一一指出，只有自己实现了才能有更深的体会。

还有一点就是一定要减少代码冗余！！！由于涉及到大量leaf、非leaf，left、right的操作，如果不减少代码冗余，很多代码都是极其相似的，导致有时候一个bug很可能只会fix了一半。

最后，能够独立实现这样一个复杂的数据结构，真的很开心～ (^_^)v

参考

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019- 版权所有

Top