Lab 3: B+ Tree Index

Due by 11:59 p.m., Sunday, November 18, 2018.

This is a partnered lab. You are to complete this lab with one other person, who must attend the same lab as you. You may discuss the lab concepts with other classmates. Please use Teammaker to set your lab partner preferences. You can choose “Random” if you do not have a partner. Remember the Academic Integrity Policy: do not show your code/solution to anyone outside of the course staff and your lab partner. Do not look at any other group’s code/solution for this lab (current or past). If you need help, please post on Piazza.

• Introduction
  • Getting Started
• I/O Layer: Updated Interface for Files and Pages
  • FileScanner Class
• A B+ Tree Index
  • Constructor
  • Insert
  • Range Search Methods
  • Destructor and Print Methods
• Tips and Additional Details
• Testing and Design
• Submitting your lab

Checkpoint 1 (Week 9) - demonstrate that your program can:

• construct a B+Tree
• print the B+Tree
• insert a few items sans splitting (pass test0 in non-debug mode).
• develop and pass a test to insert items in non-sorted order

Checkpoint 2 (Week 10) - demonstrate that your program can:

• Perform a leaf split, properly re-distributing keys with both sorted and unsorted tests. You should show me the resulting tree prints out correctly.
• Perform a search on this tree. You can do this by running test1() in non-debug mode.
• Alternatively, you can show me that you can split the root node properly (~80 inserts in debug mode). I recommend doing search first, though.

Introduction

A key distinction in data structures designed for database management systems is the fact that data (i.e., relations) are stored in files on secondary storage (usually 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.

A DBMS index is a structure to access a relation quickly. For this assignment, you will implement a B+ Tree index that will store data entries in the form of [key, rid] pairs (i.e., Alternative 2 from the course textbook). 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. You will implement a B+ tree, including the full search and insert algorithms as discussed in class. Insert must be capable of dealing with overflows (at any level of the B+ tree) by splitting pages (no redistribution will be done). The goals of this assignment include:

• Understanding and implementing a B+ tree
• Constructing an index on an existing file (relation)
• Organizing a variety of file/page types as containers for objects
• Developing a testing strategy for a large, intricate system
• Implement relation operations including scan, search (equality and range) and insert

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 it just a week before the deadline.

Getting Started

The goal of the WiscDB projects is to allow students to learn about the internals of a data processing engine. In the first assignment, you built a buffer manager. 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.

You will notice a few differences from previous labs. Records were simply strings, often with arbitrary values. In this lab, they encode actual tuples from a relation. In addition, instead of a Heap Page, 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.

cd ~/cs44/labs
git clone [the ssh url to your your repo]
cd Lab3-userID1-userID2

cd ~cs44/Lab3-userID1-userID2/
make setup

I/O Layer: Updated Interface for Files and Pages

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 is the same implementation as the File class in the previous two WiscDB labs i.e., a linked list of heap pages. We use the PageFile class to store all the relations.
• The RawFile class, as the name hints at, provides a file with minimal structure (none, actually) for pages. Specifically, the RawFile treats pages as completely unformatted chunks of memory (e.g., 8KB). You will use the RawFile class to store the B+ index file, where every page in the file is a node from the B+ tree you have complete control in formatting (similar to the data array in Lab 2).

FileScanner Class

The FileScanner class is used to scan records in a file. You 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& name, BufferManager *bufferMgr)
  The constructor takes the relation name and BufferManager instance as parameters. This loads the file and automatically interfaces with the BufferManager.
• ~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()
  Where as scanNext() returns a RecordId, this method returns the actual tuple from the most recent call to scanNext().
• 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 method for this assignment.

Be sure to examine/understand this function for using the FileScanner. You will need to use the FileScanner in your B+ tree construction.

A B+ Tree Index

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

• All records in a file are strings and have the same length.
• The B+ tree only needs to support single-attribute indexing (no composite keys).
• The data type for keys will be limited to strings (c-strings to be precise).
• String keys will undergo pre-fix compression: they are limited to the first 10 characters (this is defined using STRINGSIZE in btree.h).
• 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 previously described 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 (see below). Recall that RawFile gives unformatted Page objects , so you will need to map the various types of data (i.e., leaf node, internal node, header page) into a raw unformatted page (an unstructured array of bytes).

To start, examine the public interface of the BTreeIndex. You can (and should!) add new private methods to this class for e.g., helper functions and good modular design. But do not modify the public interfaces or add data members.

Constructor

