More Than Code

Simple-DB Lab5

发表于 分类于
本文字数： 16k 阅读时长 ≈ 15 分钟

MIT-6.830 Lab5 总结与备忘

  • 实现B+树的一些关键操作（tuple的增删改查）
  • 已经有实现树形结构所需的所有底层代码，Lab5要实现搜索tuple、拆分Page、在Page间重新分配tuple、合并Page
  • B+树内部节点包含多个entry，每个entry由一个键值和一个左、右子指针组成。相邻的键共享一个子指针，因此包含m个键的内部节点有m+1个子指针。叶子节点可以包含数据条目，或指向其他数据库文件的数据entry的指针
  • Lab5的B+树，叶子Page包含数据条目，相邻叶子Page用左右的同级指针连接——范围扫描通过根节点和内部节点一次搜索就可以找到第一个叶子Page，后面的叶子Page根据同级指针找到
  • BTreeFile由四种不同的Page组成
    • 树的节点有叶子Page（BTreeLeafPage.java）、内部Page（BTreeInternalPage.java），BTreePage.java有一个抽象类，包含叶子页和内部页的共同代码
    • HeaderPage（BTreeHeaderPage.java）跟踪文件中哪些Page正在使用
    • 每个BTreeFile的开头有一个Page，指向树的根Page和第一个HeaderPage，在BTreeRootPtrPage.java种实现
    • Lab5的代码需要用到这些类的接口

Exercise 1

思路整理

  • Implement index/BTreeFile.findLeafPage()，通过BTreeFileReadTest.java和BTreeScanTest.java系统测试

  • findLeafPage()在给定一个特定key时（也就是参数Field f，在比较时需要Field.compare(Op.GREATER_THAN_OR_EQ, f)），找到合适的leafPage，用于搜索和插入

    • 根节点是一个InternalPage，有一个Entry，有一个键和两个child指针。如果有重复的key，则返回第一个（左边）的leafPage

    • findLeafPage()应该递归地搜索内部节点，直到到达与所提供的键值相对应的leafPage

    • 每一步应该遍历InternalPage的Entry，将条目值与提供的key——BTreeInternalPage.iterator()使用BTreeEntry.java中定义的接口，提供对InternalPage的条目的访问。迭代器可以遍历InternalPage中的键值，并访问key的左右子页面ID

    • 当BTreePageId.pgcateg()等于BTreePageId.LEAF时，从缓冲池中获取该页并返回它

    • 如果提供的键值f为空，向最左边的子页递归

    • 调用BTreeFile.getPage()来从磁盘中获取Page。工作原理与BufferPool.getPage()完全一样，但需要额外的参数来跟踪脏页的列表

    • 访问每一个InternalPage时，权限应当为READ_ONLY

具体实现

  • 具体实现如下：（如果理解了B+树中，结点的结构就知道该调用什么样的接口）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    /**
     * Recursive function which finds and locks the leaf page in the B+ tree corresponding to
     * the left-most page possibly containing the key field f. It locks all internal
     * nodes along the path to the leaf node with READ_ONLY permission, and locks the 
     * leaf node with permission perm.
     * 
     * If f is null, it finds the left-most leaf page -- used for the iterator
     * 
     * @param tid - the transaction id
     * @param dirtypages - the list of dirty pages which should be updated with all new dirty pages
     * @param pid - the current page being searched
     * @param perm - the permissions with which to lock the leaf page
     * @param f - the field to search for
     * @return the left-most leaf page possibly containing the key field f
     * 
     */
    private BTreeLeafPage findLeafPage(TransactionId tid, Map<PageId, Page> dirtypages, BTreePageId pid, Permissions perm,
                                          Field f)
    				throws DbException, TransactionAbortedException {
    	// some code goes here
    	// 递归查找
    	if (pid.pgcateg() == BTreePageId.LEAF) {  // 当前page是leafPage
    		return (BTreeLeafPage) this.getPage(tid, dirtypages, pid, perm);
    	} else {
    		// 根据PageID获取internalPage
    		BTreeInternalPage curPage = (BTreeInternalPage) this.getPage(tid, dirtypages, pid, Permissions.READ_ONLY);
    		Iterator<BTreeEntry> iterator = curPage.iterator();
    		if (f == null) {  // 如果field为空，则返回最左边的child
    			return findLeafPage(tid, dirtypages, curPage.getChildId(0), perm, null);
    		}
    		// 遍历InternalPage的entry，注意child的数目为entry+1
    		while (iterator.hasNext()) {
    			BTreeEntry curEntry = iterator.next();
    			if (curEntry.getKey().compare(Op.GREATER_THAN_OR_EQ, f)) {
    				return findLeafPage(tid, dirtypages, curEntry.getLeftChild(), perm, f);
    			}
    		}
    		// 最后一个child
    		return findLeafPage(tid, dirtypages, curPage.getChildId(curPage.getNumEntries()-1), perm, f);
    	}
    }

