前言

Project2的第一部分,主要是实现B+树的主体结构部分,还有搜索和插入两个功能。

正文

Part1 B+TREE PAGES

page头文件

实现是实现B+树的叶结构,这里我们设计一个父类BPlusTreePage,然后两个子类BPlusTreeLeafPage和BPlusTreeInternalPage,一个表示叶子page,一个表示中间page。

先看下父类的结构

其中的成员变量看下,作为头部信息

Variable NameSizeDescription
pagetype4Page Type (internal or leaf)
lsn_4Log sequence number (Used in Project 4)
size_4Number of Key & Value pairs in page
maxsize4Max number of Key & Value pairs in page
parent_pageid4Parent Page Id
pageid4Self Page Id

然后看下leaf page,看下多了的两个成员变量

对于叶子结点的组织方式除了上层节点的指针,还有一个链表结构(next_page_id_)将叶子结点组织起来,然后对于每一个叶子结点其存储数组的结构是key/value,key是索引(唯一的),value是关联到slot id的,然后我们来看下具体的叶子结点,假如其max_size_为4,实际上它是可以存储5个值但是最后一位会留给溢出的元素,来方便之后的处理,类似0 1 2 3 4,这五个索引,前四个都是有效的,下标为4的索引只有插入的值溢出时才会把其放在末尾。

然后是internal page,他只有

然后提前定义了个宏给后面用

然后我们来看下internal page的结构是什么样的,同样是max_size_为4,实际容量为5,保留一位溢出位,但是n个有效位需要n+1个指针来指向子结点,所以我们需要将第一位也保留,作为左指针,即类似0 1 2 3 4,从索引1到3才是有效的,索引0对应的值是左指针,1对应的是右边指针,只有三位是有效的索引位,所以其实真正的maxsize是3。

b_plus_tree_page.cpp

然后我们来具体实现一下里面的一些基础函数。先从b_plus_tree_page.cpp,里面唯一一个需要注意的函数是

对于只有一个结点的树,如果该结点的size小于1即为0的时候需要调整header page,然后他是根结点并且不止一个结点的话,那么应该返回2,即一个左指针一个右指针,否则就返回(GetMaxSize() + 1) / 2,小于min的结点需要merge。

b_plus_tree_internal_page.cpp

然后看b_plus_tree_internal_page.cpp来实现internal page中的基础函数。先是Init函数

主要看下SetMaxSize这里是怎么实现的,PAGE_SIZE是512byte是一个页面的大小,首先需要减去header头信息即sizeof(BPlusTreeInternalPage),然后除以一个key/value对的大小,得到是整个的大小,然后-1是为了预留一个分裂时用的溢出位置。

然后是一些小的查找函数

然后是一个Lookup函数用来在page内部寻找对应的子结点指针,因为key是有序的所以可以用二分来找,注意返回的是array[l-1].second,某个index(没有0这个index)对应的value是右侧范围的值这里注意下,如果不懂可以画图看下

b_plus_tree_leaf_page.cpp

然后来看下leaf page的基础函数

同样是Init,SetMaxSize同样需要保留一位溢出位,这里sizeof的问题之后再研究

几个辅助函数

然后是一个KeyIndex函数根据key来找到第一个大于等于key的array[index].first,同样是利用二分来做,但是这里要注意下返回值,因为是>=所以应该返回的r+1,不懂的可以画图试试就知道了

然后是一个Lookup函数,这里我们直接调用上面的KeyIndex函数来寻找第一个大于等于的,然后比较key是否一样

Part2 B+TREE DATA STRUCTURE (INSERTION & POINT SEARCH)

Find

b_plus_tree_page.cpp

要实现搜索和插入的功能,那么我们先实现搜索的功能,先在b_plus_tree.h头文件中添加一个FetchPage函数用来从buffer pool中获取page

BPlusTreePage *FetchPage(page_id_t page_id);

然后同样是先完善一下基础的函数

然后看GetValue函数,FindLeafPage函数找到理论上key应该存在的leaf page,如果找到了,再用Lookup函数看是否能取出value到result中,最后记得要unpin一下这个leaf page.

然后跟进完成一下FindLeafPage函数,FindLeafPage的逻辑是先判断不为空树,然后利用FetchPage从buffer pool中根据root_page_id_来获取到根page,然后开始遍历直到到达leaf page,这里又个leftMost是在实现iterator时候会用到,这里先不详细说,这里我们FetchPage获取到的指针式BPlusTreePage格式的,我们需要用static_cast来进行一个良性转换为B_PLUS_TREE_INTERNAL_PAGE(因为是子类所以是良性的),然后用Lookup函数来找到相应key存在的指向子page的指针,这样循环直到leaf page,最后返回指向这个leaf page的指针。(这里的查找最底层都是利用二分的)

