MIT 6.5830(6.830) Lab5

简介

本次实验要求实现B+树，需要对B+树具体的特性有很好的了解，然后实现它的搜索、插入和删除操作。具体的结构与大部分操作实验已经实现，这里只需要实现几个方法，分别是搜索叶子节点、在插入时子节点和叶子节点的分裂、在删除时从左右叶节点和中间节点”借“来元素以及两个节点的合并。

本来实现一个B+树是十分苦难的，但实验已经完成了太多的事情，我们只需要实现几个关键的逻辑即可。在实现这些操作的同时，还需要保证事务能够正常执行，这也是我没有完成的一点，这就是前面实现的有问题，导致事务和锁的测试无法通过。我改了一天的bug，但加上学期末事情比较多，就先搁置了。。

Exercises

Exercise 1

根据索引项查找一个Tuple应该插入到哪个节点之中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private BTreeLeafPage findLeafPage(TransactionId tid, Map<PageId, Page> dirtypages, BTreePageId pid, Permissions perm,
                                      Field f)
           throws DbException, TransactionAbortedException {
       // TODO: some code goes here
       if (pid.pgcateg() == BTreePageId.INTERNAL) {
           BTreeInternalPage page = (BTreeInternalPage) getPage(tid, dirtypages, pid, Permissions.READ_ONLY);
           Iterator<BTreeEntry> iterator = page.iterator();
           if (f == null) return findLeafPage(tid, dirtypages, iterator.next().getLeftChild(), perm, f);
           BTreeEntry prev = null;
           while (iterator.hasNext()) {
               BTreeEntry next = iterator.next();
               if (next.getKey().compare(Op.GREATER_THAN_OR_EQ, f)) return findLeafPage(tid, dirtypages, next.getLeftChild(), perm, f);
               prev = next;
           }
           return findLeafPage(tid, dirtypages, prev.getRightChild(), perm, f);
       }
       if (pid.pgcateg() == BTreePageId.LEAF) {
           return (BTreeLeafPage) getPage(tid, dirtypages, pid, perm);
       }
       return null;
   }

Exercise 2

插入一个元组之后，索引树的变化，当一个节点满了之后，主要是节点分裂的函数

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
public BTreeLeafPage splitLeafPage(TransactionId tid, Map<PageId, Page> dirtypages, BTreeLeafPage page, Field field)
           throws DbException, IOException, TransactionAbortedException {
       // TODO: 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.
       int leftNum = page.getNumTuples() / 2;
       int rightNum = page.getNumTuples() - leftNum;
       int pt = 0;
       Tuple rightFirst = null;
       BTreeLeafPage rightPage = (BTreeLeafPage) getEmptyPage(tid, dirtypages, BTreePageId.LEAF);
       Iterator<Tuple> tupleIterator = page.reverseIterator();
       while (tupleIterator.hasNext() && pt < rightNum) {
           Tuple t = tupleIterator.next();
           rightFirst = t;
           page.deleteTuple(t);
           rightPage.insertTuple(t);
           pt ++;
       }
       rightPage.setRightSiblingId(page.getRightSiblingId());
       if (page.getRightSiblingId() != null) {
           BTreeLeafPage page1 = (BTreeLeafPage) getPage(tid, dirtypages, page.getRightSiblingId(), Permissions.READ_WRITE);
           page1.setLeftSiblingId(rightPage.getId());
           dirtypages.put(page1.getId(), page1);
       }
       page.setRightSiblingId(rightPage.getId());
       rightPage.setLeftSiblingId(page.getId());
       dirtypages.put(page.getId(), page);
       dirtypages.put(rightPage.getId(), rightPage);
       BTreeInternalPage parent = getParentWithEmptySlots(tid, dirtypages, page.getParentId(), rightFirst.getField(keyField));
       parent.insertEntry(new BTreeEntry(rightFirst.getField(keyField), page.getId(), rightPage.getId()));
       dirtypages.put(parent.getId(), parent);
       updateParentPointers(tid, dirtypages, parent);
       return rightFirst.getField(keyField).compare(Op.GREATER_THAN_OR_EQ, field) ? page : rightPage;
   }