• BTreeIndex(...)
  There are two scenarios to handle: (1) you are creating a new index from scratch or (2) you are loading a previously initialized index from file. You can use the RawFile constructor and either of its exceptions to decide which scenario is correct.

  RawFile* openFile;
  try{
    openFile = new RawFile(indexName, true); //true means create file
    //succeeds if the file did not exist
  } catch (FileExistsException){ //create failed because the file exists
    //load index
    openFile = new RawFile(indexName, false); //false means open file
  }
  

  First, let us define the parameters:

  • relationName - The file name of the relation on which to build the index (this is not the same as the name of the index file). If the index is being constructed from scratch, you will need to load the relation (using FileScanner) and insert an entry for each tuples in the relation into the index.

  • bufMgrIn - A pointer to the BufferManager. You will need to store this pointer as a data member load pages into the buffer pool from disk (e.g., when inserting or searching).

  • attrByteOffset - The offset, in bytes, of the attribute for which the index is being built for (i.e., the key). You’ll need this to extract keys out of records.

  • outIndexName - returns the name of the index file.
    An index file name is constructed by concatenating the relational name with the offset of the attribute over which the index is built ("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
    

    If relationName is "relFile" and the attrByteOffset is 0 (the key is the first field), your indexName is "relFile.0".

  Regardless of whether you are loading or creating the index, you should initialize all relevant data members. Many get the same setting in both scenarios. For the scan variables, you can leave them uninitialized except scanExecuting which needs to be false.

  If the file does not exist, you will need to create it and construct the index.

  • Allocated a header page from the BufferManager. You will need to map the struct IndexMetaInfo onto this page to store information (see the struct definition in btree.h). Be sure to unpin the header and mark it dirty when done. Note that there is some redundancy between the header page and the data members; this is necessary to make sure the file on disk knows what the settings were when it was created.
  • Allocate a page for the root. There is not much to add to the root page yet (just set the level), but you do need to store its page number in the header page and rootPageNum data member. All read/allocated pages are done through the BufferManager, so, as with the header, you will need to unpin the page when done and mark it dirty if you modified it.
  • Using the FileScanner class , open up the relation file (relationName), scan all records, and insert them into your B+ tree. You’ll need to extract the key (hint: use attrByteOffset, the STRINGSIZE prefix limit, and strncpy). I highly recommend making this it’s own method; use insertEntry() to do the tree insert.

  If the index file exists, you will follow a similar outline that reads the header/root page (instead of creating them); you also won’t need to do the inserts.

  • The headerPageNum will always be 1, so hard code that in.
  • Read the header page in, and store update data members based on the header page contents (e.g., rootPageNum).
  • Verify that the function’s parameters match the meta-data in the loaded index (e.g., relation name, attribute offset, etc.). If they do not, throw a BadIndexInfoException.

Insert

• const void insertEntry(const char* key, const RecordId rid)
  Inserts a new data entry (i.e., key-rid pair). You can utilize the struct RIDKeyPair to pair up the parameters e.g.,

  RIDKeyPair keyrid;
  keyrid.set(rid,key);
  

  This method will primarily rely on insertInSubtree to do the work; you may need to resolve a split root if insertInSubtree returns a that a split occurred. Note that at some point in your code, you should handle the special case that you are inserting for the first time. Your constructor could either initialize the three with two empty leaf nodes, or you could do that here.

• bool insertInSubtree(RIDKeyPair krid, PageId pageNum, PageKeyPair& splitKey)
  Helper method for insertEntry for non-leaf nodes.
  The method returns true if this node split and returns the key and page number to insert into the parent using the splitKey reference parameter. Similar to the RIDKeyPair, you can store key-pointer (PageId) pairs for storing in internal nodes using the struct PageKeyPair. This method should perform:
  • Search: open the non-leaf node page and follow the correct PageId pointer to descend down the tree. If the layer below is also internal nodes, you will call insertInSubtree with the child PageId value. If the child is a leaf, you will instead call insertInLeaf.
  • Insert new key: If the child node split, you must handle this event by inserting the new key-pageid pair into this node.
  • Split: in the event that there is no space for the new key, you will need to split this node, distribute keys, and push up the middle key to the parent node. You should follow the algorithm presented in class for splitting overflowing leaves and nodes. Do not implement sibling redistribution. For keys, only store the prefix. You can use strncpy to accomplish this:

   strncpy(dest, src, STRINGSIZE);
  

• bool insertInLeaf(RIDKeyPair krid, PageId pageNum, PageKeyPair& splitKey)
  Similar to the above, except there are no recursive calls. You also need to maintain a pointer to the next leaf node.

Range Search Methods

• const void startScan(const char* lowVal, const Operator lowOp, const char* highVal, const Operator highOp)
  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" (a range query). The operators are an enumerated type to make it easier to define which operator to use (see line 34 in btree.h). lowVal and highVal are c-strings to compare your keys against. Recall that you should only use a fixed prefix of strings (the first STRINGSIZE characters) for key comparisons in internal nodes.
  You can use strncmp to compare just the prefix. Be sure to set all data members related to scanning (see line 203 in btree.h).

  • This method does not return any values; you will need to use scanNext() to obtain the results one-by-one.
  • Check to see if there is already a scan in progress - if so, first end that scan before initializing a new one (use endScan() to do this).
  • Throw a BadScanrangeException if the user provides a low value greater than the high value
  • Throw a BadOpcodesException if the lowOp or highOp are not legal (the lowOp must be either GT or GTE; LT or LTE for highOp).
  • The function should “point to” the first matching record when it is complete. Use data members nextEntry and currentPageNum/currentPageData to keep track of the current match and use helper methods findInSubtree and findInLeaf to find the first match.
  • If no such record exists (i.e., no keys match the search criteria) throw an NoSuchKeyFoundException (this will probably be in findLeaf).
• const void scanNext(RecordId& outRid);
  After initializing a scan using startScan(), this method returns the RecordId of the next matching record for the search through the outRid parameter.
  • At any point in time, your class data is actually pointing to the next available record to retrieve (startScan() sets up the pointers this way). So, scanNext() actually retrieves the record currently being pointed to, and then advances the pointer for the next call.
  • Throw a ScanNotInitializedException if there is no current scan in process
  • If there is nothing to return, you should throw an IndexScanCompletedException.
  • Be sure to keep any leaf page that is currently being scanned pinned between searches - the page is still in use.
  • Each leaf page has a next sibling pointer to help continue the scan between leaves.

• const void 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.

• void findInSubtree(PageId currPid) and void findInLeaf(PageId currPid)
  Helper methods to find the first key in the range search (i.e., lowVal). These methods are only called the beginning of a scan. They follow a similar structure as your insert helper methods, except they are simpler (they do not need to handle splits or inserts). The end result of these calls is that the search is initialized and ready to return the first matching record. You should probably have findInLeaf() throw the NoSuchKeyFoundException for startScan(). Note that when you arrive in a leaf, the first key in the range may actually be in the sibling leaf to the right. This is because you are doing a range search - equality would put you in a certain leaf, but the first value in the range may be greater than this value and thus in the node to the right.

Destructor and Print Methods

• ~BTreeIndex(...)
  Performs any cleanup that may be necessary.
  • Unpin any B+ tree pages that are pinned (this should just involve ending a scan if it is still executing)
  • Flushing the index file (by calling bufferManager->flushFile()).
  • Deallocate any data members allocated in this class (i.e., file)

  This method should not delete the index file itself.

• printTree()
  This method is purely for debugging purposes. You should start out by implementing this method so that you can use it to print the contents of your B+ tree. You will probably want to use the recursive helper method to traverse the tree.

Tips and Additional Details

Here is some additional information to help complete the lab:

• Implement BTreeIndex::printTree early and use it to help you with debugging. It is for your own debugging, so what you print and how you print it out is up to you.

• Initial B+Tree inserts - start by implementing an empty B+ Tree, and then try to insert one record. An empty B+ Tree will have 2 pages: a header page, one empty index page for the root node. On the first record insert, the B+Tree will have 4 pages: the header page, the root node index page, and and two pages for the first two leaf nodes. The first record insert will add the first entry to the root index (a key value of the record being inserted, and TWO pointer (PageId) values to the two leaf pages). The first record will be inserted into the right leaf page, the left will be empty. Note: these are the only two leaf pages whose number of records can ever be lower than d (less than 50% full).

• Study tests in main.cpp - Examine the test code in main.cpp that creates and inserts elements into a BTreeIndex. This will help you determine how to write your own test code, but also give you an example of how the BTreeIndex and FileScanner interfaces are used.

• 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. You will need to map three types of pages: a header page (struct IndexMetaInfo), non-leaf nodes (struct NonLeafNode), and leaf nodes (struct LeafNode)

• 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 (i.e., level=1 for the lowest non-leaf layer). 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).

