CMU15445 P2 Checkpoint2

前言

上一篇我们已经实现了B+树，因为本地测试案例里包含了迭代器的实现，所以我们也可以将前三个task作为一个整体

Task3 Index Iterator

Iterator的实现主要在index_iterator文件中，而调用的接口则在b_plus_tree中的begin()、begin(key)、end()函数中

主要的作用就是直接从叶子层遍历整个数据，在一些需要用到连续数据的时候不必每次都从根节点进行遍历

内部实现

迭代器内部的实现主要有以下几个函数

在Iterator类中添加几个成员变量，我这里添加了leaf, index, 还有一个需要的bufferpoolmanager

leaf代表了叶节点，index代表了数据在array中的索引，两个变量即可确定迭代器需要的数据，bufferpoolmanager的作用就是在叶子节点变更时，通过leaf的next_page_id拿到下个叶节点

这里的函数都不难，无非只有**operator++()**内容稍微多一点点，需要区分两个情况

在叶节点中递增
在叶节点间递增

如果是叶节点内递增，index直接++即可；如果是叶节点间进行递增，则可以通过leaf的next_page_id获取其nextpage，同时将index置零即可实现++操作

接口实现

没什么难度，begin()就是在Findeaf的过程中始终拿第一个value，end()则是相反，begin(key)则是查找指定key的迭代器，有点类似GetValue，findleaf可以直接实现。

重要！！！

实现了前三个Task，只剩最后一个并发控制没有实现了。并发控制实现的基础，肯定是之前的B+树索引的正确实现，B+树部分的实现有误，并发控制怎么都不会跑通的。

你以为你过了checkpoint1就代表你的B+树没问题了？

checkpoint1的测试样例弱到查不出B+树的错误，我在Remove函数出错的情况下，提交checkpoint1代码，50分通过。

那该怎么办呢？

Project2文档中有写道

并发设计不允许用全局锁，但是我们可以先上一把大锁来验证一下B+树实现的正确性啊( ﹁﹁ ) ~

所以在前面三个Task的基础上上一把大锁，然后直接将代码交到Gradescope上去，果不其然，一堆报错

开始修改代码，一定要改到用上全局锁之后，全部通过才可以，不然无论你的锁实现的正确与否，都会报错。

保证前三个Task的正确性之后，就来到了最后一个环节，并发控制。

Task4 Concurrent Index

个人认为并发控制不是特别复杂，主要是理解课上讲的latch crabbing机制，先给子节点上锁，再给父节点解锁，不同操作的上锁解锁逻辑不同

GetValue：没有修改数据，所以只用上读锁，读锁非常简单，先拿子节点，上锁，释放父节点上读锁即可
Insert：沿途加写锁，直到遇到安全节点可释放其祖先页面的锁
Delete：沿途加写锁，直到遇到安全节点可释放其祖先页面的锁

重点要梳理的就是插入和删除对安全节点的定义，什么叫安全呢？安全就是该节点的变动不会影响到父节点。那为什么一旦有安全节点，就可以释放祖先页面的锁呢？安全节点不会影响到父节点，其父节点更不会修改祖先页面。

下面重点讨论Insert和Delete对安全节点的定义

Insert：插入后不会分裂

Delete：删除后不会合并

主要的改变在**Findleaf()**函数中，可以先定义一个枚举类

1	enum class Operation {SEARCH, INSERT, REMOVE};

将操作类型和安全条件都放在findleaf中实现

这里还需要用到之前一直都没有用到的Transaction，是一个处理事务的类，这里主要用到其中**AddIntoPageSet()函数，可以通过GetPageSet()**获取存储页面的队列，具体实现自行查阅。这里可以将加了写锁的祖先page加入该队列，在确定安全节点后释放其所有祖先节点，释放要从上向下依次释放，因为上级的锁被争用的更为激烈。

哦对了，千万不要忘记给树一个根锁，为什么还要一个root_latch呢？这里的root_latch不是用来锁住树根节点的，而是整个树的入口，因为当你Insert或者Delete导致树根改变时，如果没有锁住树的入口，那么其他线程的操作可能已经在原来树根的地方排队等候了，等这边树根改变之后释放写锁，后来的进程还会从之前等候的位置等待进入，那么这个时候拿到的节点便不是根节点了。