您的B + Tree实现必须隐藏key/value等的详细信息，建议使用如下结构：
template <typename KeyType, typename ValueType, typename KeyComparator> class BPlusTree{ // --- };这些类别已经为你实现了
KeyType: The type of each key in the index. This will only be GenericKey, the actual size of GenericKey is specified and instantiated with a template argument and depends on the data type of indexed attribute.
ValueType: The type of each value in the index. This will only be 64-bit RID.
KeyComparator: The class used to compare whether two KeyType instances are less/greater-than each other. These will be included in the KeyType implementation files.
TASK #2.B - B+TREE DATA STRUCTURE (DELETION)您的B+树索引需要支持删除。如果删除导致某些页面低于占用阈值，那么您的B+树索引应该正确执行合并或重新分配。同样，您的B+树索引只能支持唯一键
TASK #3 - INDEX ITERATOR您将构建一个通用索引迭代器，以有效地检索所有叶子页面。 基本思想是将它们组织到一个链接列表中，然后按照B + Tree叶子页中存储的特定方向遍历每个键/值对。 您的索引迭代器应遵循C ++ 17中定义的迭代器功能，包括使用一组运算符对一系列元素进行迭代的能力，以及for-each循环（至少具有++，==，!=和解引用运算符）。 请注意为了支持索引的每个循环功能，您的BPlusTree应该正确实现begin（）和end()。
您必须在指定的文件中实现索引迭代器。 仅允许您修改头文件（src / include / storage / index / index_iterator.h）及其相应的源文件（src / index / storage / index_iterator.cpp）。 您不需要修改任何其他文件。 您必须在这些文件中的IndexIterator类中实现以下功能。 在索引迭代器的实现中，只要您具有以下三种方法，就可以添加任何帮助程序方法。
isEnd(): Return whether this iterator is pointing at the last key/value pair.
operator++(): Move to the next key/value pair.
operator*(): Return the key/value pair this iterator is currently pointing at.
operator==(): Return whether two iterators are equal
operator!=(): Return whether two iterators are not equal.
TASK #4 - CONCURRENT INDEX在这一部分中，您需要更新原始的单线程B + Tree索引，以便它可以支持并发操作。 我们将使用课堂和教科书中介绍的Latch捕捉技术。 遍历索引的线程将获取然后释放B + Tree页上的Latch锁。 如果线程的子页面被认为是“安全的”，则该线程只能释放其父页面上的Latch锁。 请注意，“安全”的定义可能会根据线程执行的操作类型而有所不同：
Search: Starting with root page, grab read (R) latch on child Then release latch on parent as soon as you land on the child page.
Insert: Starting with root page, grab write (W) latch on child. Once child is locked, check if it is safe, in this case, not full. If child is safe, release all locks on ancestors.
Delete: Starting with root page, grab write (W) latch on child. Once child is locked, check if it is safe, in this case, at least half-full. (NOTE: for root page, we need to check with different standards) If child is safe, release all locks on ancestors.
Hints你必须使用传入的transaction，把已经加锁的页面保存起来。
我们提供了读写锁存器的实现（src / include / common / rwlatch.h）。 并且已经在页面头文件下添加了辅助函数来获取和释放Latch锁（src / include / storage / page / page.h）。
2. Insert实现首先附上书上的b+树插入算法
对上面几种情况的分析
如果当前为空树则创建一个叶子结点并且也是根节点
-- 这里是leaf结点所以这里需要用到leaf page内的函数
-- 注意这里需要用lab1实现的buffer池管理器来获得page。 这里记得创建完新的结点之后要unpin
-- 进行插入的时候用二分插入来进行优化
创建新结点
INDEX_TEMPLATE_ARGUMENTS void BPLUSTREE_TYPE::StartNewTree(const KeyType &key, const ValueType &value) { auto page = buffer_pool_manager_->NewPage(&root_page_id_); if (page == nullptr) { throw "all page are pinned"; } auto root =reinterpret_cast<BPlusTreeLeafPage<KeyType, ValueType,KeyComparator> *>(page->GetData()); UpdateRootPageId(true); root->Init(root_page_id_, INVALID_PAGE_ID ,leaf_max_size_); root->Insert(key, value, comparator_); // unpin buffer_pool_manager_->UnpinPage(root->GetPageId(), true); }