MIT6.830 Lab 5: B+ Tree Index
6.830 Lab 5: B Tree Index
lab5主要是实现B 树索引,主要有查询、插入、删除等功能,查询主要根据B 树的特性去递归查找即可,插入要考虑节点的分裂(节点tuples满的时候),删除要考虑节点内元素的重新分配(当一个页面比较空,相邻页面比较满的时候),兄弟节点的合并(当相邻两个页面的元素都比较空的时候)
B 树的页面节点类型主要有四种:
1.根节点页面:一个B 树的根节点,在SimpleDB中实现为BTreeRootPtrPage.java;
2.内部节点页面:除去根节点和叶子节点外的节点,在SimpleDB中实现为BTreeInternalPage,每个BTreeInternalPage由一个一个的entry组成;
3.叶子节点页面:存储tuple的叶子节点,在SimpleDB中实现为BTreeLeafPage;
4.头部节点页面:用于记录整个B 树中的一个页面的使用情况,在SimpleDB中实现为BTreeHeaderPage。
**Exercise 1: **Search
B 树索引查找的过程:
-
创建运算符,因为该B 树只支持单列索引,运算符只有大于,小于,等于,大于等于,小于等于,不等于:
-
IndexPredicate ipred = new IndexPredicate(Op.GREATER_THAN, f);
-
调用BTreeFile的indexIterator方法获取查找结果,indexIterator方法是会创建BTreeSearchIterator迭代器:在需要获取查找结果时,会调用BTreeSearchIterator的open和getnext方法来获取查询的结果:
-
首先是open,开启迭代器。首先是getPage获取页面,这里会加锁,然后第一次调用会从BTreeFile.getPage()获取根节点,因为写入文件时根节点是按内部节点的类型去写的,然后每个根节点有9个entry,第一次遍历实际上是遍历了根节点的9个entry然后往下查找,当然这里只是找出了叶子节点页面并创建了迭代器,真正的查找在下一步。
-
然后是要获取结果时,调用迭代器的readNext,然后会根据运算符就获取结果,这里迭代的时候是对一个leaf page的所有元组进行迭代,然后筛选出满足运算符的结果,比如说是age > 18这个条件,会先找到最后一个小于18的entry,然后获取entry的左孩子得到leaf page,然后在leaf page中迭代找到age > 18的元组,如果该leaf page 遍历完了,会一直往右兄弟的方向找下一个页面的元组,因为多个leaf page之间就是双向链表。
Exercise 2: Insert
exercise2要做的是分裂叶子节点和分裂内部节点两个方法的实现
分裂叶子节点的思路:
-
新建一个leaf page,作为新的页面;
-
将满页面的元组复制到新页面,边复制边删除;
-
检查之前的满页面是否有右兄弟,有的话需要更新指针,这里有点像在双向链表中插入一个结点,一开始没有考虑到,后面测试用例过不了重新整理思路才发现要更新这个指针;
-
更新脏页;
-
更新兄弟指针;
-
找出父节点并创建entry进行插入,最后更新脏页;
-
根据field找出要插入的页面并返回;
分裂内部节点的思路:
-
新建一个internal page,作为新的页面;
-
将满页面的entry复制到新页面,边复制边删除;
-
将中间节点挤出去;这里与leaf page不同,要注意,其实看图示就能发现不同之处了;
-
更新脏页;
-
更新左右孩子指针;
-
更新左右叶面的孩子指针,因为前面有大量的entry插入和移除;
-
根据中间节点获取父节点,将midEntry插入到父节点中,并更新脏页和指针;
-
根据field找出要插入的页面并返回
Exercise 3: Delete
exercise3是页面元素的重新分配,internal page的entry,leaf page的tuple,两种页面的分配是有区别的,重新分配tuple的话parent是需要包含tuple的value的,而重新分配entry是不需要的,因为真正的数据是在leaf page中,这个只是作为一个索引,当然你加上也是没问题的,但是这样做是会更方便的,至少图示就是这样做的。
重新分配的话可以考虑两种策略:第一种是两个页面的元组总数加起来然后平均,第二种是一个页面留下总容量的1/2,剩下的都分配给比较空的页面,这里我采用的是前者;
Exercise 4: Merging pages
In
mergeLeafPages()
andmergeInternalPages()
you will implement code to merge pages, effectively performing the inverse ofsplitLeafPage()
andsplitInternalPage()
. You will find the functiondeleteParentEntry()
extremely useful for handling all the different recursive cases. Be sure to callsetEmptyPage()
on deleted pages to make them available for reuse. As with the previous exercises, we recommend usingBTreeFile.getPage()
to encapsulate the process of fetching pages and keeping the list of dirty pages up to date.
即实现两个页面的合并。
public void mergeLeafPages(TransactionId tid, Map<PageId, Page> dirtypages,
BTreeLeafPage leftPage, BTreeLeafPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry)
throws DbException, IOException, TransactionAbortedException {
Iterator<Tuple> it = rightPage.iterator();
while (it.hasNext()){
Tuple t = it.next();
rightPage.deleteTuple(t);
leftPage.insertTuple(t);
}
BTreePageId rid = rightPage.getRightSiblingId();
if(rid != null){
BTreeLeafPage rr = (BTreeLeafPage)getPage(tid, dirtypages, rid, Permissions.READ_WRITE);
rr.setLeftSiblingId(leftPage.pid);
leftPage.setRightSiblingId(rid);
}
else {
leftPage.setRightSiblingId(null);
}
setEmptyPage(tid, dirtypages, rightPage.pid.getPageNumber());
deleteParentEntry(tid, dirtypages, leftPage, parent, parentEntry);
}
public void mergeInternalPages(TransactionId tid, Map<PageId, Page> dirtypages,
BTreeInternalPage leftPage, BTreeInternalPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry)
throws DbException, IOException, TransactionAbortedException {
BTreeEntry lastLeftEntry = leftPage.reverseIterator().next();
BTreeEntry firstRightEntry = rightPage.iterator().next();
BTreeEntry entry = new BTreeEntry(parentEntry.getKey(), lastLeftEntry.getRightChild(), firstRightEntry.getLeftChild());
leftPage.insertEntry(entry);
Iterator<BTreeEntry> it = rightPage.iterator();
while (it.hasNext()) {
BTreeEntry e = it.next();
rightPage.deleteKeyAndLeftChild(e);
leftPage.insertEntry(e);
}
updateParentPointers(tid, dirtypages, leftPage);
setEmptyPage(tid, dirtypages, rightPage.pid.getPageNumber());
deleteParentEntry(tid, dirtypages, leftPage, parent, parentEntry);
}
实验总结
lab5是用b 树实现数据库的索引,还是比较简单的。
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgggeeh
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13