Merge two internal pages by moving all entries from the right page to the left page and "pulling down" the corresponding key from the parent entry. Delete the corresponding key and right child pointer from the parent, and recursively handle the case when the parent gets below minimum occupancy. Upda
(TransactionId tid, Map<PageId, Page> dirtypages, BTreeInternalPage leftPage, BTreeInternalPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry)
| 952 | * @throws TransactionAbortedException |
| 953 | */ |
| 954 | public void mergeInternalPages(TransactionId tid, Map<PageId, Page> dirtypages, |
| 955 | BTreeInternalPage leftPage, BTreeInternalPage rightPage, BTreeInternalPage parent, BTreeEntry parentEntry) |
| 956 | throws DbException, IOException, TransactionAbortedException { |
| 957 | |
| 958 | // some code goes here |
| 959 | // |
| 960 | // Move all the entries from the right page to the left page, update |
| 961 | // the parent pointers of the children in the entries that were moved, |
| 962 | // and make the right page available for reuse |
| 963 | // Delete the entry in the parent corresponding to the two pages that are merging - |
| 964 | // deleteParentEntry() will be useful here |
| 965 | //1. 获取两个节点的迭代器 |
| 966 | Iterator<BTreeEntry> leftIterator = leftPage.reverseIterator(); |
| 967 | Iterator<BTreeEntry> rightIterator = rightPage.iterator(); |
| 968 | BTreeEntry leftLastEntry = leftIterator.next(); |
| 969 | BTreeEntry rightFirstEntry = rightIterator.next(); |
| 970 | //2. 将两节点中间的父节点entry插入到左节点，并将其删除 |
| 971 | BTreeEntry midEntry = new BTreeEntry(parentEntry.getKey(), leftLastEntry.getRightChild(), rightFirstEntry.getLeftChild()); |
| 972 | leftPage.insertEntry(midEntry); |
| 973 | deleteParentEntry(tid,dirtypages,leftPage,parent,parentEntry); |
| 974 | //3. 插入右节点的第一个entry |
| 975 | rightPage.deleteKeyAndLeftChild(rightFirstEntry); |
| 976 | leftPage.insertEntry(rightFirstEntry); |
| 977 | //4. 循环插入右节点的entry |
| 978 | while(rightIterator.hasNext()){ |
| 979 | rightFirstEntry = rightIterator.next(); |
| 980 | rightPage.deleteKeyAndLeftChild(rightFirstEntry); |
| 981 | leftPage.insertEntry(rightFirstEntry); |
| 982 | } |
| 983 | //5. 更新左节点的子节点的父节点指向 |
| 984 | updateParentPointers(tid,dirtypages,leftPage); |
| 985 | //6. 设置空page |
| 986 | setEmptyPage(tid,dirtypages,rightPage.getId().getPageNumber()); |
| 987 | //7. 增加脏页 |
| 988 | dirtypages.remove(rightPage.getId()); |
| 989 | dirtypages.put(leftPage.getId(),leftPage); |
| 990 | dirtypages.put(parent.getId(),parent); |
| 991 | } |
| 992 | |
| 993 | /** |
| 994 | * Method to encapsulate the process of deleting an entry (specifically the key and right child) |