项目文档在这里，这个PROJECT我大概看了下描述。还是比较有挑战的，所以我会写的详细一点。
但和MIT 6.824那样一步步手把手指导，还是会不同。这边我重点挑我认为 不是无脑就可以实现的部分写。
https://15445.courses.cs.cmu.edu/fall2018/project2/
按照CHECK POINT A的描述，大概我们会改动
image.png
在此之前，我建议你做一下HOMEWORK 2 ，我一开始对B+树理解有偏差，做了之后纠正了这个偏差。
下面就是按顺序 依次实现每个文件。
1
最开始就是实现PARENT PAGE，它是INTERNAL PAGE 和 LEAF PAGE的父类。抽出了2个PAGE的共有变量和方法。
难点在于MINPAGE。
image.png
2
下面是是实现，INTERNAL PAGE，也就是B+树的非叶子节点，存储的是ROUTE 信息。
在写INIT的时候，有一个要注意的点就是MAX SIZE怎么算。
因为中间节点，他的第一个KEY是让费的也就是只存指针。所以要减1，同时我们也无法利用全部的PAGE_SIZE，因为每个节点还要存一些HEADER信息。
image.png
LOOK UP是一个二分查找的基本功。
image.png
INSERT 暂时先不动。
3
下面是是实现，LEAFPAGE，也就是B+树的叶子节点，存储的是数据信息。
在这里我们同样减1，这个是为了实现插入 如果发现满了，然后分裂。如果不留这个空间，后续分裂代码的逻辑会十分复杂。算是一个简化代码复杂度的哨兵吧。
image.png
BUG1 上述代码 没有给NEXT PAGE ID 赋初始值
下面又是一个二分查找的基本功
image.png
4
B TREE 里面实现GET，分为3步，第一步找到那个叶子的PAGE，在叶子PAGE里找这个KEY。用完最后UNPIN 这个PAGE。
image.png
image.png
实现FindLeafPage,
大概思路从根PAGE开始找，如果不是LEAF PAGE，调用PAGE的LOOK UP，直到找到LEAF PAGE。
记得FETCH之后 要UNPIN
一开始没明白为啥需要一个LEFT MOST，后来知道，在实现ITERATOR的时候，需要先定位到最左的叶子节点，就是这个作用的。
image.png
那么B+树的查找，基于上面的FUNCTION就很容易了。
首先定位到正确的叶子节点，在叶子节点里运用二分查找。
image.png
5
下面就是开始实现INSERT了。我们来回顾下B+树的INSERT如何做
插入前
image.png
插入后
image.png
伪代码
image.png
image.png
6
按照上述思路，我们再结合下代码里给的接口
INSERT 首先判断树是不是空的，如果是空的，就创建一颗新树。如果不是就把值插到LEAFPAGE里。
创建新树，就是开个NEW PAGE，随后把它的PAGE ID赋值给ROOT PAGE ID，然后再把第一个KEY VALUE PAIR插入进去。
INSERT INTO LEAF PAGE，大概思路是先查找。值存在，就RETURN FALSE。
不存在就插入到LEAF PAGE，如果满就分裂。 分裂就是后半部分的节点 放进一个新的PAGE里，如果是INTERNAL PAGE需要修改孩子的PARENT指针，如果是叶子PAGE需要更新NEXT 指针
分裂完之后，会有一个新的节点插入到PARENT那，如果有需要递归做这件事。
image.png
创建新树，注释里也有讲
image.png
插入LEAF，先找到LEAF PAGE，找到之后看这个KEY有没有，有的话RETURN FALSE。
没有，就做一个插入。
插入后判断需不需要分裂。
分裂之后要调用INSERT TO PARENT，因为后半部分的头节点，要进入父节点对应的位置。
image.png
插入到父亲节点也是根据伪代码实现的
image.png
7 要把INSERT TEST 2个测试跑通，需要实现迭代器
是不是END，如果树还没创建，那么其实节点会是NULL，所以是END。
我们需要在++的时候去判断，如果+了之后，达到SIZE了，这个时候要去用NEXT PAGE 找到下一个，下一个不存在，把节点更新为NULL。
image.png
BUG 2
下面忘记减1，导致写穿ARRAY，修改了内存里下一个PAGE的HEADER 信息，产生BUG
image.png
BUG 3
FALSE 不应该能覆盖TRUE,之前是直接赋值，造成应该刷回磁盘的页没有被刷回。然后出了IO ERROR
image.png
BUG 4
INTERNAL PAGE 和 LEAF PAGE 的MOVE HALF TO 逻辑要注意
举个例子，比如MAXSIZE是4.
对LEAF PAGE来说，最多可以放5个元素（多预留了一个位置为了防分裂前的元素）
分裂后，前面放了2个，后面放了3个。
但对INTERNAL PAGE来说，最多也是放5个。X,1,2,3,4 （X是1的左指针）
但是分裂后前面是放了x,1,
后面是放了2,3,4(2会在函数调用后，被挪到他的父亲节点，等价于被删除，只留下3的左指针的作用）
image.png
BUG 5
内存泄漏
主要是C++的SHARED POINTER的引用计数法的问题。在析构函数里添加如下代码
image.png
创建了针对LEAF PAGE 和 INTERNAL PAGE的测试
创建了小BUFFER POOL，不同KEY SIZE，顺序插入，和随机插入的INSERT 测试。
测试通过，无内存泄漏
最后把2A的代码打包上传（包含测试）
https://github.com/yixuaz/CMU-15445
网友评论