首页 > 其他分享 >MIT6.830-Lab5

MIT6.830-Lab5

时间：2024-03-02 14:57:08浏览次数：23  
标签：dirtypages parent 节点 next Lab5 tid MIT6.830 page

simpleDB项目地址

概览

类概述

  • BTreePage：B+树节点（叶子节点和内部节点）的公共父类，存储了父节点页号protected int parent，并且使用protected final int keyField存储在表记录的哪个字段建立索引。
  • BTreeLeafPage：B+树的叶子节点，用来存放具体的表记录。
  • BTreeInternalPage：B+树的内部节点，此外，private final Field[] keys存储了索引的字段，private final int[] children存储了孩子节点的页号，具体规则为keys[i]的左孩子对应children[i]，keys[i]的右孩子对应children[i+1]。（孩子节点可能是BTreeLeafPage或BTreeLeafPage）
  • BTreeEntry：对BTreeInternalPage内部记录的封装
  • BTreeHeaderPage：作用类似HeapPage中的header[]数组，每个正在使用的BTreePage都有一个对应的BTreeHeaderPage，这些BTreeHeaderPage组成链表，标记每一个页中记录的有效情况。
  • BTreeRootPtrPage：内部包含B+树根节点的页号以及BTreeHeaderPage链表中头节点的页号。

注意点

文件被转化为B+树后，树中的任何节点都是顺序存储在磁盘上的，在查找字段为某个值的记录时，不需要像HeapFile一样遍历每个页来搜索，而时通过读取文件头部存储的BTreeRootPtrPage找到根节点位置，再从根节点依次向下索引找到对应的叶子节点，最后从叶子节点页中遍历搜索即可，省下了大量时间。

实验部分

实验1

BTreeFile.findLeafPage()中Field f参数不为空时，该方法要求返回可能含有f的最左叶子节点，当Field f为空时，返回整个B+树的最左叶子节点，对索引过程中遍历到的内部节点，只请求读权限，对返回的叶子节点，请求Permissions perm参数指定的权限。使用BTreeFile.getPage()方法获取页，它是对BufferPool.getPage()的封装，使用了Map<PageId, Page> dirtypages记录了脏页（BufferPool中得页中数据修改完之后才能将其标记为脏页，dirtypages则是直接将请求写权限的页加入，相当于比BufferPool提前标记了脏页）

private BTreeLeafPage findLeafPage(TransactionId tid, Map<PageId, Page> dirtypages, BTreePageId pid, Permissions perm,
                                       Field f)
					throws DbException, TransactionAbortedException {
		if(f != null){
			if(pid.pgcateg() == BTreePageId.LEAF)
				return (BTreeLeafPage) getPage(tid,dirtypages,pid,perm);
			else {
				BTreeInternalPage page = (BTreeInternalPage) getPage(tid, dirtypages, pid, Permissions.READ_ONLY);
				Iterator<BTreeEntry> iterator = page.iterator();
				BTreeEntry next = null;
				while(iterator.hasNext()){
					next = iterator.next();
					if(f.compare(Op.LESS_THAN_OR_EQ,next.getKey()))
						return findLeafPage(tid,dirtypages,next.getLeftChild(),perm,f);
				}
				// 走到这说明f比该页所有的key都大，只能从最右边的rightChild再找
				return findLeafPage(tid,dirtypages,next.getRightChild(),perm,f);
			}
		}else {
			if(pid.pgcateg() == BTreePageId.LEAF)
				return (BTreeLeafPage) getPage(tid,dirtypages,pid,perm);
			else {
				BTreeInternalPage page = (BTreeInternalPage) getPage(tid, dirtypages, pid, Permissions.READ_ONLY);
				Iterator<BTreeEntry> iterator = page.iterator();
				BTreeEntry next = iterator.next();
				return findLeafPage(tid,dirtypages,next.getLeftChild(),perm,null);
			}
		}
	}

实验2

分裂叶子节点时，将新叶子节点的中存储的首条记录“拷贝”到父内部节点中(key6)：
image
分裂内部节点时，将新页的中存储的首条记录“移动”到父内部节点中（key6）：
image
叶子节点分裂实现步骤如下：

  1. 创建新的右叶子页面，将新建叶子节点的keyFiled更新为待分裂叶子节点的keyFiled
  2. 获取待分裂叶子节点的反向迭代器中，反向遍历其中一半的tuple插入新的右叶子页面中
  3. 根据待分裂的叶子节点是否有右兄弟，将新建叶子节点以合适的方式插入双向链表中
  4. 通过getParentWithEmptySlots（）递归获取可插入新记录的父节点
  5. 将右叶子节点的第一条记录封装成BTreeEntry对象插入父节点
  6. 更新左右叶子节点的父指针
