# Database Lab 4 Report

### Exercise 1
- `findLeafPage()`: It iterates all entries in a `BTreeInternalPage` and compare current entry with the target field. If the target is`null`, always return `findLeafPage(cur.getLeftChild())`. Once finding an entry greater or equal to the target, return `findLeafPage(cur.getLeftChild())` to recursively search the target in its left subtree. Return `findLeafPage(cur.getRightChild())` if the iterator reaches the end.

### Exercise 2
- `splitLeafPage()`: Create an empty `BTreeLeafPage` and move right half of tuples in the original page using `reverseIterator()`. Create a new `BTreeEntry` with the middle field of the original page and insert it into the `BTreeInternalPage` returned by `getParentWithEmptySlots()`. Update all necessary pointers, e.g. parent, sibling. Compare the middle field with the target and return which page to insert.
- `splitInternalPage()`: Create an empty `BTreeInternalPage` and move right half of tuples in the original page using `reverseIterator()`. Move the middle entry of the original page into the `BTreeInternalPage` returned by `getParentWithEmptySlots()`. Update all necessary pointers, e.g. parent, child. Compare the middle entry's field with the target and return which page to insert.

### Exercise 3
- `steaFromLeafPage()`: We select the appropriate iterator based on the type of sibling and iterate through the tuples in the entry, deleting them while updating the parent entry
- `stealFromLeftInternalPage()`: Use the reverse iterator of the left sibling to iterate through the entries and insert them into the new BTree entry, while updating the parent and the respective pointers, and deleting the iterated entries on the left sibling. When there are no more entries left, we end the iteration
- `StealFromRightInternalPage()`: Use the iterator of the right sibling to iterate through the entries and insert them into the new BTree entry, while updating the parent and the respective pointers, and deleting the iterated entries on the right sibling. When there are no more entries left, we end the iteration

### Exercise 4
- `mergeLeafPages()`:
- Create an iterator for right page's tuples, which is used to delete them from right page then insert into left page.
- Update the new right sibling's left pointer (if the previous right page has right sibling) by `setLeftSiblingId()`, which sets the left pages's id to the new right page as left sibling. Update the left page's right sibling pointer by `setRightSiblingId()`, which sets the new right pages's id to the left page as right sibling.
- Empty right page by `setEmptyPage()` to make it available for reuse.
- Delete the corresponding key and right child pointer from parent using `deleteParentEntry()`.
- `mergeInternalPages()`:
- Delete the corresponding key and right child pointer from parent using `deleteParentEntry()`.
- Create an iterator for right page's entries, which is used to delete them from right page then insert into left page.
- Insert the index node in parent into the left page by setting right child of the last entry in left page as left child, and the left child of first entry in right page as right child.
- Empty right page by `setEmptyPage()` to make it available for reuse.
- Update the parent pointers of the children in the entries that were moved by calling `updateParentPointers()` on the udpate left page.