B+Tree
现在正式进入B+树实验的部分, 相关代码都在
概览
本次课程实验实现一个B+树索引。B+树是一种自平衡的多路搜索树，广泛应用于数据库和文件系统的索引结构。与其他树结构（如二叉树、前缀树等）相比，B+树具有更低的树高和更好的磁盘I/O性能，特别适用于大量数据的存储和检索。一棵B+树由内部节点和叶子节点组成，内部节点负责进行索引，叶子节点存储真实数据。你的实现需要支持线程安全的搜索、插入、删除以及一个用于有序遍历叶子节点的迭代器。
实验分为两个阶段：
阶段#1(30分) - 截止日期：5月28号
阶段#2(70分) - 截止日期：6月18号
阶段#1
任务#1 - B+树结点
你需要为你的B+树实现三个类型的节点。
- 节点
- 内部节点
- 叶子节点
BPlusTreeNode是内部节点与叶子节点的基类，只包含两个子类所公有的信息。BPlusTreeNode应该包含以下字段：
| 变量名 | 描述 |
|---|---|
| node_type_ | 节点的类型(internal or leaf) |
| size_ | 该节点当前内部键值对的数量 |
| max_size_ | 该节点最大能容纳的键值对数量 |
你需要在storage/db20xx/src/b_plus_tree_node.cc和storage/db20xx/include/b_plus_tree_node.h两个文件中实现这个类。
一个InternalNode最多能存储个键和个孩子指针。这些键和指针用一个长度为的数组进行存储即可。由于键和指针的数量不同，数组的第一个元素的键应该被忽略，在查找的时候总是从第二个元素开始。
InternalNode始终要保持以下性质：
- size_ = number of children
你需要在storage/db20xx/src/b_plus_tree_internal_node.cc和storage/db20xx/include/b_plus_tree_internal_node.h两个文件中实现这个类。
LeafNode
LeafNode始终要保持以下性质：
值得注意的是InternalNode和LeafNode的可以不同。
你需要在storage/db20xx/src/b_plus_tree_leaf_node.cc和storage/db20xx/include/b_plus_tree_leaf_node.h两个文件中实现这个类。
任务#2a - B+树插入与单点查询
在阶段#1，你的B+属索引必须支持插入(put(key, value))以及单点查询(get(key))。这个索引不支持重复键；如果试图向树中插入一个已经存在的键，就不进行插入，并且返回插入失败。
如果插入操作会破坏B+树的性质，B+树节点应该分裂或进行键的重新分配。如果插入操作会更改根节点，则必须更新B+树索引中的header_node_。
插入的流程如下：
- 如果树为空，创建一个新的根节点
- 找到插入位置所在的叶子节点
- 向中插入键值对
- 如果还有足够的空间，操作完成
- 否则，将分裂为和。将键值对在这两个节点之间平均分配，并且将中间的键复制后插入父亲节点，使得中有指向的指针。
- 如果，有充足空间，则操作完成，否则将分裂为和，键值对平均分配。值得注意的是，与
LeafNode的分裂不同，InternalNode分裂的时候，只需将中间的键插入爷爷节点，无需在或中保留这个中间键。
单点查询的流程则与二叉树的搜索类似，在每次访问InternalNode的时候定位到下一层要去哪个孩子节点查询，访问LeafNode的时候再去查找key对应的value即可。
在进行实现的时候，你会看到一个很奇怪的参数叫VersionChainHead*，这是为了让树支持多个版本的值(与MVCC相关)。你可以认为值的版本构成了一个链表，插入操作可以不覆盖旧的值，而是在版本链的头部插入一个新版本的值。当然你也可以不做多版本的实现，直接将VersionChainHead当作值，插入的时候覆盖旧值即可。
阶段#2
任务#2b - B+树删除
本任务你需要实现键的删除(remove(key))。
如果在删除过程中破坏了B+树的性质，B+树节点应该进行合并或进行键的重新分配。与插入类似，如果根节点被删除了，你需要更新B+树的根节点。
删除的流程如下：
- 如果树是空的，直接返回
- 找到删除位置所在叶子节点
- 删除键值对
- 的size_仍在合法范围内，返回
- size_小于允许的最小值，进行合并或键的重新分配
- 如果是其父节点最右边的孩子，则与左孩子进行合并
- 如果是最左边的孩子，则与右孩子进行合并
- 既不是最左也不是最右孩子，随意
- 你需要自己思考何时进行合并，何时进行键的重新分配
- 重新分配后需要对做什么操作来保证有序性规定？
- 如果上一步中发生了合并，在中删除对应的键和指针
- 如果删除一直传递到了根节点
- 如果根节点是叶子节点(即树只有根节点一个节点)，该做什么？
- 如果根节点是内部节点，并且只剩一个唯一的孩子，该做什么？
任务#3 - B+树迭代器
本任务中，你需要实现一个C++迭代器用于有序便利所有叶子节点的键值对。由于叶子节点存储了它的兄弟节点的指针，迭代器的实现会非常简单。相关的代码在storage/db20xx/include/index.h中，你需要关注ScanIterator这个类。
你的迭代器至少要能支持这四个函数：
任务#4 - 并发索引
最后，修改你的B+树实现，让他支持安全的并发操作。最简单的思路是用一个互斥锁将整棵B+树锁住，在读/写操作的过程中上锁。但本次实验要求细化锁的粒度，每个节点拥有一个互斥锁，在读写的过程中去决定该锁住哪些节点。同时你可以使用Lock Crabbing技术来释放读写过程中不必要持有的父节点的锁来提升你的实现的并发性能。