public BTreeInternalPage splitInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
                                              BTreeInternalPage page, Field field)
           throws DbException, IOException, TransactionAbortedException {
       // TODO: 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.
       int num = page.getNumEntries(), pt = 0;
       Iterator<BTreeEntry> iterator = page.reverseIterator();
       BTreeInternalPage rightPage = (BTreeInternalPage) getEmptyPage(tid, dirtypages, BTreePageId.INTERNAL);
       while (iterator.hasNext() && pt < num / 2) {
           BTreeEntry next = iterator.next();
           page.deleteKeyAndRightChild(next);
           rightPage.insertEntry(next);
           pt ++;
       }
       BTreeEntry next = iterator.next();
       page.deleteKeyAndRightChild(next);
       next.setLeftChild(page.getId());
       next.setRightChild(rightPage.getId());
       BTreeInternalPage parent = getParentWithEmptySlots(tid, dirtypages, page.getParentId(), next.getKey());
       parent.insertEntry(next);
       dirtypages.put(page.getId(), page);
       dirtypages.put(rightPage.getId(), rightPage);
       dirtypages.put(parent.getId(), parent);
       updateParentPointers(tid, dirtypages, parent);
       updateParentPointers(tid, dirtypages, page);
       updateParentPointers(tid, dirtypages, rightPage);

       return next.getKey().compare(Op.GREATER_THAN_OR_EQ, field) ? page : rightPage;
   }

Exercise 3

