Do not post your project on a public GitHub repository.
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
Checkpoint #2 (85 points) — Due Date: Mar 22 @ 11:59pm
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.
Task #1 - B+Tree Pages
You must implement three Page classes to store the data of your B+Tree.
This is a base class that the Internal Page and Leaf Page inherit from, and contains only information that both child classes share. The B+Tree Page has the following fields:
|page_type_||4||Page type (internal or leaf)|
|size_||4||Number of key & value pairs in page|
|max_size_||4||Max number of key & value pairs in page|
You must implement the B+Tree Page by modifying only its header file (src/include/storage/page/b_plus_tree_page.h) and corresponding source file (src/storage/page/b_plus_tree_page.cpp).
B+Tree Internal Page
An Internal Page stores m ordered keys and m+1 child pointers (as page_ids) to other B+Tree Pages. These keys and pointers are internally represented as an array of key/page_id pairs. Because the number of pointers does not equal the number of keys, the first key is set to be invalid, and lookups should always start with the second key.
At any time, each internal page should be at least half full. During deletion, two half-full pages can be merged, or keys and pointers can be redistributed to avoid merging. During insertion, one full page can be split into two, or keys and pointers can be redistributed to avoid splitting. These are examples of the many design choices that you will make while implementing your B+ Tree.
You must implement the Internal Page by modifying only its header file (src/include/storage/page/b_plus_tree_internal_page.h) and corresponding source file (src/storage/page/b_plus_tree_internal_page.cpp).
B+Tree Leaf Page
The Leaf Page stores m ordered keys and their m corresponding values. In your implementation, the value should always be the 64-bit record_id for where the actual tuples are stored; see the
RID class, in src/include/common/rid.h. Leaf pages have the same restrictions on the number of key/value pairs as Internal pages, and should follow the same operations for merging, splitting, and redistributing keys.
You must implement your Leaf Page by modifying only its header file (src/include/storage/page/b_plus_tree_leaf_page.h) and corresponding source file (src/storage/page/b_plus_tree_leaf_page.cpp).
Note: Even though Leaf Pages and Internal Pages contain the same type of key, they may have different value types. Thus, the
max_size can be different.
Each B+Tree leaf/internal page corresponds to the content (i.e., the
data_ part) of a memory page fetched by the buffer pool. Every time you read or write a leaf or internal page, you must first fetch the page from the buffer pool (using its unique
reinterpret cast it to either a leaf or an internal page, and unpin the page after reading or writing it.
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
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
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_ASSERTto 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
- To unlock the header page, simply set
std::nullopt. To unlock other pages, pop from the
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
GenericKeyvaries, 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
KeyTypeinstances are less than, greater than, or equal to each other. These will be included in the
Note: Our B+Tree functions also take a
Transaction* with default value
nullptr. This is intended for project 4 if you want to implement
concurrent index lookup in concurrency control. You generally don't need to use it in this project.
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.
BPlusTree also must correctly implement
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
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.
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 IteratorsThe section on Task 3 describes the implementation of an iterator for the B+Tree.
Concurrent IndicesThe 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
BasicPageGuardto 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
newto 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_sizeafter insertion, and split an internal node when number of values reaches
max_sizebefore insertion. This will ensure that an insertion to a leaf node will never cause a page data overflow when you do something like
InsertIntoLeafand 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.
- We do not test your iterator for thread-safe leaf scans. A correct implementation, however, would require the Leaf Page to throw a
std::exceptionwhen 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
- 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.
See the Project #0 instructions on how to create your private repository and setup your development environment.
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:
You must pass the following tests for Checkpoint #2:
You can test individual components of this project using our testing framework. We use GTest for unit test cases.
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.
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:
- Dump the content to http://dreampuf.github.io/GraphvizOnline/.
- Or download a command line tool at https://graphviz.org/download/ on your platform.
- 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=3tells 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.
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
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.
Execute the following commands to check your syntax. The
format target will automatically correct your code. The
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
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= ..
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
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
Post all of your questions about this project on Piazza. Do not email the TAs directly with questions.
Each project submission will be graded based on the following criteria:
- Does the submission successfully execute all of the test cases and produce the correct answer?
- Does the submission execute without any memory leaks?
- 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.
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.