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() and mergeInternalPages() you will implement code to merge pages, effectively performing the inverse of splitLeafPage() and splitInternalPage(). You will find the function deleteParentEntry() extremely useful for handling all the different recursive cases. Be sure to call setEmptyPage() on deleted pages to make them available for reuse. As with the previous exercises, we recommend using BTreeFile.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 树实现数据库的索引，还是比较简单的。

这篇好文章是转载于：学新通技术网