删除一个元组后，索引树的变化，删除操作会导致叶节点变得半满，此时需要从兄弟节点借元素，这也会导致非叶子节点元素变少，递归的进行补充的操作，包括借元素与两个兄弟节点合并。

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
    public void stealFromLeafPage(BTreeLeafPage page, BTreeLeafPage sibling,
                                  BTreeInternalPage parent, BTreeEntry entry, boolean isRightSibling) throws DbException {
        // TODO: 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 totalNum = page.getNumTuples() + sibling.getNumTuples();
        int cnt = totalNum / 2 - page.getNumTuples();
        if (isRightSibling) {
            Iterator<Tuple> iterator = sibling.iterator();
            Tuple next = null;
            for (int i = 0; i < cnt; i++) {
                next = iterator.next();
                sibling.deleteTuple(next);
                page.insertTuple(next);
            }
            parent.deleteKeyAndRightChild(entry);
            BTreeEntry newEntry = new BTreeEntry(next.getField(keyField), page.getId(), sibling.getId());
            parent.insertEntry(newEntry);
        } else {
            Iterator<Tuple> tupleIterator = sibling.reverseIterator();
            Tuple tuple = null;
            for (int i = 0; i < cnt; i++) {
                tuple = tupleIterator.next();
                sibling.deleteTuple(tuple);
                page.insertTuple(tuple);
            }

            parent.deleteKeyAndRightChild(entry);
            BTreeEntry newEntry = new BTreeEntry(tuple.getField(keyField), sibling.getId(), page.getId());
            parent.insertEntry(newEntry);
        }
    }
    public void stealFromLeftInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
                                          BTreeInternalPage page, BTreeInternalPage leftSibling, BTreeInternalPage parent,
                                          BTreeEntry parentEntry) throws DbException, TransactionAbortedException {
        // TODO: 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 totalNum = page.getNumEntries() + leftSibling.getNumEntries();
        Iterator<BTreeEntry> iterator = leftSibling.reverseIterator();

        int cnt = totalNum / 2 - page.getNumEntries();

        for (int i = 0; i < cnt; i++) {
            BTreeEntry next = iterator.next();
            leftSibling.deleteKeyAndRightChild(next);
            page.insertEntry(new BTreeEntry(parentEntry.getKey(), next.getRightChild(), page.iterator().next().getLeftChild()));
//            page.insertEntry(next);
            parentEntry.setKey(next.getKey());
            parent.updateEntry(parentEntry);

        }
        dirtypages.put(parent.getId(), parent);
        dirtypages.put(leftSibling.getId(), leftSibling);
        dirtypages.put(page.getId(), page);
        updateParentPointers(tid, dirtypages, parent);
        updateParentPointers(tid, dirtypages, leftSibling);
        updateParentPointers(tid, dirtypages, page);

    }
    public void stealFromRightInternalPage(TransactionId tid, Map<PageId, Page> dirtypages,
                                           BTreeInternalPage page, BTreeInternalPage rightSibling, BTreeInternalPage parent,
                                           BTreeEntry parentEntry) throws DbException, TransactionAbortedException {
        // TODO: 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 totalNum = page.getNumEntries() + rightSibling.getNumEntries();
        int cnt = totalNum / 2 - page.getNumEntries();
        Iterator<BTreeEntry> iterator = rightSibling.iterator();
        for (int i = 0; i < cnt; i++) {
            BTreeEntry next = iterator.next();
            rightSibling.deleteKeyAndLeftChild(next);
            page.insertEntry(new BTreeEntry(parentEntry.getKey(), page.reverseIterator().next().getRightChild(), next.getLeftChild()));
            parentEntry.setKey(next.getKey());
            parent.updateEntry(parentEntry);
        }
        dirtypages.put(parent.getId(), parent);
        dirtypages.put(rightSibling.getId(), rightSibling);
        dirtypages.put(page.getId(), page);
        updateParentPointers(tid, dirtypages, parent);
        updateParentPointers(tid, dirtypages, rightSibling);
        updateParentPointers(tid, dirtypages, page);
    }
    public void mergeLeafPages(TransactionId tid, Map<PageId, Page> dirtypages,
                               BTreeLeafPage leftPage, BTreeLeafPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry)
            throws DbException, IOException, TransactionAbortedException {

        // TODO: 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
        Iterator<Tuple> iterator = rightPage.iterator();
        while (iterator.hasNext()) {
            Tuple next = iterator.next();
            rightPage.deleteTuple(next);
            leftPage.insertTuple(next);
        }
        BTreePageId rightSiblingId = rightPage.getRightSiblingId();
        if (rightSiblingId == null) {
            leftPage.setRightSiblingId(null);
        } else {
            leftPage.setRightSiblingId(rightSiblingId);
            BTreeLeafPage page = (BTreeLeafPage) getPage(tid, dirtypages, rightSiblingId, Permissions.READ_WRITE);
            page.setLeftSiblingId(leftPage.getId());
        }

        deleteParentEntry(tid, dirtypages, leftPage, parent, parentEntry);
        setEmptyPage(tid, dirtypages, rightPage.getId().getPageNumber());
        dirtypages.put(parent.getId(), parent);
        dirtypages.put(leftPage.getId(), leftPage);
        //dirtypages.put(rightPage.getId(), rightPage);
    }
    public void mergeInternalPages(TransactionId tid, Map<PageId, Page> dirtypages,
                                   BTreeInternalPage leftPage, BTreeInternalPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry)
            throws DbException, IOException, TransactionAbortedException {

        // TODO: 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
        BTreeEntry mid = new BTreeEntry(parentEntry.getKey(), leftPage.reverseIterator().next().getRightChild(),
                rightPage.iterator().next().getLeftChild());
        leftPage.insertEntry(mid);
        Iterator<BTreeEntry> iterator = rightPage.iterator();
        BTreeEntry prev = null;
        boolean flag = false;
        while (iterator.hasNext()) {
            BTreeEntry next = iterator.next();

            rightPage.deleteKeyAndLeftChild(next);
            leftPage.insertEntry(next);
        }

        dirtypages.put(parent.getId(), parent);
        dirtypages.put(leftPage.getId(), leftPage);
        //dirtypages.put(rightPage.getId(), rightPage);
        deleteParentEntry(tid, dirtypages, leftPage, parent, parentEntry);
        setEmptyPage(tid, dirtypages, rightPage.getId().getPageNumber());
        updateParentPointers(tid, dirtypages, parent);
        updateParentPointers(tid, dirtypages, leftPage);
    }

测试

除了BTreeNextKeyLockingTest和BTreeTest之外全部通过

1
2
3
4
5
6
7
8
9
ant runtest -Dtest=BTreeFileReadTest
ant runsystest -Dtest=BTreeScanTest
ant runtest -Dtest=BTreeFileInsertTest
ant runsystest -Dtest=BTreeFileInsertTest
ant runtest -Dtest=BTreeFileDeleteTest
ant runsystest -Dtest=BTreeFileDeleteTest
ant runtest -Dtest=BTreeNextKeyLockingTest
				   BTreeDeadlockTest
ant runsystest -Dtest=BTreeTest

事件记录

开始时间：2022.12.12

结束时间：2022.12.13

耗时：2天