Do not post your project on a public GitHub repository.

Overview

In this programming project you will implement a B+Tree index in your database system. A B+Tree is a balanced search tree in which the internal pages direct the search and leaf pages contain the actual data entries. The index provides fast data retrieval without needing to search every row in a database table, enabling rapid random lookups and efficient scans of ordered records. Your implementation will support thread-safe search, insertion, deletion (including splitting and merging nodes), and an iterator to support in-order leaf scans.

This project has two checkpoint deadlines:

Checkpoint #1 (15 points) — Due Date: Mar 3 @ 11:59pm

• Task #1 - B+Tree Pages
• Task #2a - B+Tree Data Structure (Insertion, Point Search)

Checkpoint #2 (85 points) — Due Date: Mar 22 @ 11:59pm

• Task #2b - B+Tree Data Structure (Deletion)
• Task #3 - Index Iterator
• Task #4 - Concurrency Control

This project must be completed individually (i.e., no groups). Before starting, run git pull public master to pull the latest code from the public BusTub repo.

Remember to pull latest code from the bustub repository.

Your work here depends on your implementation of the buffer pool and page guards from Project 1. If your Project 1 solution was incorrect, you must fix it to successfully complete this project.

We have provided stub classes that define the API you must implement. You should not modify the signatures for these pre-defined functions; if you do, our test code will not work and you will receive little or no credit for the project. Similarly, you should not remove existing member variables from the code we provide. You may add functions and member variables to these classes to implement your solution.

Checkpoint #1

Task #1 - B+Tree Pages

You must implement three Page classes to store the data of your B+Tree.

• B+Tree Page
• B+Tree Internal Page
• B+Tree Leaf Page

Task #2a - B+Tree Insertion and Search for Single Values)

For Checkpoint #1, your B+Tree Index must support insertion (Insert()) and search (GetValue()) for single values. The index should support only unique keys; if you try to reinsert an existing key into the index, it should not perform the insertion, and should return false.

B+Tree pages should be split (or keys should be redistributed) if an insertion would violate the B+Tree's invariants. If an insertion changes the page ID of the root, you must update the root_page_id in the B+Tree index's header page. You can do this by accessing the header_page_id_ page, which is given to you in the constructor. Then, by using reinterpret cast , you can interpret this page as a BPlusTreeHeaderPage (from src/include/storage/page/b_plus_tree_header_page.h) and update the root page ID from there. You also must implement GetRootPageId, which currently returns 0 by default.

We recommend that you use the page guard classes from Project 1 to help prevent synchronization problems. For this checkpoint, we recommend that you use FetchPageBasic (defined in src/include/storage/page/) when you access a page. When you later implement concurrency control in Task 4, you can change this to use FetchPageRead and FetchPageWrite, as needed.

You may optionally use the Context class (defined in src/include/storage/index/b_plus_tree.h) to track the pages that you've read or written (via the read_set_ and write_set_ fields) or to store other metadata that you need to pass into other functions recursively.

If you are using the Context class, here are some tips:

• You might only need to use write_set_ when inserting or deleting. It is possible that you don't need to use read_set_, depending on your implementation.
• You might want to store the root page id in the context and acquire write guard of header page when modifying the B+Tree.
• To find a parent to the current node, look at the back of write_set_. It should contain all nodes along the access path.
• You should use BUSTUB_ASSERT to help you find inconsistent data in your implementation. For example, if you want to split a node (except root), you might want to ensure there is still at least one node in the write_set_. If you need to split root, you might want to check if header_page_ is std::nullopt.
• To unlock the header page, simply set header_page_ to std::nullopt. To unlock other pages, pop from the write_set_ and drop.

The B+Tree is parameterized on arbitrary key, value, and key comparator types. We've defined a macro, INDEX_TEMPLATE_ARGUMENTS, that generates the right template parameter declaration for you:

template <typename KeyType,
          typename ValueType,
          typename KeyComparator>

The type parameters are:

• KeyType: The type of each key in the index. In practice this will be a GenericKey. The actual size of a GenericKey varies, and is specified with its own template argument that depends on the type of indexed attribute.
• ValueType: The type of each value in the index. In practice, this will be a 64-bit RID.
• KeyComparator: A class used to compare whether two KeyType instances are less than, greater than, or equal to each other. These will be included in the KeyType implementation files.