看下我们自己定义的FetchPage函数,从buffer pool中根据page_id来拿到对应的page

Insert

b_plus_tree_page.cpp

Insert这一块比较复杂,因为涉及到分裂的情况,先看Insert()函数

当是一个空树时,新建一个树StartNewTree,否则调用InsertIntoLeaf插入到leaf page中,我们先看StartNewTree

先从buffer pool中new一个Page出来,存储id在newRootPageId中,然后我们要将Page struct转换为B_PLUS_TREE_LEAF_PAGE_TYPE 类型,需要使用reinterpret_cast进行不安全的转换,然后需要初始化一些信息,Init(),更新root_page_id,UpdateRootPageId更新root page id到header page中,然后将key/value插入(在b_plus_tree_leaf_page.cp中实现)到root这个page中,最后unpin这个page。

然后我们看下InsertIntoLeaf这个函数

首先我们应该FindLeafPage中找到相应key应该在的leaf page,然后判断是否已经存在key了,如果存在直接返回false,并且unpin这个leaf page,否则就Insert到这个leaf page中,然后我们需要判断这个page是否溢出了,如果溢出了,我们需要调用Split函数来分裂出一个新的page,并将值分配好,然后调用InsertIntoParent函数将new leaf page插入到parent page中的相应的位置,最后同样记得unpin原来的leaf page(new leaf page我们在别的地方unpin)。

然后我们逐一看下其中的函数,先看Split函数,他用来分裂出新的page,他的逻辑是从buffer pool中new一个Page然后转换后初始化Init,然后调用MoveHalfTo函数将old node中一半的element转移,最后返回new node,(MoveHalfTo放在后面说)

然后看下InsertIntoParent,这个函数是将new node记录到parent node相应的位置

这个函数比较复杂,需要考虑几种情况,首先是当old node是根结点,此时没有parent node,那么我们就需要从buffer pool中new一个新的page,经过初始化后,调用PopulateNewRoot函数来计算new root中的key/value(在internal page cpp中实现),将old node和new node的parent node id设置为新的root,然后更新UpdateRootPageId,最后unpin一下新的root node和new node。另一个情况是存在parent node这种情况,我们FetchPage拿到这个parent node的指针转换后,将new node的parent node id设置为它,然后unpin new node,对于这个parent node需要调用InsertNodeAfter,将new node插到old node后面,然后判断parent node是否有溢出,如果溢出继续分裂parent node,这种情况是递归得,最后记得unpin这个parent node。

之后我们再看下b_plus_tree_internal_page.cpp和b_plus_tree_leaf_page.cpp中要实现的Insert的部分。

b_plus_tree_internal_page.cpp

首先看下b_plus_tree_internal_page.cpp的PopulateNewRoot,这个主要更新root结点的左右两个指针

来看下InsertNodeAfter这个函数,ValueIndex来获取old node的key的位置,+1位new node的位置,IncreaseSize这个node的大小,然后顺位后移idx后面的index,然后将new node对应的key/value放入,这里没有判断是否溢出,是在InsertIntoParent中进行检查的溢出。

然后是MoveHalfTo函数,用来切半,注意要更改childrens' parent id,其他的具体看注释

b_plus_tree_leaf_page.cpp

看下insert函数,找到第一个大于等于的idx,然后后移,然后插入

同样leaf也需要实现MoveHalfTo函数

Iterator

对于我们需要实现Itreator

index_iterator.h

一个构造函数,然后isEnd(),然后重载*,表示取key/value。重载++,首先index_增加,然后如果溢出,判断是否有下一个leaf page,如果没有返回nullptr,如果存在那么unpin这个page,FecthPage下一个next page,然后index_重制为0

index_iterator.cpp

然后看下index_iterator.cpp文件中,主要是构造和析构函数

Fix bug

前面又一些bug需要修

buffer_pool_manager.cpp

原来是直接p->is_dirty = is_dirty是直接赋值,但是false不应该覆盖原来的true值,应该用或符号来刷新pin

lru_replacer.cpp

缺少析构函数原来,会导致内存泄漏

最后跑通了两个test

总结

今天先把find和insertion部分搞定,写完后再分析下测试用例和整个架构