Project #2 - B+ Tree Checkpoint 1 Notes
Notes on Checkpoint 1 of the 2nd project of the course 15-445/645 Database Systems, 2020 Fall version.
Introduction
This project is to implement an indexing mechanism for a DBMS using the data structure B+ Tree. The complexity of this project comes from multiple aspects:
- The data structure B+ Tree and associated operations per se.
- The application of B+ Tree in a database, e.g., what do keys, values, and nodes refer to in the context of a database, and how does it work with other parts of a DBMS.
- Some features of C++ that I am not familiar with used for the implementation.
- High-level project description, which requires us to refine the requirements ourselves by referring to the source code, textbook, course slides and notes, etc.
Overview of implementation
We have two types of nodes in a B+ tree: internal and leaf. The following diagrams visualize how the nodes are implemented according to their types.
First, this is the common representation of a B+ tree node:
The way to implement a leaf node:
The way to implement an internal node:
And this is what happens when splitting an internal node:
C++ features
- Templates: for generic programming in C++.
- Explicit instantiation of templates: to allow the template to only work for a couple of explicit types.
- Non-type parameters for templates: we can pass non-type arguments to templates. Non-type parameters are mainly used for specifying max or min values or any other constant value for a particular instance of a template.