Checkpoint #2

Task #2b - B+Tree Deletions

For Checkpoint #2, your solution also must support deletion of a key (Delete()), including merging or redistributing keys between pages if necessary to maintain the B+Tree invariants. As with insertions, you must correctly update the B+Tree's root page ID if the root changes.

Task #3 - An Iterator for Leaf Scans

After you have implemented and thoroughly tested your B+Tree in Tasks 1 and 2, you must add a C++ iterator that efficiently supports an in-order scan of the data in the leaf pages. The basic idea is store sibling pointers so that you can efficiently traverse the leaf pages, and then implement an iterator that iterates through every key-value pair, in order, in every leaf page.

Your iterator must be implemented as a C++17-style Iterator, including at least the methods:

• isEnd(): Return whether this iterator is pointing at the last key/value pair.
• operator++(): Move to the next key/value pair.
• operator*(): Return the key/value pair this iterator is currently pointing at.
• operator==(): Return whether two iterators are equal
• operator!=(): Return whether two iterators are not equal.

Your BPlusTree also must correctly implement begin() and end() methods, to support C++ for-each loop functionality on the index.

You must implement your index iterator by modifying only its header file (src/include/storage/index/index_iterator.h) and corresponding source file (src/index/storage/index_iterator.cpp).

Task #4 - Concurrent Index

Finally, modify your B+Tree implementation so that it safely supports concurrent operations. You should use the latch crabbing technique described in class and in the textbook. The thread traversing the index should acquire latches on B+Tree pages as necessary to ensure safe concurrent operations, and should release latches on parent pages as soon as it is possible to determine that it is safe to do so.

We recommend that you complete this task by first changing instances of FetchPageBasic to either FetchPageWrite or FetchPageRead, depending on whether you want to access a page with read or write privileges. Then modify your implementation to grab and release read and write latches as necessary to implement the latch crabbing algorithm.

Note: you should never acquire the same read lock twice in a single thread. It might lead to deadlock.

Road Map

There are several ways in which you could go about building a B+Tree Index. This road map serves as only a rough conceptual guideline for building one. This road map is based on the algorithm outlined in the textbook. You could choose to ignore parts of the road map and still end up with a semantically correct B+Tree that passes all our tests. The choice is entirely yours.

• Simple Inserts: Given a key-value pair KV and a non-full node N, insert KV into N. Self check: What are the different types of nodes and can key-values be inserted in all of them?
• Simple Search: Given a key K, define a search mechanism on the tree to determine the presence of the key. Self check: Can keys exist in multiple nodes and are all these keys the same?
• Simple Splits: Given a key K, and a target leaf node L that is full, insert the key into the tree, while keeping the tree consistent. Self check: When do you choose to split a node and how do define a split?
• Multiple Splits: Define inserts for a key K on a leaf node L that is full, whose parent node M is also full. Self check: What happens when the parent of M is also full?
• Simple Deletes: Given a key K and a target leaf node L that is at-least half full, delete K from L. Self check: Is the leaf node L the only node that contains the key K?
• Simple Coalesces: Define deletes for a key K on a leaf node L that is less than half-full after the delete operation. Self check: Is it mandatory to coalesce when L is less than half-full and how do you choose which node to coalesce with?
• Not-So-Simple Coalesces: Define deletes for a key K on a node L that contains no suitable node to coalesce with. Self check: Does coalescing behavior vary depending on the type of nodes? This should take you through to Checkpoint 1
• Index Iterators The section on Task 3 describes the implementation of an iterator for the B+Tree.
• Concurrent Indices The section on Task 4 describes the implementation of the latch crabbing technique to support concurrency in your design.

Requirements and Hints

