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!