前言

B+树的删除功能的实现,也很复杂,来看一下吧,然后对前面的代码要做一些修正。

正文

首先我们来看下b_plus_tree.cpp文件里面的remove函数,从这里是remove的入口:

先是为空就直接返回,然后找到存在这个key的leaf page,然后调用RemoveAndDeleteRecord函数,返回的是删除后的叶子大小,然后如果是小于最小size会调用CoalesceOrRedistribute函数来进行合并或者重新分配,最后记住unpin一下tar page。

然后我们看下RemoveAndDeleteRecord函数,在leaf page文件中实现

看下删除,首先找到第一个大于等于key值的index,如果firstKeyIndex大于size或者比较找到的firstKeyindex不等于key值,说明没找到相应的key直接返回size大小就行了。找到的话,就利用memmove函数来把后一位开始的element进行移位,注意这里是指针哦,然后大小减一,返回size。

看下CoalesceOrRedistribute是怎么做的最复杂的部分

如果需要合并或者重新分配的是根节点那么需要调整root结点,来看下AdjustRoot函数。我想先来说下根结点的存在方式,根节点是internal page,所以对于第一个index是invalid的,key是空的,value是个左指针指向page或者下面的internal page,然后如果只有大小为1的话那么value指向的是一个page也就是一个leaf page,这种情况的话,我们需要用这个value指向的page来替换我们原来的root page,还有一种情况是直接空了index 0的地方value也是空了的话,那么可以直接删除B+树了,然后我们细看下整个代码。

对于第二种情况,如果这个root page同时也是leaf page,因为能触发这里的话,说明root page size < GetMinSize() = 1,说明这个树空了,直接先unpin这个root page,然后delete这个root page,然后记得更新下root_page_id_因为要更新header信息,然后看下第一种情况,只有index 1的地方有个value指向leaf page,然后我们要拿这个page替换root page,

先是RemoveAndReturnOnlyChild函数,拿到0处的value值,然后size-1,然后return value拿到新的root node的page id

然后更新root_pageid,然后拿到新的page页面进行一次强制转换为internal page,然后更新new root id的信息,然后unpin原来的和新的root page,然后删除老的page。

返回之后我们继续看因为不是根结点的话,需要寻找他的兄弟结点,我们优先找它的前兄弟结点,只有它没有前兄弟的时候才找后兄弟,我们自己添加一个FindSibling函数

因为我们需要寻找兄弟结点,首先需要寻找父节点(因为可能是internal page要找兄弟),找到parent node后先找到当前node的index然后找到sibling node index,记得unpin parent page,然后又分为两种情况,如果sibling node和node合并大小小于max时候合并,否则重新分配他们,然后分两部分看下。

先看合并部分,

我们要保证siblingNode里面的值是前面的值,所以先交换,然后我们拿到需要被remove的page id(我们需要将node的所有element移到钱买呢的sibling page node),然后我们看下Coalsece函数是怎么具体的合并,最后记得unpin parent page

调用MoveAllTo函数来迁移element,这个具体在internal page和leaf page中实现的等会再说,记得unpin自己这个page,然后delete,还要unpin neighbor_node,最后从parent中移除自己的index,简单看下Remove就是简单的array移动下

记得有可能因为parent node减小后也会触发,注意这里是<=,为什么呢,因为我们internal page的第一个index是invalid的,只有value没有key,所以是小于等于。所以需要递归的调用。

之后我们回来看下重新分配

我们先拿下在parent中当前node的index值,然后调用Redistribute

然后看下其中的逻辑,如果node是第一个,那么就把后面结点的第一个element移到node的末尾,否则话就把前面的node的最后一个element移到node的first位置,这两个函数也是leaf page和internal page中具体实现的,最后记得unpin这两个node。

之后我们来看下之前的几个函数在internal page和leaf page中的具体实现

先看MoveAllTo函数在leaf page

把node的element都移到recipient中,然后更新recipient page的下一个page,再更新recipient size,自己的size设置为0

然后是internal page中的MoveAllTo,这个比较麻烦

对于internal page的move all需要先拿到parent page然后将这个node在parent中的index所对应的key,需要下移到对应的结点的index 0处就是invalid处,值下放后再将node移动到recipient处,注意因为是internal page,所以需要更新node的children中的parent id,注意每一个都要unpin一下。

然后我们来看leaf page中的MoveFirstToEndOf和MoveLastToFrontOf两个函数,都比较类似,这里直接贴下代码,主要就是element迁移

然后是internal page中的两个move,但是会多了更新Childers's parent id,不贴代码了。

最后需要修几个前面的bug,一个是buffer_pool_manager中flush的最后应该是return true,还有DeletePage中需要记得更新p的page id为INVALID_PAGE_ID

还有在index_iterator在unpin leaf page时应该不管什么情况都要unpin

最后一些check函数和test到写完再分析,太菜了写不动

总结

B+树写的难度我是不会写了,只能看了,先读懂实现吧,等最后一致性完成后再做总的分析。