• You are not allowed to use a global latch to protect your data structure; your implementation must support a reasonable level of concurrency. In other words, you may not latch the whole index and only unlatch when operations are done.
• We recommend that you use the page guard classes ReadPageGuard, WritePageGuard, and BasicPageGuard to implement thread safety for your B+Tree. It's possible to receive full credit on this project using these constructs for thread safety.
• You may add functions to your implementation as long as you keep all our original public interfaces intact for testing purposes.
• Don't use malloc or new to allocate large blocks of memory for your tree. If you need to need to create a new node for your tree or need a buffer for some operation, you should use the buffer pool manager.
• Use binary search to find the place to insert a value when iterating an internal or leaf node. Otherwise, your implementation will probably timeout on Gradescope.
• We recommend (but do not require) that you to follow this rule when implementing split: split a leaf node when the number of values reaches max_size after insertion, and split an internal node when number of values reaches max_size before insertion. This will ensure that an insertion to a leaf node will never cause a page data overflow when you do something like InsertIntoLeaf and then redistribute; it will also prevent an internal node with only one child. However, you indeed can do something like lazily splitting leaf node / handling the case for internal node of only one children. It’s up to you; our test cases do not test for these conditions.

Common Pitfalls

• We do not test your iterator for thread-safe leaf scans. A correct implementation, however, would require the Leaf Page to throw a std::exception when it cannot acquire a latch on its sibling to avoid potential dead-locks.
• If you are implementing a concurrent B+tree index correctly, then every thread will always acquire latches from the header page to the bottom. When you release latches, make sure you release them in the same order (from the header page to the bottom).
• When implementing the page classes (Task 1), make sure you only add class fields of trivially-constructed types (e.g. int). Do not add vectors and do not modify array_.
• You should always acquire the lock of a node's children, even if you have the parent's lock, when inserting. Think of the case where some threads are retrieving values from the leaf page with a read lock, while some other threads are updating the page (e.g., when coalescing). If you don’t hold the lock, there will be a race condition.

Instructions

See the Project #0 instructions on how to create your private repository and setup your development environment.

Checkpoint #1

Update your project source code like you did in Project #1.

