【数据库】cmu15445-project2 B+Tree Checkpoint 1 实验总结-526互联

project-2相比project-1难度提升了不少。

project2的工作量较大，因此分成两个checkpoint。checkpoint2是支持并发安全，而checkpoint1其实是数据结构的问题，这篇文章先写project-1的checkpoint1。

实验前提

可以看project-2的实验文档。由于课件里没有B+ Tree的具体插入删除规则，因此需要找数据库系统概念找到对应的伪代码,最好看英文版的内容。整个project的checkpoint1就是在这个数据结构上折腾。

$D:\Gitlab\DB-Lab\cs15445-docs\image-20230606110216758.png$

checkpoint1需要实现tree如下接口：Remove Insert GetValue

迭代器接口：Begin End operator++

整个project的任务（22fall的任务标题有误导，主要不是实现数据结构，而是实现增加和删除）

Task #2a - B+Tree Insertions

Task #2b - B+Tree Deletions

Task #2c – Index Iterator

Task #2d – Concurrency Control

对应的leaf节点和internal节点类的实现按照需要添加各自的接口

代码确实比较长，所以在实现之前最好先搞清楚数据存储的结构。具体来说，叶子节点跟内部节点存在最大，最小值的区别，而内部节点的v都是page_id，叶子节点的v是多样的。

内部节点因为孩子数=kv对数+1，所以用数组保存的时候，index=0的位置的key是无效的。

叶子节点的结构：

+----------+------+----------+------+-----+-------------+----------+----------+

+----------+------+----------+------+-----+-------------+----------+----------+

内部节点的结构：

第i个节点指向的子树中的任意K，满足K(i) <= K < K(i+1)，这里n=size-1，KEY(0)无效

+----------+------+----------+------+-----+-------------+----------+----------+

+----------+------+----------+------+-----+-------------+----------+----------+

数量关系遵循如下约定：

internal的size=key数+1=指针数；

leaf的size=key数=value数；

节点类型与size大小	叶子节点	内部节点
最小值	作为根节点=1；非根节点=floor(max_size/2)	作为根节点=2，非根节点=floor((max_size+ 1) / 2)
最大值	leaf_max_size	internal_max_size
key数	size	size – 1
插入的分裂条件	插入后size>=leaf_max_size	插入后size>internal_max_size
删除的合并条件	删除后与另一节点的size之和∈[min_size, max_size)	插入后与兄弟节点的size之和∈[min_size, max_size]
删除的重新分布条件（拆借）	删除后与另一节点的size之和>=max_size	插入后与兄弟节点的size之和>max_size