CMU15445 2022fall project2

CheckPoint 1

这部分主要是给page、internal、leaf三个page类实现一些get、set方法和一些简单的函数。

注意点：

判断root page：parent page id = INVALID_PAGE_ID
GetMinSize()：叶子结点为max_size_ / 2，内部节点为(max_size_ + 1) / 2（为什么root没特判？因为root节点既可以是叶子节点，也可以是内部节点，所以我选择在后面实现时再根据情况判断）

这部分是b+树的单线程实现，只给了三个接口。可以先看书上的伪代码实现，修改一下就可以了。

利用好模拟插入删除的网站来debug可以减轻痛苦，降低b+树的噩梦程度。

注意点：

树为空，创建一个新页并更新root_page_id，然后把节点插入，记得调用一下UpdateRootPageId，返回true
树不空，遍历找到key应该插入的叶子节点
将kv插入叶子节点，如果插入后，叶子节点size没变，返回false，如果size < leaf_max_size，直接返回true
到这一步说明需要分裂叶子节点，叶子节点满额条件是size = leaf_max_size
- 分裂出一个新的节点，并将原节点中一半的元素插入这个新节点，记得设置好它的parent page id和next page id，还有原节点的next page id
- 将这个新节点插入到原节点的父节点中，并设置父节点中的对应key为新节点中的index为0的key
- 这个插入操作又有可能会导致父节点满，内部节点满的条件时要size > internal_max_size，向上递归即可

注意点：

split处理内部节点时，还是将一半的节点复制到新节点，但我们知道，内部节点的第一个节点应该为空key，所以此时我们把它当作没有key就行了，只需要它的value指向一个下层的page
还有一个点就是在插入到父节点时，如果原来的节点就是父节点的话，需要重新创建一个新页面，进行换根的操作

如果树空，直接返回
树不空时，查找需要删除的key所在的叶子节点
在所在叶子节点中删除target key，删除失败直接返回，删除成功时如果size >= leaf_min_size直接返回表示删除成功
如果删除后节点size不满足条件了，则需要对进行向左右节点借kv，或者合并入左右节点的操作（注意是先向左右借，不够借时才合并，借操作不会导致父节点的元素增减，只会导致元素变化，而合并操作可能会导致父节点size变小，进而向上递归借加合并）
借左右：向左借时，将左节点最后一个节点借过来放在自己的第0个，同时将父节点对应自己的key设置为这个新的借过来的key；

向右借时：将右节点的第0个节点借过来放在自己的最后一个，此时需要将父节点对于右节点的key设置为右节点中第1个位置的key；（这里可以发现前面所说的内部节点的第0个节点的空key其实在这里又可以视为存在的）
合并左右：无论合并左右，可以全部当作将右边节点的元素全部加入左边节点，这样如果是在合并叶子节点时，方便设置它的next page id，之后删除父节点中对于的key，如果此时发现父节点的size不满足条件，向上递归即可

注意点：

合并节点时的内部节点和叶子节点的两种情况如何设置key情况有点复杂，可以画图好好分析下，可以使用BusTub B+Tree Printer (skyzh.dev)这个网站的模拟插入来分析自己实现的对错
关于内部节点的0号节点的key存不存在这个问题，在我的实现中，其实绝大多数内部节点的0号节点都是有key的，如下图所示，只有最左侧的所有节点实际为空key，这个可能每个人的实现方法不一样。

这块比较简单，iterator中添加3个变量即可

BufferPoolManager *bpm_;
LeafPage *leaf_;
int index_;

贴几篇我在实现时参考的文章，大佬们已经讲的很好了。

注意点：

一定要确保实现的单线程b+树没有问题，checkpoint1在线测试也不够强大，我在实现通过后，在checkpoint2中仍然出现了问题，利用b_plus_tree_printer工具自己做测试或者自己写测试即可，最好测试插入很多数后，依次删除奇数的key，或依次删除偶数的key，看看自己的实现有没有问题。

标签：CMU15445,page,叶子,插入,key,2022fall,project2,节点,size
From： https://www.cnblogs.com/xulizs666/p/18081450