CS 564, Fall 2013 BadgerDB Assignment

1 CS 564, Fall 2013 BadgerDB Assignment #2: B+-­-Tree Index Manager Due Date: October 30, by 2:00PM. No late days. Project Grade Weight: 13% of the total grade Introduction As we discussed in class, relations are stored in files. Each file has a particular organization. Each organization lends itself to efficient evaluation of some (not all) of the following operations: scan, equality search, range search, insertion, and deletion. When it is important to access a relation quickly in more than one way, a good solution is to use an index. For this assignment, the index will store data entries in the form pair. These data entries in the index will be stored in a file that is separate from the data file. In other words, the index file “points to” the data file where the actual records are stored. Two primary kinds of indexes are hash-­-based and tree-­-based, and the most commonly implemented tree-­-based index is the B+-­-Tree. For the second part of the BadgerDB project, you need to implement a B+-­-Tree index. To help get you started, we will provide you with an implementation of few new classes: PageFile, BlobFile, and FileScan. The PageFile and BlobFile classes are derived from the File class. These classes implement a file interface in two different ways. The PageFile class implements the file interface for the File class, as was done in your last buffer manager assignment. Hence, we use the PageFile class to store all the relations as we did in the buffer manager assignment. The BlobFile class implements the file interface for a file organization in which the pages in the file are not linked by prevPage/nextPage links, as they are in the case of the PageFile class. When reading/writing pages, the BlobFile class treats the pages as blobs of 8KB size and hence does not require these pages to be valid objects of the Page class. We will use the BlobFile class to store the B+ index file, where every page in the file is a node from the B+ tree.