Extra Credit (5%)

Due Sunday by 11:59pm Points 50 Submitting a website url

Start Assignment

Integration of B+tree with previous work on heapfile

By itself, a B+ tree is interesting, but not particularly useful. To see the benefit of a B+ tree in action, we must

integrate it with the other parts of our DBMS.

There are two additional pieces of functionality required to integrate our B+ trees:

* Storing a B+ tree in a HeapFile

* Constructing a B+ from a HeapFile

If you wish to tackle this, consider the following:

* You will need a mapping from a B+ node to a tuple. The size of the tuple is important, as that will dictate the

degree of the B+ tree. This will differ depending on whether or not we use ints or strings as the key.

* When storing a B+ tree to a HeapFile one node from our tree (either a LeafNode or an InnerNode ) will

correspond to one page in our HeapFile . The structure of the page should be roughly the same regardless of

node type.

* Numbering the nodes in our tree becomes important for storage purposes. Each node should know which

page it belongs to in the heap file.

* Reading in a tree works in the exact opposite way: read in one page at a time and turn that page into a Node.

The tricky part here comes from determining whether a page represents an InnerNode or a LeafNode . Note that

since our tree is balanced, we can easily determine how many inner nodes there are based on the number of

pages. If we are careful about how we store nodes (for example, first n pages are inner nodes, all others are

leaf nodes), then we can solve this problem.

* Our Catalog should be updated to provide a method to create an index for a given table. It should also look

for an index when a table is imported (by searching for tablenameindex.dat, for example) and load the index if it

exists. The metadata for a table will need to be updated to include any indexes that exist.

* Queries should ask the Catalog about indexes that exist on relevant columns and use those indexes if they

are available.

Demo your implementation and explain your work in a TA OH to get the extra credit!