Exercise 2

思路整理

  • Implement BTreeFile.splitLeafPage()和BTreeFile.splitInternalPage()，通过BTreeFileInsertTest单元测试，和BTreeFileInsertTest系统测试
  • findLeafPage()可以用于找应该插入tuple的叶子页，如果叶子页满了，则需要分裂。每次叶子页分裂时，要向父节点添加分裂后第二页的第一个tuple对应的entry。如果父节点也是满的，则需要递归分裂，可能最终创建一个新的根节点——此时需要创建一个新的内部节点，成为新的根页面，并更新BTreeRootPtrPage
  • splitLeafPage()中应该将键”复制”到父页上，splitInternalPage()中应该将键”推”到父页上，而当一个内部节点被分割时，需要更新所有被移动的子节点的父指针（用到updateParentPointers()），并更新被拆分的叶子页面的兄弟姐妹指针。最后，要返回新的tuple或entry应该被插入的页面
  • 在分裂时，需要以READ_WRITE权限获取父页，必要时递归分割，并添加一个新条目——此时需要用到getParentWithEmptySlots()
  • 创建一个新的页面时，要调用getEmptyPage()来获取新的Page
  • 使用BTreeLeafPage.iterator()和BTreeInternalPage.iterator()以迭代页面中的tuple和条目。反向迭代器BTreeLeafPage.reverseIterator()和BTreeInternalPage.reverseIterator()适用于将一个页面中的tuple/条目子集移动到其右边的同级页面；BTreeInternalPage.iterator()有一个key和两个child pointers，以及一个recordId用于识别底层页面上键和子指针的位置
  • BTreeEntry只是一个接口，不是实际存储在页面上的对象，因此更新BTreeEntry的字段不会修改底层页面，为了改变页面的数据需要调用BTreeInternalPage.updateEntry()，而BTreeInternalPage.deleteKeyAndLeftChild()和BTreeInternalPage.deleteKeyAndRightChild()来删除一个key和相应子结点

