删除这关也不是那么好过。花了一整天才把代码写完加上BUG调完。
值得幸运的是，内存泄漏的问题在实现中没有发生。
首先我们先来看下书上的伪代码
B+ 树删除伪代码
image.png
然后依据这个，再对照作业里的代码框架开始整理。
Remove 是暴露给CLIENT的调用，思想是找到LEAF PAGE删除掉对应的节点，随后按需看做不做合并或者借节点。
image.png
难点就在于 CoalesceOrRedistribute
里面主要有三件事，第一件如果来的是ROOT PAGE，要做ADJUST ROOT。
如果不是，首要要找到这个PAGE的兄弟PAGE。
然后按照兄弟PAGE和当前PAGE的位置关系，来做2个事情。第一个是当可以合并的时候，走Coalesce。 如果不能合并，就意味着可以借节点。走Redistribute
上述2个函数，都会要去传入一个INDEX的参数。
经过研究我理解了，对于Redistribute，是要求传当前节点在PARENT PAGE里的INDEX的位置。
如果是0的话，就要把后面的第一个节点借过来。如果不是的话，就要把前面的最后一个节点接过来。
那么我们在找兄弟节点的时候，就是先找前面的，如果自己是第一个的情况下，才找后面的兄弟节点。
对于Coalesce来说，需要合并，那么统一把后面PAGE的全部孩子移到前面的PAGE。随后把后面PAGE对应在父节点的节点给删了。那个INDEX就是对应后面的NODE在PARENT的INDEX。
下面代码的思想是按照伪代码来写的。
image.png
FIND SIBLING 就是找到前一个兄弟，只有当自己是头节点的时候，才找后一个同时返回TRUE。
image.png
合并的方法，就是把后面的移到前面的。随后把全部移走的那个节点从PAGE TABLE里删了。然后移除PARENT的节点。最后按PARENT是不是小于阈值，递归。
image.png
这里有个很重要的不同
parent->GetSize() <= parent->GetMinSize()
因为走到这个分支的都是INTERNAL PAGE。
LEAF PAGE 是不用小于等于的，而是直接小于。
原因就是INTERNAL PAGE，最小的SIZE就是2.我们设想MAX SIZE 是4的INTERNAL PAGE。 如果SIZE 是2，那么有效的节点其实只有1个（因为第一个是INVALID KEY），所以等于的情况也是需要做合并的。
如果MAX SIZE是5，SIZE 是3，有效节点是2 的情况可以允许。所以有了这里的小于等于
这里再更新下MINSIZE的计算方法。大家自己琢磨下为什么LEAF PAGE是<
INTERNAL PAGE 是<=
image.png
借孩子的方法也是简单粗暴，不多做解释了。
image.png
AdjustRoot 的分为2个情况，一个是ROOT本身是LEAF PAGE，那么因为只有<= min size 才会被调用。所以一定是空PAGE了，直接删成EMPTY TREE就好。
还有一个ROOT PAGE 不是LEAF PAGE，但是小于2了。就意味他的唯一的孩子 需要继承来做ROOT PAGE。
这里我写的时候忘记SET 他孩子的PARENT PAGE ID 为INVALID_PAGE_ID。后来DEBUG时发现。
image.png
综上B+树的删除写完了。我们还需要去PAGE里实现，PAGE的子方法。
叶子节点的比较简单粗暴，就是直接移动，然后更新NEXT PAGE ID即可。和MOVE HALF TO 差不多的套路，复制下来改改就好。
image.png
而INTERNAL的要麻烦一些。
在调用MOVE ALL TO的时候，因为第一个节点是INVALID的节点，我们需要先去把PARENT指向这个PAGE的KEY的值拿到赋予第一个INVALID KEY。然后再搬过去。
我用图来解释一下。下图来自作业
image.png
我们可以看到在标1的地方，就直接MOVE ALL头把32给移过去即可。
因为删31的时候，会响应删掉整个PAGE在PARENT中的INDEX，也就是30.
这是会触发30的那个INTERNAL PAGE <= minsize ， 就会再触发合并，也要MOVE ALL TO
invalid key指的是第一个没有KEY，只有一根指针的节点，在INTERNAL PAGE里永远是0的位置。
其实我们需要把26给MOVE 过去，但是那个PAGE只有一个INVALID KEY了怎么办呢？
他要把他即将要删除的父节点（图中为根节点的26）先搞下来，放在他INVALID key的位置，随后把这个KEY MOVE 过去。就有了最终的形态。
同时根节点的SIZE为1（只有一个INVALID KEY）就会触发ADJUST ROOT的CASE 2
image.png
做INTERNAL PAGE的时候，再搬节点，都要记得更新孩子上维持的父亲节点。
下面就是移头或者移尾。可以看到INTERNAL PAGE主要多多出来的就是维护孩子的指针那一块。
image.png
image.png
最后实现好了之后就是写测试。
STEP1 继续先针对PAGE写测试。
image.png
STEP2 过送的2个DELETE测试
STEP 3 自己写一个测试DELETE SCALE的测试。
这里有个技巧，比较直观的去看和分析的是，大概MAX KEY是3的时候，我经过研究，把GENERIC KEY设置为16，PAGE SIZE设置为128,可以有这个效果。
image.png
image.png
INSERT 和 REMOVE前都打印下。
image.png
让分裂的时候，奇数的时候前半部分可以拿到更多KEY。只要用TOTAL+1即可。
我之前的实现是后半部分拿到多数的KEY。
其实都可以，但是前半部分多数KEY，在顺序插入的时候会好看一些。
image.png
image.png
不变量的验证
一般一种数据结构，都有特定的不变量，比如BST，比如红黑树。
B+树也不例外。
我们可以根据B+数的特性，得到每一次插入，删除操作后
B+树应该满足。
每个PAGE的SIZE 满>= MIN SIZE, <= MAX SIZE
每个PAGE里面的元素是有序的。
INTERNAL PAGE指向左边的PAGE的最大值小于INTERNAL PAGE的KEY，右边PAGE的最小值，大于等于KEY。
同时每个LEAF 节点到根节点的深度一致。
最后做完操作后，所有PAGE 应该都保持PIN COUNT 为0的情况。
具体的代码，小伙伴可以去我的GIT上，下下来使用。
image.png
使用方法，在INSERT 和 REMOVE的时候，返回前调用。
image.png
因为验证是O N的时间复杂度，所以在处理10000的规模的数据的时候，每一次操作都调用，就是N^2的复杂度，会非常慢。所以我额外加了一些截止，让他再处理大数据集的时候 去批量验证。以提高测试通过速度。当然最简单的方法是注释掉每次INSERT, REMOVE之后的不变量CHECK。
测试内存无泄漏
image.png
这次更新的代码提交到2B FINISH
网友评论