SimpleDB-Lab5
0.实验目标
在这个实验中，你将实现一个B+树形索引，用于高效的查找和范围扫描。我们为你提供了实现树形结构所需的所有底层代码。你将实现搜索、拆分页面、在页面之间重新分配 tuple 以及合并页面。
B+树的内部节点拥有多条记录，每个节点的内容包括节点当前值、以及左右子树的指针；相邻键之间共享一个孩子指针，所以拥有m个键的内部节点通常拥有m+1个孩子指针。叶子节点可以包括数据记录或者指向其他数据库文件的指针。为了简单起见，我们实现的B+树的叶子节点只包括数据记录。相邻的叶子页通过左右同级指针链接在一起，因此范围扫描只需要通过根节点和内部节点进行一次初始搜索即可找到第一个叶子页，后续叶子页通过右(或者左)指针找到。
- B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
- B+树相邻的叶子节点之间是通过链表指针连起来的
- B+树中，内部节点与其父节点的key值不能重复，叶子节点与其父节点的key值可以重复
下面这幅图是SimpleDB B+ tree这部分整体架构组织图（来源：MIT 6.830数据库系统）
磁盘上Header Page是懒初始化的，因此出现的位置是不固定的，Internal Page和Leaf Page同样如此，之所以可以这样，是因为存在一个root ptr page,它起到的作用就类似文件系统中的超级块:
我们应该在lab4的基础上开始本次实验代码的编写，此外，报告中还为本次实验提供了额外的源码和测试文件
搜索
B+树的单值查询
- 当查询key=70的节点时，首先从读取根节点，判断得key<75；
- 然后读取根节点的左孩子节点，将70依次与左孩子节点中的值进行比较，判断得key>66；
- 则读取66的右孩子节点，key存储于该叶节点中，读取其中的数据。
B+树的范围查询
- 当要读取[68,100]范围内的数据时，首先找到第一个大于等于68的节点，然后在叶节点中向后遍历。
查看index目录下的BTreeFile.java文件，这是实现B+树的核心文件，你将会在该文件为本次实验编写所有代码。不像HeapFile，BTreeFile包含四种不同的页。正如你期望的那样，树的结点有两种不同类型的页面：叶子节点和非叶子节点。
非叶子节点在BTreeInternalPage.java中实现，叶子节点在BTreeLeafPage.java中实现。为了方便起见，BTreePage.java中已经创建了包含叶子节点和非叶子结点共同特性的抽象类。此外，header pages在BTreeHeaderPage.java中实现并且追踪文件中的哪个页面是被使用的。
最后，在每个BTreeFile开始都有一个指向树的根页和第一个header page的页；该单独的页在BTreeRootPtrPage.java中被实现。熟悉这些类的接口，尤其是BTreePage、BTreeInternalPage和BTreeLeafPage。在实现B+树的过程中需要使用它们。
1. BTreeFile.findLeafPage()
a. 要修改的文件
- src/simpledb/index/BTreeFile.java
b. 实现说明
我们的第一个任务就是实现BTreeFile.java中的findLeafPage()函数，该函数通过给定的键查找合适的叶子页，主要用于搜索和插入。例如，假设我们提供了包含两个叶子页的B+树(如图1所示)，根节点是一个包含一个键和两个孩子结点指针的内部结点。给定键值1，该函数应该返回第一个叶子结点；同样地，给定键值8，该函数应该返回第二个结点。不太明显的情况是，我们给定键值6，可能存在重复的键，因此两个页结点上可能都包含键6对应的元组。在这种情况下，函数应该返回第一个叶子节点。
我们实现的findLeafPage()函数应该递归的搜索内部节点，直到它到达给定键值对应的叶子页。为了在每阶段找到合适的叶子页，我们应该迭代遍历内部节点的记录斌给比较记录与给定的键值的大小，以确定下一步往哪个方向走。BTreeInternalPage.iterator（）使用在BTreeEntry.java中定义的接口提供对内部页面中条目的访问。该迭代器允许我们遍历内部节点的键值，并且访问每个键的左右孩子页指针。当传入的BTreePageId的pgcateg()方法返回值与BTreePageId.LEAF相等时，表明这是一个叶子页。在这种情况下，我们仅需要从缓冲池中获取该页并返回它即可，不需要确保它实际上包含提供的键值f。
当提供的键值是null时，findLeafPage()方法必须处理这种情况。如果给定的值是空的，那么在递归的过程中就遍历最左侧的孩子节点，最终返回最左侧的叶子页。查找最左侧的叶子也对于扫描记录文件非常有用。当查找到正确的叶子页时，我们应该返回它。正如上面提到的那样，我们可以通过pgcateg()方法检查叶子也的类型。我们可以假设只有叶子页和内部节点才会被传递给该函数。
与其直接调用BufferPool.getPage()方法来获取每个内部页面和叶子页，建议调用代码中的包装函数BTreeFile.getPage()。它像BufferPool.getPage()那样工作，但是提供额外的参数去追踪脏页。在接下来的两个练习中，该函数非常重要，在这两个练习中，我们需要实际更新数据，因此需要追踪脏页。
findLeafPage()实现访问的每个内部（非叶）页面都应使用只读权限获取，但返回的叶页面除外，返回的叶页面应使用作为函数参数提供的权限获取。这些权限级别对于本实验室来说并不重要，但对于代码在未来的实验室中正常运行来说，它们将非常重要。
c. 实现目标
- 通过BTreeFileReadTest.java中的所有单元测试
- 通过BTreeScanTest.java中的系统测试。
d. 实现记录
- 查找值为field的元组所在的叶子Page：findLeafPage()
- 若为叶子Page则直接返回。若field为空，则查找最左的叶子Page。递归查找，非叶子Page访问均加读锁，叶子Page访问加写锁。
2. Splitting Pages
a. 要修改的文件
- src/simpledb/index/BTreeFile.java
b. 实现说明
为了保证B+树中存储元组的顺序性并且保持B+树的完整性，我们必须将元组插入到包含键范围的叶子页中。正如我们上面提到的，findLeafPage()方法被用于寻找我们应该插入元组的正确的叶子页。但是，每个页都有槽数的限制，即使对应的叶子页已满我们也需要能向其中插入元组。
尝试向已满的叶子页插入元组会导致页分裂，以便元组平均地分布到两个新页中。叶子页的每次分裂，都需要将第二页中的第一个元组对应的新条目添加到父节点。有时，内部节点也可能已满，无法接受新条目。在这种情况下，父节点应该分裂并且向它的父节点添加一个新纪录。这可能导致递归地分裂并且最终创建一个新的根节点
在本次练习中，我们需要实现BTreeFile.java中的splitLeafPage()和splitInternalPage()方法。如果被分裂的页是根节点，我们需要创建一个新的内部节点作为新的根节点，并且更新BTreeRootPtrPage。否则，我们需要通过READ_WRITE权限读取父页面，如果有必要就递归地进行分裂，并且添加新记录。你会发现getParentWithEmptySlots()函数对于处理这些不同的情况非常有用。在splitLeafPage()方法中我们应该将键复制到父页，而在splitInternalPage()方法中，应该将键推到父页(如图2所示)。记住根据需要更新新页的父指针(为了简单起见，图2没有展示父指针)。
分裂叶节点时，节点中的key值复制到父节点中（即叶节点和内部节点可以有相同的值）
当一个内部节点被分裂时，我们需要更新被移动的孩子页的父指针。你会发现updateParentPointers()对于这非常有用。此外，记住更新被分裂的叶子页的兄弟指针。最后，返回应该插入新元组或记录的页面，如提供的键字段所示。(提示：不必担心提供的键实际上可能位于要拆分的元组/条目的正中心。应该在拆分期间忽略该键，只使用它来确定返回两个页面中的哪一个)
分裂内部节点时，是将节点中的key值“挤到”父节点中（即内部节点之间的key值不能重复）
无论何时创建新页面，无论是因为拆分页面还是创建新的根页面，都可以调用getEmptyPage()来或取新页面。这个函数是一个抽象函数，它允许我们重用由于合并而被删除的页面。
我们期望使用BtreeAppPage.iterator()和BTreeInternalPage.iterator()与叶和内部页面交互，以迭代每个页面中的元组/条目。为了方便起见，源码中提供了这两种类型页面的反向迭代器：
- BTreeLeafPage.reverseIterator() 和 BTreeInternalPage.reverseIterator()。
- 对于将页中元组/条目的子集移动到其右侧兄弟节点的任务来说，这些反向迭代器非常有用。
如上所述，内部页面迭代器使用BTreeEntry.java中定义的接口，该接口有一个键和两个孩子指针。它也包含一个recordId，用于标识基础页面上键和孩子指针的位置。我们认为一次处理一个条目是与内部页面交互的自然方式，但重要的是要记住，底层页面实际上并不存储条目列表，而是存储m键和m+1子指针的有序列表。由于
BTreeEntry只是一个接口，而不是实际存储在页面上的对象，因此更新BTreeEntry的字段不会修改底层页面。为了修改页面上的数据，需要调用BTreeInternalPage.updateEntry()方法。另外，删除一个记录实际上仅仅删除了键和孩子指针，因此源码提供了BTreeInternalPage.deleteKeyAndLeftChild()和BTreeInternalPage.deleteKeyAndRightChild()函数来实现这一点。记录的recordId用于查找被删除的键和孩子指针。插入记录也仅仅插入键和孩子指针(除非它是第一条记录)，所以BTreeInternalPage.insertEntry()检查所提供的记录中的一个孩子指针是否与页面上现有的孩子指针重叠，并且在该位置插入条目将使键保持排序顺序在splitLeafPage()和splitINternalPage()方法中，需要使用任何新创建的页面以及由于新指针或新数据而修改的页面来更新
dirtypages集合。这是BTreeFile.getPage()派上用场的地方，每次获取页面时，BTreeFile.getPage()都会检查页面是否已经存储在本地缓存中，如果本地缓存中找不到请求的页面，则会从缓冲池中获取该页面。BTreeFile.getPage()如果使用读写权限获取页面，也会将页面添加到dirtypages缓存中，因为它们可能很快就会被弄脏。这种方法的一个优点是，如果在一个元组插入或删除过程中多次访问相同的页面，则可以防止更新丢失。请注意，与
HeapFile.insertTuple()不同的是，BTreeFile.insertTuple()可能会返回大量脏页，特别是在拆分任何内部页的情况下。您可能还记得以前的实验，返回脏页集是为了防止缓冲池在刷新脏页之前逐出脏页
Warning:B+树是一种复杂的数据结构，在修改B+树之前了解每个合法的B+树的必要属性很有帮助：
- 如果一个父节点指向孩子节点，那么孩子节点必须指向同一个父节点
- 如果叶子节点指向右侧兄弟节点，那么右侧兄弟节点也需要指向左边这个兄弟节点
- 第一个叶子和最后一个叶子节点必须分别指向null
- 记录ID必须与它们实际属于的页匹配
- 具有非叶子节点的节点中
key必须大于左子节点中的任何key，小于右子节点中的任何key - 具有叶子节点的节点中
key必须大于等于左孩子的所有key，小于等于右孩子的所有key - 节点孩子或为非叶子节点、或为叶子节点
- 每个节点最多只有m个子节点，非叶子节点具有至少⌈m/2⌉子节点
在BTreeChecker.java中已经实现了检查上述属性的机制，该方法也用于在 systemtest/BTreeFileDeleteTest.java中测试我们的B+树实现，可以随意添加对该函数的调用，以帮助调试
注意
- checker方法应始终在树初始化之后、开始和完成对键插入或删除的完整调用之前和之后通过，但不一定在内部方法中通过。
- 树可能格式正确(因此通过checkRep())，但仍然可能不正确。例如，空树始终会通过checkRep()方法，但可能并不总是正确的(如果刚刚插入元组,则树不应该为空)
c. 实现目标
- 通过BTreeFileInsertTest.java中的单元测试。
- 通过 systemtest/BTreeFileInsertTest.java 中的系统测试。
- 系统测试可能要花费几秒钟才能完成，这些文件会测试我们代码中插入元组和分裂也的正确性，并且处理重复的元组。
d. 实现记录
- 分裂Page：splitLeafPage()和splitInternalPage()
- 为了保证增加节点后，B+树的高度不会太高，当Page中节点超过阈值时需要将Page中的元组分裂到一个新的Page中。方法返回加入的filed所在的Page。
- 使用倒序遍历，将原本Page中右边一半的元组加入到新的Page中。叶子Page需要更新左右兄弟指针，并向父Page插入新Page中的第一个元组；非叶子Page需要将分裂后左边Page的最后一个元组挤入父Page。之后更新脏页中的孩子指针，并记录脏页。
3. Redistributing pages
a. 要修改的文件
- src/simpledb/index/BTreeFile.java
b. 实现说明
为了保持树的平衡并且不浪费不必要的空间，B+树的删除操作可能会导致页重新分配元组，最终导致页合并:
如果试图从小于半满的叶子页中删除元组的话，则会导致该页面从其兄弟节点中窃取元组或与其兄弟节点中的一个合并。如果页面的兄弟节点有多余的元组，则元组应该均匀分布在两个页面之间，并且父级条目应该进行更新(如图3)。但是，如果兄弟节点也是半满(如图4)，那么应该合并两个页，并且删除父节点的记录。反过来，从父节点中删除记录也可能导致父节点半满，在这种情况下，父节点应该从它的兄弟节点中窃取记录或者与他的兄弟节点合并。这可能会导致递归地合并，如果根节点的最后一个记录被删除的话，那么最终会删除根节点。
在接下来的练习中我们需要实现
BTreeFile.java中stealFromLeafPage(),stealFromLeftInternalPage(),stealFromRightInternalPage(),mergeLeafPages()和mergeInternalPages()方法。在前三个函数中，如果兄弟节点有多余的元组/记录，那么我们需要实现均匀地再分布元组/记录。记住更新父节点中相应的key(仔细看图3).在stealFromLeftInternalPage()/stealFromRightInternalPage()方法中，我们需要更新已经被移动的孩子的父节点。我们可以重用updateParentPointers()方法。
c. 实现目标
- 通过BTreeFileDeleteTest.java中的一些单元测试（如testStealFromLeftLeafPage和testStealFromRightLeafPage）。
d. 实现记录
使兄弟Page的元组数均分：stealFromLeafPage()和stealFromLeftInternalPage()和stealFromRightInternalPage()
是为了删除节点后，若当前节点不满足Page中最小元组数，则需要看兄弟是否有多余的，如果有，可以直接向兄弟节点借；若没有，则需要合并结点。
从兄弟节点中借siblingNumTuples - (pageNumTuples + siblingNumTuples) / 2个元组。若向左兄弟借，则对左兄弟进行倒序遍历；右兄弟则进行正向遍历。最后需要更新entry中的key值，并调用parent.updateEntry()、updateParentPointers()更新。
void stealFromLaefPage()
计算要steal的元组数（使其和兄弟Page中最终的元组数一致）
左兄弟从最后开始遍历，右兄弟从最左开始遍历
不断从兄弟Page中取出元组，插入到本Page
更新entry中的key值为较右Page中的第一个元组
调用parent.updateEntry(entry)更新parent信息
BTreeEntry中有一个Field类型的key和两个BTreePageId类型的child，以及一个RecordId类型的rid，可以看做B+树中非叶子节点的一个单元，每个单元保存key值并且指向两个孩子节点。BTreeEntry为InternalPageIterator遍历的单位，实际Page中没有保存这样一个结构。BTreeInternalPage中保存的是keys和children。
updateEntry()是通过传入的BTreeEntry来更新本Page中的keys和children信息。
stealFromLaefPage()中传入的参数entry代表的是兄弟节点和本节点所对应的父节点的entry，也就是其key为父节点中的key，两个child分别指向兄弟和自己。因此，steal完成后，对entry进行更新，指针和对应的rid（即PageId和该entry在该Page的位置）都不需要改变，只需要更新key。
void stealFromLeftInternalPage()
计算要steal的元组数（使其和兄弟Page中最终的元组数一致）
左兄弟从最后开始遍历
先将父Page中的entry插入本Page，更新孩子节点指针
不断从兄弟Page中取出元组，插入到本Page
之后更新父Page的entry，将左Page中的最后一个元组的key给父entry，调用parent.updateEntry(entry)更新parent信息
最后调用updateParentPointers，更新本Page中所有entry的父节点信息，保证子节点的parent都指向本Page。
void stealFromRightInternalPage()
- 基本与上相同，右兄弟从头开始遍历
4. Merging pages
a. 要修改的文件
- src/simpledb/index/BTreeFile.java
b. 实现说明
在
mergeLeafPages()和mergeInternalPages()方法中，我们需要编写合并页的代码，有效地执行splitLeafPage()和splitInternalPage()相反操作。deleteParentEntry方法在处理不同的递归情况时非常有用。确保在删除页时调用setEmptyPage()方法以使它们可以被重用。与前面的练习相似，这推荐使用BTreeFile.getPage()方法获取页面并使脏页列表保持最新。实现BTreeFile.mergeLeafPages()和BTreeFile.mergeInternalPages()。
c. 实现目标
通过BTreeFileDeleteTest.java中的所有单元测试。
通过systemtest/BTreeFileDeleteTest.java中的系统测试。
d. 实现记录
合并两个Page：mergeLeafPages()和mergeInternalPages()
- 将左Page中的元组全部加入到右Page，修改左右Page的兄弟指针，最后调用setEmptyPage()将右Page置空，并删除parentEntry。
void mergeLeafPages()
将rightPage中的所有元组插入到leftPage中
修改leftPage和rightPage右边的Page的兄弟指针
调用setEmptyPage()将rightPage置空
调用deleteParentEntry()删除父entry
void mergeInternalPages()
先将父entry插入到leftPage
再将rightPage中的所有元组插入到leftPage中
调用setEmptyPage()将rightPage置空
调用deleteParentEntry()删除父entry
最后调用updateParentPointers，更新leftPage中所有entry的父节点信息
5. 事务
- 通过next-key lock，B+树可以防止在两次连续范围扫描之间出现幻读的问题。由于SimpleDB使用页面级、严格的两阶段锁定，因此如果B+树实现正确的话，那就可以有效地防止幻读发生。因此，我们的B+树实现代码应该通过
BTreeNextKeyLockingTest测试. - 此外，如果我们在B+树代码中正确地实现锁，那么我们的代码也应该通过单元测试
test/simpledb/BTreeDeadlockTest.java - 如果所有练习都正确地实现，那么我们应该能够通过BTreeTest系统测试。通过该测试可能需要几分钟的时间。
6. Bonus Exercise
- 创建并实现一个名为BTreeReverseScan的类，该类在给定一个可选的IndexPredicate后，反向扫描BTreeFile。
- 你可以使用BTreeScan作为起点，但你可能需要在BTreeFile中实现一个反向迭代器。你也可能需要实现一个单独的BTreeFile.findLeafPage()版本。我们已经在BTreeLeafPage和BTreeInternalPage上提供了反向迭代器，你可能会发现它很有用。你还应该编写代码来测试你的实现是否正常工作。BTreeScanTest.java是一个寻找思路的好地方。
小结
BTreePage中有4种Page，分别为BTreeRootPtrPage、BTreeHeaderPage、BTreeLeafPage和BTreeInternalPage。其中，BTreeLeafPage为叶子节点，BTreeInternalPage为非叶子结点。
一个表中一个Field对应一个B+树，BTreeRootPtrPage中的root指向根节点。BTreeRootPtrPage只保存9个字节的信息，共3个属性：root为根节点对应的page number，rootCategory为根节点的类型（中间节点或叶子节点），header为BTreeHeaderPage对应的page number。
getParentWithEmptySlots中，若parentId.pgcateg()为ROOT_PTR，说明是根节点需要访问其父节点，也就是parentId无法直接获取到对应的Page，因此需要新建一个空节点，作为根节点的父节点，再返回这个新的节点。
BTreeHeaderPage为Header，多个Header组成一个Header链表，通过prevPage和prevPage可以获取到下一个HeaderPage。BTreeRootPtrPage中的header指向第一个HeaderPage的page number。Header除了指向上一个和下一个HeaderPage的指针外，其余空间全部用于位图，与HeapPage相同，每一bit都指明该tuple是否为空。
位图中tuple的顺序是物理存储的顺序，但是不是查找时的逻辑顺序。
原本BufferPool、TableStats等文件中，会将Page强转为HeapPage（或DbFile强转为HeapFile），在使用B+树存储时不适用。因此取消强转，需要时直接调用B+树的相关方法。
测试结果：
SimpleDB-Lab5