In this assignment, you will implement a B+ tree in which leaf level pages contain entries of the form key, rid of a data record (Alternative 2 for data entries, in terms of the textbook.) You must implement the full search and insert algorithms as discussed in class. In particular, your insert routine must be capable of dealing with overflows (at any level of the tree) by splitting pages; as per the algorithm discussed in class, you will not consider re-distribution. For this assignment, you can deal with deletes by simply marking the corresponding leaf entry as `deleted'; you do not have to implement merging.
You will be given, among all other necessary packages and classes,
HFPage and BTSortedPage. BTSortedPage is derived from HFPage, and
it augments the
insertRecord method of HFPage by storing records on the
HFPage in sorted order by a specified key value.
The key value must be included as the initial part of each
record, to enable easy comparison of the key value of a new
record with the key values of existing records on a page.
The documentation available in the java code documentation is
sufficient to understand what operation each function performs.
You need to implement two page-level classes, BTIndexPage and BTLeafPage, both of which extends BTSortedPage. These page classes are used to build the B+ tree index; you will write code to create, destroy, open and close a B+ tree index, and to open scans that return all data entries (from the leaf pages) which satisfy some range selection on the keys.
You will carry out this assignment in teams of two, continuing with the same partner as for the previous assignment. If you want to change partners, you must let us know first.