`

Quick Links

• Introduction
• Getting Started
• I/O layer changes
• FileScanner class
• B+ tree index
• Tips and Additional Details
• Testing and design
• Submitting your lab

This assignment is to be done with a partner. You may not work with other groups, and the share of workload must be even between both partners. Failing to do either is a violation of the department Academic Integrity policy.

A key distinction in data structures designed for database management systems is the fact that data (i.e., relations) are stored in files which reside on disk. In addition to discussing the effect of data structure design, we must also discuss each file type's particular organization and how that organization lends itself to efficient evaluation of typical 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 < key, rid> (Alternative 2 for data entries in terms of index values). The actual tuples are stored in a file separate from the index; entries in the index file "point to" the location of the tuple using a RecordId.

Two primary kinds of indexes are hash-based and tree-based, and the most commonly implemented tree-based index is the B+ tree. In this assignment, you will implement a B+ tree, including the full search and insert algorithms as discussed in class. Your insert routine must be capable of dealing with overflows (at any level of the tree) by splitting pages. The goals of this assignment include:

• Understand and implement a B+ tree
• Constructing an index on an existing file (relation) to improve efficiency
• Organizing a variety of file/page types as containers for objects
• Developing a testing strategy for a large, intricate system
• Implement relation operations including scanning, searching (equality and range), insertion, and deletion

There are number of design choices that you need to make, and you probably need to reserve a big chunk of time for testing and debugging. So, start working on this assignment early; you are unlikely to finish this project if you start is just a week before the deadline.

The goal of the WiscDB projects is to allow students to learn about the internals of a data processing engine. In this first assignment, you will built a buffer manager, on top of an I/O Layer that I provide to understand the management of main memory in a DBMS. In part two, you dove into the I/O Layer to implement a heap page.

In this last part, you will construct a B+ tree class to index relations on disk. In the previous two labs, we simplified the topic of records by not directly dealing with relations. In this lab, records will be more complex. This will require you to navigate a wide-range of concepts including efficiency, relations, indexes, and the use of low-level memory. As such, the depth of design choices and testing strategy will increase significantly. Furthermore, you will re-use many of the constructs from previous labs in your implementation, In particular, you will use (modified) page representations to map nodes on to disk and you will use a buffer manager to manage the interface between your B+ tree and the actual data on disk.

The code base is quite extensive and will require much reading of API documentation and thorough testing. Note: For this lab, I have attempted to directly link all class names to their API documentation. This should make understanding the interface for a class more streamlined for you. You are responsible for making significant progress early on the in assignment as waiting until the last few days will not be manageable.

To get started, run update44 to obtain the starting point files in ~/cs44/labs/5/. You should obtain the following files (files highlighted in blue require modification):

• Makefile - pre-defined. You may edit this file to add extra source files or execution commands.
• btree.h/.cpp - You must edit these files to implement the B+ Tree Index. The header file has been completed for you, and is quite extensive. You should modify it to add necessary private methods but do not modify the public interface.
• fileScanner.h/.cpp - Defines the FileScanner class which iterates over instances of a relation.
• main.cpp - The main testing grounds for this lab. Feel free to add any additional test files as needed.
• README - a few wrap-up questions for you to answer about the lab assignment.

As in previous labs, the following directories are in a shared directory (/home/soni/public/cs44/btree). They are already tied into your make targets and are readable for your reference:

• include/ - contains header files for the Page, File, Page and related classes. These do not need to be modified, but each class must be well understood to manage the interface to the I/O layer. While reading the header files may be helpful, you should start with the online WiscDB documents first.
• lib/ - necessary object files. This directory can be ignored and should not be modified. It provides the object files for all classes related to the buffer manager (i.e., Lab 1 solutions) and I/O layer (i.e., Lab 3 solutions).
• exceptions/ - defines the list of possible exceptions for WiscDB. You will need to reference these exceptions to both handle possible errors that can be thrown to you or that you must throw. Again, it is probably easier to refer to the online documentation.

When you are ready to submit your lab, use handin44. Recall that only files in the ~/cs44/labs/5 subdirectory will be submitted. You may submit as many times as you wish; only the most recent copy will be saved.

To help get you started, I have provided you with an implementation of few new classes: PageFile, RawFile, and FileScanner. The PageFile and RawFile 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 the previous two WisdDB labs - a file consists of pages formatted using the Page class (i.e., a double-linked list of heap pages). We use the PageFile class to store all the relations.

The RawFile class provides an abstraction where there is minimal internal structuring of the data. This allows us to implement our own file organization on top of the RawFile without having our data corrupted in the process. Specifically, the RawFile treats pages as completely unformatted chunks of memory (e.g., 8KB). There is no slot directory or page pointers built in. This allows us to use the page as essentially one large chunk of memory (like the data array from the previous lab). We will use the RawFile class to store the B+ index file, where every page in the file is a node from the B+ tree that we manually format.

The FileScanner class is used to scan records in a file. We will use this class for the base relation, and not for the index file. The file main.cpp file contains code which shows how to use this class. The public member functions of this class are described below.

• FileScanner(const std::string &relationName, BufMgr *bufMgr)
  The constructor takes the relation name and buffer manager instance as parameters. The methods described below are then used to scan the relation.


• ~FileScanner()
  Shuts down the scan and unpins any pinned pages.


• void scanNext(RecordId& outRid)
  Returns (via the outRid parameter) the RecordId of the next record from the relation being scanned. It throws EndOfFileException when the end of relation is reached.


• std::string getRecord()
  Returns the record identified by rid. The rid is obtained by a preceding scanNext() call.


• void markDirty()
  Marks the current page being scanned as dirty, in case the page was being modified. You probably won't need to use this in this assignment.

Your assignment is to implement a B+ tree index. To simplify the task, we will make the following assumptions:

• All records in a file have the same length (so for a given attribute its offset in the record is always the same).
• The B+ tree only needs to support single-attribute indexing (not composite attribute).
• The data type for the index attribute will be limited to strings (c-strings to be precise). While this seems limiting, we can always map a structure into c-strings if, for example, we wanted to instead index ints.
• String keys will undergo pre-fix compression: they are limited to the first 10 characters.
• All keys are unique. That is, you will not need to handle inserting two keys with the same value.

The index will be built directly on top of the I/O Layer (the RawFile and the Page classes). An index will need to store its data in a file on disk, and the file will need a name (so that the DB class can identify it). The convention for naming an index file is specified below. To create a disk image of the index file, you simply use the RawFile constructor with the name of the index file. Since the file is unformatted, you will need to implement a structure on top of the pages that you get from the I/O Layer to represent the nodes of the B+ tree. Furthermore, where the File class abstracted the creation a header page, you will need to directly allocate a page and format it to be the header page (i.e., store meta-data) for your index.

We'll start you off with an interface for a class, BTreeIndex. You will need to implement the methods of this interface as described below. You may add new private methods to this class if needed (hint: it should be), but do not modify the public interfaces that are described here:

• Constructor
  The constructor first checks if the specified index file exists - if it does, simply load the file and the header page which stores the relevant meta-data. You should verify that the parameters match the meta-data in the loaded index (e.g., file name, attribute offset, etc.). If they do not, throw an BadIndexInfoException. If the file does not exist, you will need to create it and construct the index as defined below. To specify this, it is best to examine the role of each parameter:
  • relationName - The name of the relation on which to build the index. If creating a new index, the constructor should scan this relation (using FileScanner) and insert entries for all the tuples in this relation into the index. You can insert an entry one-by-one (i.e., don't worry about bulk-loading. Although that would be one fun extension!).
  • outIndexName - A return value for the name of the file for the index. An index file name is constructed by concatenating the relational name with the offset of the attribute over which the index is built e.g., "relName.attrOffset. If you don't have experience with stringstreams, use the following code:

        std::stringstream ss;
        ss << relationName << '.' << attrByteOffset;
        std::string indexName = ss.str(); // indexName is the name of the index file
    		

  • bufMgrIn - A pointer to the buffer manager. You will need to store this pointer so the index can load pages into the buffer pool from disc.
  • attrByteOffset - The offset, in bytes, of the attribute for which the index is being built for. This defines how to extract the values necessary from the structured tuples.


• Destructor
  Performs any cleanup that may be necessary, including clearing up any state variables, unpinning any B+ tree pages that are pinned, and flushing the index file (by calling bufMgr->flushFile()). Note that this method does not delete the index file itself! It is useful to recall that deletion will call the destructor of File class causing the index file to be closed.


• insertEntry
  Inserts a new data entry (i.e., pair). The parameter key is of type const char*. You should follow the algorithm presented in class e.g., split overflowing leaves and nodes.


• startScan
  This method is used to begin a "filtered" scan of the index. For example, if the method is called using arguments ("a",GT,"d",LTE), the scan should seek all entries greater than "a" and less than or equal to "d". Recall that the operators are an enumerated type to make it easier to define which operator to use. lowValue and highValue are pointers that need to be interpreted as mentioned above. Recall that you should only use a fixed prefix of strings (defined to be 10 in the code) for key comparisons.

  This method does not return any values; you will need to use scanNext to obtain the results one-by-one. You should first check to see if there is already a scan in progress - if so, first end that scan before initializing a new one. You should throw a BadScanrangeException if the user provides a low value greater than the high value and throw a BadOpcodesException if the lowOpParm or highOpParm are not legal (e.g., the lowOpParm must be either GT or GTE). The function should point to the first matching record when it is complete; if no such record exists (i.e., no keys match the search criteria) throw an NoSuchKeyFoundException.



• scanNext
  After initializing a scan using startScan, this method returns the rid of the next matching record for the search through the outRid parameter. You should be maintaining global information about the current search using existing data members for the BTreeIndex. If there is nothing to return, you should throw an IndexScanCompletedException. You should be sure to keep any leaf page that is currently being scanned pinned between searches - logically, the page isn't free until the page is fully scanned or the scan is complete. As discussed in class, each leaf page should have a sibling pointer to help continue the scan between leaves.


• endScan
  Terminates the current scan, unpinning any pages related to the scan. You should throw a ScanNotInitializedException if there is no current scan in process for either this method or scanNext.

Here is some additional information to help complete the lab:

• Using raw Page objects for nodes - Before starting, think closely about how you can use a Page from a RawFile to store node information. See the slides from lab on using Page objects to store LeafNode data


• Setting level value for NonLeafNode - You can use the level value in several different ways. What is most important is that you will need some signal to know whether the next node is going to be a leaf or non-leaf (a consequence of mapping our own structure is that we cannot have C++ check types for us). I suggest using level to store how far a node is from the leaf level. You could also use it to signify whether the next level down is a leaf or not. (e.g., level==0 implies the child Page is a NonLeafNode while level==1 implies the child is LeafNode.


• Buffer Manager - One of the more important aspects to your implementation is the use of the buffer manager. Any time you allocate/read/write a page from disk, you will be using the buffer manager to do so. Be sure you carefully consider when pages no longer need to be used - most pages should be unpinned almost immediately after use, but some pages will be pinned for long durations.


• Special case for first insert - Dealing with the first insert in a B+ tree can be tricky. In particular, you will be creating a leaf node that technically violates the requirement of 50% occupancy. Also, you may create a leaf node that never is inserted into. This is okay for your initial creation (it should not occur again later though). For example, you could use the following strategy: upon the first insert, create a root node with one key k, two empty leaves that get assigned to P[0] for all keys less than k and P[1] for keys greater than or equal to k. By definition the insert of k* will occur in the leaf pointed from P[1]. Note that it is possible that the leaf P[0] may never be used again (we never insert a key less than k)! That is okay for this lab, every other node will comply with the properties of a B+ tree.


• Study btree.h - There are quite a large number of member variables. You should be sure to study the header file before beginning your design since the data member serve as useful global variables for your meta and search data.


• No redistribution on inserts - Do not try to implement (non-splitting) redistribution for insert, it's not fun. You should resolve all full occupancy insertions using splitting.


• Linking leaf pages - As opposed to our model in class, you will only store a forward pointer on leaf pages i.e., a single-linked list.
• Exceptions - In practice, there is the expectation that exceptions thrown from other DBMS components may interrupt the B+ tree and cause an inconsistent state. For example, the buffer manager may through an exception if there are no free frames during your attempt to insert information. This could be a huge source for bugs, but you do not need to concern yourself with these potential bugs. Only exceptions within your own B+ tree implementation should be considered carefully. In other words, you can assume the buffer manager will have plenty of space assuming you handling pinning/unpinning properly.


• Calculating attribute offset - For calculating the attribute offset to send to the BTreeIndex you may want to use the offsetof library. For instance, if we are storing the following structure as a record in the original relation:

    struct RECORD {
      int i;
      double d;
      char s[64];
    };
  	

  And, we are building the index over the double d, then the argument for attrByteOffset is offsetof(RECORD, d). There are examples of this in main.cpp that you can use when constructing new tests.

The majority of your time on this lab will be spent designing and testing your program. When designing your solution, be sure to consider the major hurdles here are two types of nodes - leaf and non-leaf nodes - and each has its own structure. You will need to design several short helper methods for common operations.

You should develop a testing strategy that parallels your design. The provided test is not useful for incremental development. You should devise smaller tests. Ideas include:

• Write a print method that does a traversal of the tree, printing out information stored in each node.
• Create smaller/simple relations that specifically invoke events like splitting.
• Use the DEBUG flag during development in btree.h. When uncommented, nodes will store only 8 keys. This means splits happen after just a few inserts (as opposed to hundreds of inserts).
• Write a short test that creates a B+ tree, closes it, and then attempts to read it back from disk to verify you are saving header information properly. There is a provided test at the end of main.cpp that is a good starting point.
• Search for TODOs in main.cpp for tips on the provided test as well as on ideas for creating new tests.
• Be sure to also test for expected errors (e.g., giving a bad search range).
• The current test inserts keys from smallest to largest in order. That is a poor assumption to make. Be sure to try more "random" orderings.

Submit using handin44. Please run make clean before submitting to keep file sizes down. Also, be sure to complete the README file.