next up previous
Next: Getting Started Up: BTree Previous: BTree

Introduction

In this assignment, you will implement a B+ tree in which leaf level pages contain entries of the form $\langle$key, rid of a data record$\rangle$ (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.


next up previous
Next: Getting Started Up: BTree Previous: BTree
2011-11-15