You can use the b_plus_tree_printer to check your solution for correct behavior. (There's more info in the Testing section below.)

You must pass the following tests (except iterators) for Checkpoint #1:

• test/storage/b_plus_tree_insert_test.cpp
• test/storage/b_plus_tree_sequential_scale_test.cpp

Checkpoint #2

You must pass the following tests for Checkpoint #2:

• test/storage/b_plus_tree_insert_test.cpp
• test/storage/b_plus_tree_delete_test.cpp
• test/storage/b_plus_tree_sequential_scale_test.cpp
• test/storage/b_plus_tree_concurrent_test.cpp

Testing

You can test individual components of this project using our testing framework. We use GTest for unit test cases. Within tools/b_plus_tree_printer is a tool that you can use to print the internal data structures of your B+Tree. You might find it useful to track and find early mistakes.

You can compile and run each test individually from the command line:

$ mkdir build
$ cd build
$ make b_plus_tree_insert_test -j$(nproc)
$ ./test/b_plus_tree_insert_test

You can also run make check-tests to run ALL of the test cases. Note that some tests are disabled as you have not implemented future projects. You can disable tests in GTest by adding a DISABLED_ prefix to the test name.

Important: These tests are only a subset of the all the tests that we will use to evaluate and grade your project. You should write additional test cases to better test your implementation.

Tree Visualization

Use the b_plus_tree_printer tool to generate a dot file after constructing a tree:

$ # To build the tool
$ mkdir build
$ cd build
$ make b_plus_tree_printer -j$(nproc)
$ ./bin/b_plus_tree_printer
>> ... USAGE ...
>> 5 5 // set leaf node and internal node max size to be 5
>> f input.txt // Insert into the tree with some inserts 
>> g my-tree.dot // output the tree to dot format 
>> q // Quit the test (Or use another terminal) 

You should now have a my-tree.dot file with the DOT file format in the same directory as your test binary, which you can then visualize with a command line visualizer or an online visualizer:

1. Dump the content to http://dreampuf.github.io/GraphvizOnline/.
2. Or download a command line tool at https://graphviz.org/download/ on your platform.
3. Draw the tree with dot -Tpng -O my-tree.dot, a PNG file will be generated.

Consider the following example generated with GraphvizOnline:

• Rectangles in Pink represent internal nodes, those in Green represent leaf nodes.
• The first row P=3 tells you the page id of the tree page.
• The second row prints out the properties.
• The third row prints out keys, and pointers from internal node to the leaf node is constructed from internal node's value.
• Note that the first box of the internal node is empty. This is not a bug.

You can also compare with our reference solution running in your browser.

Contention Benchmark

To ensure you are implementing lock crabbing correctly, we will use a contention benchmark to collect some heuristics from your implementation, and then manually review your code based on the heuristics. The contention ratio is the slowdown when the B+ tree is used in a multi-thread environment, compared to a single-thread environment. The contention ratio generally should be in the range [2.5, 3.5] on Gradescope. A contention ratio less than 2.5 probably means that your lock crabbing is incorrect (e.g, you might be using some global locks or holding locks for an unnecessary long time). A contention ratio greater than 3.5 probably means that the lock contention is too high in your implementation and you are recommended to investigating what is happening.

Your submission must pass contention benchmark without segfault and deadlock. Otherwise you will get zero score for all of the concurrent test cases (which will be deducted manually).

(Optional) Leaderboard Task

See btree_bench.cpp for more information. We have multiple threads concurrently reading and updating the B+ tree.

Your submission must pass leaderboard test without segfault and deadlock but you don't need to optimize for it.

Recommended Optimizations: For deletion, place tombstones in the leaf instead of doing actual deletions. Clean up tombstones in the background or after some thresholds. After that, you can optimistically acquire read locks for all modification operations because trees will split and coalesce less often. Similar techniques are described in the Bε-tree paper.

Formatting

Your code must follow the Google C++ Style Guide. We use Clang to automatically check the quality of your source code. Your project grade will be zero if your submission fails any of these checks.

Execute the following commands to check your syntax. The format target will automatically correct your code. The check-lint and check-clang-tidy-p2 targets will print errors and instruct you how to fix it to conform to our style guide.

$ make format
$ make check-lint
$ make check-clang-tidy-p2

Memory Leaks

For this project, we use LLVM Address Sanitizer (ASAN) and Leak Sanitizer (LSAN) to check for memory errors. To enable ASAN and LSAN, configure CMake in debug mode and run tests as you normally would. If there is memory error, you will see a memory error report. Note that macOS only supports address sanitizer without leak sanitizer.

In some cases, address sanitizer might affect the usability of the debugger. In this case, you might need to disable all sanitizers by configuring the CMake project with:

$ cmake -DCMAKE_BUILD_TYPE=Debug -DBUSTUB_SANITIZER= ..

Development Hints

You can use BUSTUB_ASSERT for assertions in debug mode. Note that the statements within BUSTUB_ASSERT will NOT be executed in release mode. If you have something to assert in all cases, use BUSTUB_ENSURE instead.

We encourage you to use a graphical debugger to debug your project if you are having problems.

If you are having compilation problems, running make clean does not completely reset the compilation process. You will need to delete your build directory and run cmake .. again before you rerun make.

Post all of your questions about this project on Piazza. Do not email the TAs directly with questions.

Grading Rubric

Each project submission will be graded based on the following criteria:

1. Does the submission successfully execute all of the test cases and produce the correct answer?
2. Does the submission execute without any memory leaks?
3. Does the submission follow the code formatting and style policies?

Note that we will use additional test cases to grade your submission that are more complex than the sample test cases that we provide you.

Late Policy

See the late policy in the syllabus. Both checkpoint 1 and checkpoint 2 count for late days.

After completing the assignment, you can submit your implementation of to Gradescope. We have two homework assignments set up for this project -- one for each checkpoint -- and you will need to submit the two checkpoints separately.

You can run make submit-p2 in your build/ directory will generate a zip archive called project2-submission.zip under your project root directory that you can submit to Gradescope. This command will package the files necessary for both checkpoints. You are not expected to have implemented index iterators and concurrency support for checkpoint 1. You will not be graded on this.

cd build
make submit-p2
cd ..
# project2-submission.zip will be generated here. Submit this.

You can submit your answers as many times as you like and get immediate feedback. Your score will be sent via email to your Andrew account within a few minutes after your submission.