public BTreeLeafPage splitLeafPage(TransactionId tid, Map<PageId, Page> dirtypages, BTreeLeafPage page, Field field)
			throws DbException, IOException, TransactionAbortedException {

		// 通过getPage方法读取的权限为Permissions.READ_WRITE的页都会加入dirtypages
		BTreeLeafPage page1 = (BTreeLeafPage)getPage(tid, dirtypages, page.getId(), Permissions.READ_WRITE);
		// 通过getEmptyPage创建的页会上X锁
		BTreeLeafPage page2 = (BTreeLeafPage)getEmptyPage(tid, dirtypages, BTreePageId.LEAF);
		try {
			// 设置page2的keyFiled
			java.lang.reflect.Field keyField = BTreePage.class.getDeclaredField("keyField");
			keyField.setAccessible(true);
			java.lang.reflect.Field modifiers = java.lang.reflect.Field.class.getDeclaredField("modifiers");
			modifiers.setAccessible(true);
			modifiers.setInt(keyField,keyField.getModifiers()&~Modifier.FINAL);
			keyField.setInt(page2,page1.keyField);
		} catch (Exception e) {
			throw new RuntimeException(e);
		}

		int page1NumTuples = page1.getNumTuples();
		int count = 0;
		Iterator<Tuple> reverseIterator = page1.reverseIterator();
		while(reverseIterator.hasNext()){
			Tuple next = reverseIterator.next();
			// BtreeLeafPage的insertTuple方法在插入tuple的时候，就会更新该tuple所属的页信息和序号，
			// 这就会导致page1调用deleteTuple的时候发现该tuple不属于本页，从而报错
			// page2.insertTuple(next);
			// page1.deleteTuple(next);
			page1.deleteTuple(next);
			page2.insertTuple(next);
			count++;
			if(count >= page1NumTuples/2)
				break;
		}
		// 插入兄弟指针
		if(page1.getRightSiblingId() != null){
			BTreeLeafPage page3 = (BTreeLeafPage)getPage(tid, dirtypages, page1.getRightSiblingId(), Permissions.READ_WRITE);
			page1.setRightSiblingId(page2.getId());
			page2.setLeftSiblingId(page1.getId());
			page3.setLeftSiblingId(page2.getId());
			page2.setRightSiblingId(page3.getId());
		}else {
			page1.setRightSiblingId(page2.getId());
			page2.setLeftSiblingId(page1.getId());
		}

		// 如果原来的parent页满了，getParentWithEmptySlots会调用splitInternalPage方法并返回一个新的parent页
		// 通过getParentWithEmptySlots获得的页已经上锁了
		BTreeInternalPage parent = getParentWithEmptySlots(tid, dirtypages, page1.getParentId(), field);
		Tuple first = page2.iterator().next();
		parent.insertEntry(new BTreeEntry(first.getField(page2.keyField),page1.getId(),page2.getId()));
		// 更新父指针
		updateParentPointer(tid,dirtypages,parent.getId(),page1.getId());
		updateParentPointer(tid,dirtypages,parent.getId(),page2.getId());
		// 返回合适的页
		if(field.compare(Op.LESS_THAN_OR_EQ,first.getField(page2.keyField))){
			return page1;
		}else {
			return page2;
		}
	}

注意，splitLeafPage()会根据传入的field参数返回插入的叶子节点，不会真正执行记录插入操作。
内部节点的分裂步骤类似叶子节点，从第4步开始不同：
4. 获取左内部节点最后的BTreeEntry记录，并从左内部节点删除该记录
5. 设置该记录的左右孩子分别为左右内部节点
6. 更新右内部节点中，所有子页的父节点为该右内部节点（这些子页的父节点一开始是左内部节点）
7. 通过getParentWithEmptySlots（）递归获取可插入新记录的父节点
8. 插入之前获取的左内部节点最后的BTreeEntry记录