具体实现

  • 牢记Entry、key、子节点之间的关系

  • splitLeafPage：先通过getEmptyPage()从创建新的LeafPage，然后将原来Page中一半的tuple（LeafPage中存储的是Tuple，而不是Entry）移动到新的Page中。将新的LeafPage插入到双向链表（注意可能它是链表的尾结点）；获得要推送给父节点的key（key是一个Field类型的变量，来自新Page的第一个tuple），通过getParentWithEmptySlots获取父页，父页插入以key为键、以page和newPage为左右子节点的Entry，最后``updateParentPointer()`更新所有被移动的子结点的父指针。以上过程，修改了的LeafPage和InternalPage，都要加入dirtyPage

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    public BTreeLeafPage splitLeafPage(TransactionId tid, Map<PageId, Page> dirtypages, BTreeLeafPage page, Field field)
            throws DbException, IOException, TransactionAbortedException {
        // some code goes here
        //
        // Split the leaf page by adding a new page on the right of the existing
        // page and moving half of the tuples to the new page.  Copy 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 sibling pointers of all the affected leaf pages.  Return the page into which a
        // tuple with the given key field should be inserted.
        BTreeLeafPage newPage = (BTreeLeafPage) getEmptyPage(tid, dirtypages, BTreePageId.LEAF);  // 用getEmptyPage获得一个新的page
        int tuples = page.getNumTuples();
        for (int i = tuples / 2; i < tuples; i++) {  // 将一半的tuple移到新的leafPage
            Tuple tupleMove = page.getTuple(i);
            page.deleteTuple(tupleMove);
            newPage.insertTuple(tupleMove);
        }
      
        // 将新的leafPage插入双向链表
        if (page.getRightSiblingId() != null) {
            BTreeLeafPage rightPage = (BTreeLeafPage) this.getPage(tid, dirtypages, page.getRightSiblingId(), Permissions.READ_WRITE);
            newPage.setRightSiblingId(rightPage.getId());
            rightPage.setLeftSiblingId(newPage.getId());
            dirtypages.put(rightPage.getId(), rightPage);  // 修改了rightPage，将其加入脏页的跟踪map
        }
        page.setRightSiblingId(newPage.getId());
        newPage.setLeftSiblingId(page.getId());
      
        Tuple push = newPage.getTuple(0);  // 获得要推送给父节点的tuple，以及key（一般为中间的tuple）
        Field key = push.getField(newPage.keyField);
        BTreeInternalPage parentPage = this.getParentWithEmptySlots(tid, dirtypages, page.getParentId(), field);
        parentPage.insertEntry(new BTreeEntry(key, page.getId(), newPage.getId()));
      
        updateParentPointer(tid, dirtypages, parentPage.getId(), page.getId());
        updateParentPointer(tid, dirtypages, parentPage.getId(), newPage.getId());
      
        dirtypages.put(parentPage.getId(), parentPage);
        dirtypages.put(page.getId(), page);
        dirtypages.put(newPage.getId(), newPage);
      
        if (field.compare(Op.GREATER_THAN_OR_EQ, key)) {
            return newPage;
        } else {
            return page;
        }
    }

  • splitInternalPage：与上面过程相似，将原来InternalPage中一半的Entry移动的新的Page中。这里通过reverseIterator从后向前遍历Entry，通过deleteKeyAndRightChild()将原Page中的相应entry删除。找到要推给父节点的Entry，从page中删除，设置该Entry左右子节点为page和newPage后，父节点再insert（一定先设置，再insert）。最后通过updateParentPointers()更新父指针。最后返回的时候，用参数field要比较的是推送给父节点的Entry的Key

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    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 newPage = (BTreeInternalPage) getEmptyPage(tid, dirtypages, BTreePageId.INTERNAL);  // 用getEmptyPage获得一个新的page
        int numEntries = page.getNumEntries();
        Iterator<BTreeEntry> iterator = page.reverseIterator();  // 要访问entry只能通过迭代器
        for (int i = 0; i < numEntries / 2; i++) {  // 将一半的entry移到新的InternalPage
            BTreeEntry curEntry = iterator.next();
            page.deleteKeyAndRightChild(curEntry);  // 画图理解为什么为RightChild。这里Entry的数目=key+1=childern+1
            newPage.insertEntry(curEntry);
        }
      
        BTreeEntry push = iterator.next();  // 这个entry属于page，而非newPage。是page的最后一个entry
        // 这个entry要删除，推送到父节点，然后entry的左右分别为page和newPage
        page.deleteKeyAndRightChild(push);
        BTreeInternalPage parentPage = this.getParentWithEmptySlots(tid, dirtypages, page.getParentId(), push.getKey());
        push.setLeftChild(page.getId());
        push.setRightChild(newPage.getId());
        parentPage.insertEntry(push);  // 先设置左右子节点，再insert到父节点
      
        updateParentPointers(tid, dirtypages, page);
        updateParentPointers(tid, dirtypages, newPage);
        updateParentPointers(tid, dirtypages, parentPage);
      
        dirtypages.put(parentPage.getId(), parentPage);
        dirtypages.put(page.getId(), page);
        dirtypages.put(newPage.getId(), newPage);
      
        if (field.compare(Op.GREATER_THAN_OR_EQ, push.getKey())) {
            return newPage;
        } else {
            return page;
        }
    }

Exercise 3、4

思路整理

  • Implement BTreeFile.stealFromLeafPage()、BTreeFile.stealFromLeftInternalPage()、BTreeFile.stealFromRightInternalPage()

  • Implement BTreeFile.mergeLeafPages()、BTreeFile.mergeInternalPages()，通过BTreeFileDeleteTest单元测试和BTreeFileDeleteTest系统测试。B+ trees can prevent phantom tuples from showing up between two consecutive range scans by using next-key locking，而SimpleDB实现了Page level的两阶段锁，因此如果以上的实现正确，应当能自然地实现protection against phantoms，因此还应当通过BTreeDeadlockTest、BTreeNextKeyLockingTest单元测试，和BTreeTest系统测试

  • B+树中的删除可能导致页面重新分配tuple或合并

    image-20220623142716472 image-20220623143006253 * 从不满一半的LeafPage删除一个tuple，如果兄弟Page有多余的tuple，该页从兄弟Page拿取tuple，并且tuples在两个页面之间平均分配，父页的Entry相应更新 * 如果兄弟Page也没有多余的tuple，则两个Page合并，从父页删除Entry。此时，可能会导致递归的合并，甚至删除根结点

  • stealFrom方法中，兄弟Page的tuple/entry足够，不需要合并。stealFromLeftInternalPage()，stealFromRightInternalPage()还需要更新被移动的子项的父项指针——使用updateParentPointers()

  • mergeLeafPages()和mergeInternalPages()，需要执行splitLeafPage()和splitInternalPage()的逆过程，需要用到deleteParentEntry()，并对被删除的Page调用setEmptyPage()。需要用BTreeFile.getPage()来获取Page，并更新脏页面Map

具体实现

  • 基本上按照移动过程即可，还是要注意entry的结构

  • Steal：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    public void stealFromLeafPage(BTreeLeafPage page, BTreeLeafPage sibling,
                                  BTreeInternalPage parent, BTreeEntry entry, boolean isRightSibling) throws DbException {
        // some code goes here
        //
        // Move some of the tuples from the sibling to the page so
        // that the tuples are evenly distributed. Be sure to update
        // the corresponding parent entry.
        int numInsert = (page.getNumTuples() + sibling.getNumTuples()) / 2 - page.getNumTuples();
        Iterator<Tuple> iterator = isRightSibling ? sibling.iterator() : sibling.reverseIterator();
        for (int i = 0; i < numInsert; i++) {
            Tuple curTuple = iterator.next();
            sibling.deleteTuple(curTuple);
            page.insertTuple(curTuple);
        }
      
        entry.setKey(iterator.next().getField(this.keyField));
        parent.updateEntry(entry);
    }

    public void stealFromLeftInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
                                          BTreeInternalPage page, BTreeInternalPage leftSibling, BTreeInternalPage parent,
                                          BTreeEntry parentEntry) throws DbException, TransactionAbortedException {
        // some code goes here
        // Move some of the entries from the left sibling to the page so
        // that the entries are evenly distributed. Be sure to update
        // the corresponding parent entry. Be sure to update the parent
        // pointers of all children in the entries that were moved.
        int numEntrySteal = (page.getNumEntries() + leftSibling.getNumEntries()) / 2 - page.getNumEntries();
        Iterator<BTreeEntry> iterator = leftSibling.reverseIterator();
        BTreeEntry curEntry = iterator.next();
        // 将原来的parentEntry拉下来
        // parentEntry比page的entry的key都要小，比leftpage的entry都要大
        BTreeEntry midEntry = new BTreeEntry(parentEntry.getKey(), curEntry.getRightChild(), page.iterator().next().getLeftChild());
        page.insertEntry(midEntry);
        numEntrySteal -= 1;
        // 平衡entry数目
        for (int i = 0; i < numEntrySteal; i++) {
            leftSibling.deleteKeyAndRightChild(curEntry);
            page.insertEntry(curEntry);
            curEntry = iterator.next();
        }
      
        // 此时的curEntry是leftInternalPage的最后一个entry，也是要push给父节点的entry
        leftSibling.deleteKeyAndRightChild(curEntry);
        parentEntry.setKey(curEntry.getKey());
        parent.updateEntry(parentEntry);
      
        dirtypages.put(page.getId(), page);
        dirtypages.put(leftSibling.getId(), leftSibling);
        dirtypages.put(parent.getId(), parent);
      
        updateParentPointers(tid, dirtypages, page);
        updateParentPointers(tid, dirtypages, leftSibling);
    }

    public void stealFromRightInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
                                           BTreeInternalPage page, BTreeInternalPage rightSibling, BTreeInternalPage parent,
                                           BTreeEntry parentEntry) throws DbException, TransactionAbortedException {
        // some code goes here
        // Move some of the entries from the right sibling to the page so
        // that the entries are evenly distributed. Be sure to update
        // the corresponding parent entry. Be sure to update the parent
        // pointers of all children in the entries that were moved.
        int numEntrySteal = (page.getNumEntries() + rightSibling.getNumEntries()) / 2 - page.getNumEntries();
        Iterator<BTreeEntry> iterator = rightSibling.iterator();
        BTreeEntry curEntry = iterator.next();
        // 将原来的parentEntry拉下来
        // parentEntry比page的entry的key都要大，比rightpage的entry都要小
        BTreeEntry midEntry = new BTreeEntry(
                parentEntry.getKey(),
                page.reverseIterator().next().getRightChild(),
                curEntry.getLeftChild()
        );
        page.insertEntry(midEntry);
        numEntrySteal -= 1;
        // 平衡entry数目
        for (int i = 0; i < numEntrySteal; i++) {
            rightSibling.deleteKeyAndLeftChild(curEntry);
            page.insertEntry(curEntry);
            curEntry = iterator.next();
        }
      
        // 此时的curEntry是rightInternalPage的第一个entry，也是要push给父节点的entry
        rightSibling.deleteKeyAndLeftChild(curEntry);
        parentEntry.setKey(curEntry.getKey());
        parent.updateEntry(parentEntry);
      
        dirtypages.put(page.getId(), page);
        dirtypages.put(rightSibling.getId(), rightSibling);
        dirtypages.put(parent.getId(), parent);
      
        updateParentPointers(tid, dirtypages, page);
        updateParentPointers(tid, dirtypages, rightSibling);
    }

  • Merge：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    public void mergeLeafPages(TransactionId tid, Map<PageId, Page> dirtypages,
                               BTreeLeafPage leftPage, BTreeLeafPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry)
            throws DbException, IOException, TransactionAbortedException {
        // some code goes here
        //
        // 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
      
        // 将tuples挪给左边
        Iterator<Tuple> rightIterator = rightPage.iterator();
        while (rightIterator.hasNext()) {
            Tuple curTuple = rightIterator.next();
            rightPage.deleteTuple(curTuple);
            leftPage.insertTuple(curTuple);
        }
      
        if (rightPage.getRightSiblingId() == null) {
            leftPage.setRightSiblingId(null);
        } else {
            leftPage.setRightSiblingId(rightPage.getRightSiblingId());
            BTreeLeafPage nextPage = (BTreeLeafPage) this.getPage(tid, dirtypages, rightPage.getRightSiblingId(), Permissions.READ_WRITE);
            nextPage.setLeftSiblingId(leftPage.getId());
        }
      
        this.setEmptyPage(tid, dirtypages, rightPage.getId().getPageNumber());
        this.deleteParentEntry(tid, dirtypages, leftPage, parent, parentEntry);
      
        dirtypages.put(rightPage.getId(), rightPage);  // todo: 这里是否还要放入dirtyPage？
        dirtypages.put(leftPage.getId(), leftPage);
        dirtypages.put(parent.getId(), parent);
    }
      
    public void mergeInternalPages(TransactionId tid, Map<PageId, Page> dirtypages,
                                   BTreeInternalPage leftPage, BTreeInternalPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry)
            throws DbException, IOException, TransactionAbortedException {
        // some code goes here
        //
        // Move all the entries from the right page to the left page, update
        // the parent pointers of the children in the entries that were moved,
        // 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
      
        // 添加一个连接左右page最后一个和第一个child的entry
        Iterator<BTreeEntry> rightIterator = rightPage.iterator();
        BTreeEntry curEntry = rightIterator.next();
        BTreeEntry concate = new BTreeEntry(
                parentEntry.getKey(),
                leftPage.reverseIterator().next().getRightChild(),
                curEntry.getLeftChild()
        );
        leftPage.insertEntry(concate);
        // 将rightPage的entry移动到左边
        while (rightIterator.hasNext()) {
            rightPage.deleteKeyAndLeftChild(curEntry);
            leftPage.insertEntry(curEntry);
            curEntry = rightIterator.next();
        }
        rightPage.deleteKeyAndLeftChild(curEntry);
        leftPage.insertEntry(curEntry);
      
        // 更新父节点指针
        updateParentPointers(tid, dirtypages, leftPage);
        setEmptyPage(tid, dirtypages, rightPage.getId().getPageNumber());
        this.deleteParentEntry(tid, dirtypages, leftPage, parent, parentEntry);
      
        dirtypages.put(rightPage.getId(), rightPage);
        dirtypages.put(leftPage.getId(), leftPage);
        dirtypages.put(parent.getId(), parent);
    }
相关文章推荐