• BufferManager - One of the more important aspects to your implementation is the use of the BufferManager. Any time you allocate/read/write a page through the from disk, you will be using the buffer manager to do so. That is, you should never be doing this directly through the File interface. Also, 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.

• 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 the model in class, only store a forward pointer on leaf pages i.e., a single-linked list.

• Exceptions - As you recall from Lab 1, the BufferManager could throw exceptions e.g., if there are no frames available to allocate. You do not need to handle these exceptions. However, if your code is consistently triggering an exception, it means you have a bug in how the B+ tree is using the BufferManager. Do not catch the exception; figure out what is wrong with your B+ tree and fix it. You can assume the BufferManager will have enough space to handle the basic needs of the B+ tree.

• 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.

Testing and Design

A large part of your time on this lab will be spent designing and testing your program. When designing your solution, be sure to consider that there 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 make debug during development. Nodes will store only 8 keys. This means splits happen after just a few inserts (as opposed to hundreds of inserts). In testing be sure to also use the normal setup (make main) that does full node utilization.
• 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.

Submitting your lab

Before the due date, push your solution to github from one of your local repos to the GitHub remote repo. Only one of you or your partner needs to do this.

From your local repo (in your ~cs44/labs/Lab3-userID1-userID2subdirectory)

make clean
git add *
git commit -m "our correct, robust, and well commented solution for grading"
git push

If that doesn’t work, take a look at the “Troubleshooting” section of the Using Git page. Also, be sure to complete the README.md file, add and push it.