public BTreeInternalPage splitInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
			BTreeInternalPage page, Field field) 
					throws DbException, IOException, TransactionAbortedException {
		// some code goes here
        //
        // Split the internal page by adding a new page on the right of the existing
		// page and moving half of the entries to the new page.  Push the middle key up
		// into the parent page, and recursively split the parent as needed to accommodate
		// the new entry.  getParentWithEmtpySlots() will be useful here.  Don't forget to update
		// the parent pointers of all the children moving to the new page.  updateParentPointers()
		// will be useful here.  Return the page into which an entry with the given key field
		// should be inserted.
		BTreeInternalPage page1 = (BTreeInternalPage)getPage(tid, dirtypages, page.getId(), Permissions.READ_WRITE);
		BTreeInternalPage page2 = (BTreeInternalPage)getEmptyPage(tid, dirtypages, BTreePageId.INTERNAL);

		try {
			java.lang.reflect.Field keyField = BTreePage.class.getDeclaredField("keyField");
			keyField.setAccessible(true);
			java.lang.reflect.Field modifiers = java.lang.reflect.Field.class.getDeclaredField("modifiers");
			modifiers.setAccessible(true);
			modifiers.setInt(keyField,keyField.getModifiers()&~Modifier.FINAL);
			keyField.setInt(page2,page1.keyField);
		} catch (Exception e) {
			throw new RuntimeException(e);
		}

		int page1NumEntries = page1.getNumEntries();
		Iterator<BTreeEntry> reverseIterator = page1.reverseIterator();
		int count = 0;
		while(reverseIterator.hasNext()){
			BTreeEntry next = reverseIterator.next();
			page1.deleteKeyAndRightChild(next);
			page2.insertEntry(next);
			count++;
			if(count >= page1NumEntries/2)
				break;
		}

		// 获取要提上parent的Entry
		BTreeEntry last =  page1.reverseIterator().next();
		page1.deleteKeyAndRightChild(last);
		last.setLeftChild(page1.getId());
		last.setRightChild(page2.getId());
		// 因为internal页分裂了，所以原先一半子节点被分到了新的internal页，要更新这些子节点页的父节点
		updateParentPointers(tid,dirtypages,page2);

		BTreeInternalPage parent = getParentWithEmptySlots(tid, dirtypages, page1.getParentId(), field);
		parent.insertEntry(last);
		// 因为parent页上有新加入的节点，所以也要更新该节点页的父节点
		updateParentPointers(tid,dirtypages,parent);

		BTreeEntry first = page2.iterator().next();
		if(field.compare(Op.LESS_THAN_OR_EQ,first.getKey())){
			return page1;
		}else {
			return page2;
		}
	}

实验3

删除记录时，可能会导致该记录所在的节点不满足B+树的要求，这时要分两种情况，一种是兄弟节点含有多余的记录，将多余记录分给该节点；二是兄弟节点没有多余的记录，要将该节点和兄弟节点合并。
实现第一种情况要完成stealFromLeafPage(),stealFromLeftInternalPage(), stealFromRightInternalPage()三个方法。
image
叶子节点分配记录的方法stealFromLeafPage()实现流程：

  1. 根据isRightSibling判断是左兄弟还是右兄弟含有多余的记录，如果是左兄弟含有多余记录，则获取左兄弟的反向迭代器遍历数据插入叶子节点page中，如果是右兄弟含有多余记录则获取右兄弟的正向迭代器遍历数据插入叶子节点page中
  2. 更新父节点中指向这两个叶子节点的entry，将其key值改为叶子节点page中第一条记录的key值。
public void stealFromLeafPage(BTreeLeafPage page, BTreeLeafPage sibling,
			BTreeInternalPage parent, BTreeEntry entry, boolean isRightSibling) throws DbException {
		// 注意，此时的page和sibling都是leaf，它们的父节点为parent不会变
		int half = (page.getNumTuples() + sibling.getNumTuples())/2;
		if(half < page.getMaxTuples()/2)
			throw new RuntimeException("the leaf page does not have enough tuples to steal");
		if(isRightSibling){
			// 把右兄弟的tuple移动到page中
			Iterator<Tuple> iterator = sibling.iterator();
			while(page.getNumTuples() < half){
				Tuple next = iterator.next();
				sibling.deleteTuple(next);
				page.insertTuple(next);
			}
			Tuple first = iterator.next();
			entry.setKey(first.getField(sibling.keyField));
			parent.updateEntry(entry);
		}else {
			// 把左兄弟的tuple移动到page中
			Iterator<Tuple> reverseIterator = sibling.reverseIterator();
			while(page.getNumTuples() < half){
				Tuple next = reverseIterator.next();
				sibling.deleteTuple(next);
				page.insertTuple(next);
			}
			Tuple first = page.iterator().next();
			entry.setKey(first.getField(page.keyField));
			parent.updateEntry(entry);
		}
	}

image
内部节点分配记录的方法stealFromLeftInternalPage()实现流程：

public void stealFromLeftInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
			BTreeInternalPage page, BTreeInternalPage leftSibling, BTreeInternalPage parent,
			BTreeEntry parentEntry) throws DbException, TransactionAbortedException {
		page = (BTreeInternalPage) getPage(tid,dirtypages,page.getId(),Permissions.READ_WRITE);
		leftSibling = (BTreeInternalPage) getPage(tid,dirtypages,leftSibling.getId(),Permissions.READ_WRITE);
		parent = (BTreeInternalPage) getPage(tid,dirtypages,parent.getId(),Permissions.READ_WRITE);

		int half = (page.getNumEntries() + leftSibling.getNumEntries())/2;
		if(half < page.getMaxEntries()/2)
			throw new RuntimeException("the internal page does not have enough entries to steal");
		// 注意，BTreeFile的insertEntry方法要求新加入的entry的左右孩子指针，必须有一个和已存在的孩子指针相同
		// 在插入entry时，新entry的key来自parent，左孩子为leftSibling对应位置entry的右孩子，右孩子为page第一个位置entry的左孩子
		Iterator<BTreeEntry> reverseIterator = leftSibling.reverseIterator();
		while(page.getNumEntries() < half){
			BTreeEntry next = reverseIterator.next();
			leftSibling.deleteKeyAndRightChild(next);
			BTreeEntry bTreeEntry = new BTreeEntry(parentEntry.getKey(),
													next.getRightChild(),
													page.iterator().next().getLeftChild());
			page.insertEntry(bTreeEntry);
			parentEntry.setKey(next.getKey());
		}
		// 虽然parentEntry更新了，但是parent节点内的信息未更新，要调用updateEntry方法
		parent.updateEntry(parentEntry);
		// 因为有entry从左兄弟移动到了右兄弟，要更新这部分entry的父指针
		updateParentPointers(tid,dirtypages,page);
	}

实验4

merge是split的逆过程，注意deleteParentEntry内部递归删除父节点中相应的entry记录
image

public void mergeLeafPages(TransactionId tid, Map<PageId, Page> dirtypages,
			BTreeLeafPage leftPage, BTreeLeafPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry) 
					throws DbException, IOException, TransactionAbortedException {
		// Move all the tuples from the right page to the left page, update
		// the sibling pointers, and make the right page available for reuse.
		// Delete the entry in the parent corresponding to the two pages that are merging -
		// deleteParentEntry() will be useful here
		leftPage = (BTreeLeafPage) getPage(tid,dirtypages,leftPage.getId(),Permissions.READ_WRITE);
		rightPage = (BTreeLeafPage) getPage(tid,dirtypages,rightPage.getId(),Permissions.READ_WRITE);
		parent = (BTreeInternalPage) getPage(tid,dirtypages,parent.getId(),Permissions.READ_WRITE);
		if(leftPage.getNumTuples() + rightPage.getNumTuples() > leftPage.getMaxTuples())
			throw new RuntimeException("the leaf page can not hold those tuples");
		// 从右leaf将tuple移动到左leaf
		Iterator<Tuple> iterator = rightPage.iterator();
		while(rightPage.getNumTuples() > 0){
			Tuple next = iterator.next();
			rightPage.deleteTuple(next);
			leftPage.insertTuple(next);
		}
		// 设置新的左右兄弟
		if(rightPage.getRightSiblingId() != null){
			BTreeLeafPage rightSibling = (BTreeLeafPage) getPage(tid,dirtypages,rightPage.getRightSiblingId(),Permissions.READ_WRITE);
			leftPage.setRightSiblingId(rightSibling.getId());
			rightSibling.setLeftSiblingId(leftPage.getId());
		}else {
			leftPage.setRightSiblingId(null);
		}
		// 删除右leaf
		setEmptyPage(tid,dirtypages,rightPage.getId().getPageNumber());
		deleteParentEntry(tid,dirtypages,leftPage,parent,parentEntry);
	}

image

public void mergeInternalPages(TransactionId tid, Map<PageId, Page> dirtypages,
			BTreeInternalPage leftPage, BTreeInternalPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry) 
					throws DbException, IOException, TransactionAbortedException {
		leftPage = (BTreeInternalPage) getPage(tid,dirtypages,leftPage.getId(),Permissions.READ_WRITE);
		rightPage = (BTreeInternalPage) getPage(tid,dirtypages,rightPage.getId(),Permissions.READ_WRITE);
		parent = (BTreeInternalPage) getPage(tid,dirtypages,parent.getId(),Permissions.READ_WRITE);

		BTreeEntry bTreeEntry = new BTreeEntry(parentEntry.getKey(),
												leftPage.reverseIterator().next().getRightChild(),
												rightPage.iterator().next().getLeftChild());
		leftPage.insertEntry(bTreeEntry);
		Iterator<BTreeEntry> iterator = rightPage.iterator();
		while (iterator.hasNext()){
			BTreeEntry next = iterator.next();
			rightPage.deleteKeyAndLeftChild(next);
			leftPage.insertEntry(next);
		}
		updateParentPointers(tid,dirtypages,leftPage);
		setEmptyPage(tid,dirtypages,rightPage.getId().getPageNumber());
		deleteParentEntry(tid,dirtypages,leftPage,parent,parentEntry);
	}

标签：dirtypages,parent,节点,next,Lab5,tid,MIT6.830,page
From： https://www.cnblogs.com/rockdow/p/18048627

相关文章

  • MIT6.830-Lab3
    simpleDB项目地址概览IntHistogram作用估计条件过滤某表的某个Int字段时，结果集记录数和该表记录总数的比例；StringHistogram类似IntHistogramTableStats作用存放某表各个字段对应的直方图对象（IntHistogram或StringHistogram类型）；使用静态对象ConcurrentMap<String,Tab......
  • MIT6.830-Lab2
    simpleDB项目地址实验部分实验1Predicate类用来存放对表记录进行条件过滤的信息（要过滤字段的序号，具体的比较规则，用来比较的字段），其内部的枚举类Op就是比较规则类，filter()方法的实现使用Field接口中的compare()即可。JoinPredicate类用来存放两表的记录进行连接的信息（两表......
  • MIT6.830-Lab1
    TupleDesc类TupleDesc类用来存储表结构，使用静态内部类TDItem封装字段类型和字段名称。Tuple类Tuple类用来存储具体的数据行，使用Filed接口数组存放不同字段类型的数据，使用TupleDesc成员变量存放与该数据行关联的表结构信息，使用RecordId成员变量存放该数据行的行号和所处的数......
  • mit6.828 - lab5笔记（上）
    文件系统结构unix的文件系统相关知识unix将可用的磁盘空间划分为两种主要类型的区域：inode区域和数据区域。unix为每个文件分配一个inode，其中保存文件的关键元数据，如文件的stat属性和指向文件数据块的指针。数据区域中的空间会被分成大小相同的数据块（就像内存管理中的分页）。数......
  • Lab5: 面向功能程序构造方法及创新应用 (基础)
    1、构造两数交换的函数，并验证各种参数形式代码#include<iostream>usingnamespacestd;//交换两个整数的值voidswap(int&a,int&b){inttemp=a;a=b;b=temp;}//交换两个浮点数的值voidswap(double&a,double&b){doubletemp=a;......
  • CS144-lab5
    Checkpoint5Writeup该lab较简单，没什么好说的有两点是route函数for循环时必须用引用，还是ttl递减后要重新计算checksum，写的时候被坑到了。至于找到最长前缀匹配，遍历路由表即可，注意prefix为0时要特判；为了方便判断是否在路由表中找到符合项，max_prefix设置为int8_t。voidRouter:......
  • MIT6.s081/6.828 lectrue07：Page faults 以及 Lab5 心得
    本篇博客主要是复习MIT6.s081/6.828lectrue07：Pagefaults以及记录Lab5：COWfork的心得值得一提的是，2020年之前的版本第5个lab是lazyalloction，但是到了2020年之后就换成了难度稍高一点的COWfork，有兴趣的小伙伴可以把lazyalloction也一起做一做~毕竟这些lab......
  • ICT实战系统集成-LAB5-OpenEuler软件管理
    系统集成-LAB5-OpenEuler软件管理1实验要求任务一：使用rpm包安装zziplib工具1、完成安装2、查询zziplib工具是否安装成功3、查询zziplib工具的文件列表和完整目录4、查询zziplib工具的详细信息5、对zziplib工具进行卸载任务二：使用yum/dnf安装java-1.8.01、完成yum/dnf源......
  • lab5：深入理解进程切换
    目录linux操作系统分析Lab5:深入理解进程切换context_switch函数执行过程1.prepare_task_switch()2.arch_start_context_switch()3.switch_mm_irqs_off()进程地址切换3.switch_to()实验总结linux操作系统分析Lab5:深入理解进程切换context_switch函数content_switch函......
  • lab5实验报告
    lab5实验报告一、实验思考题Thinking5.1/proc是一种由软件创建的特殊的伪文件系统，通过特殊的接口来访问内核。每一个文件对应于内核中的函数，其中大部分文件时只读的，但可......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99