Building My Own Database in C++ — Part 3: Implementing indexes

Table of Contents

• Building a b+ tree

Building a B+ Tree

In the previous sections, we built the storage layer of our database, including the table heap and record identifiers (RIDs). However, retrieving a record still requires scanning the table to find the corresponding key. As the number of records grows, this becomes increasingly expensive.

To improve lookup performance, we can introduce an index. In this section, we will implement an in-memory B+ tree that maps integer keys to RIDs. Instead of scanning every record, the tree directs us towards the leaf node that may contain the key we are looking for.

Our implementation supports inserting unique keys and searching for their corresponding RIDs. We will start with the node structure, then implement insertion and search, before handling node splits and maintaining the tree as it grows.

Understanding the structure of a B+ Tree

A B+ tree consists of two types of nodes. Internal nodes contain separator keys and child pointers, which guide the search towards the correct leaf. Leaf nodes contain the actual keys and their corresponding RIDs.

In our implementation, each node can hold at most max_keys keys before it needs to split. For simplicity, we will use a default maximum of four keys. Internal nodes have one more child pointer than separator keys, while leaf nodes maintain matching numbers of keys and RIDs.

Notice that the internal nodes do not store the actual RIDs in this design. The key-to-RID mapping lives in the leaves. The internal keys are used solely to decide which child to visit during a search.

Defining the node structure

We begin by defining a Node structure inside our BPlusTree class. Each node records whether it is a leaf, its keys, and its relationship with other nodes.

1class BPlusTree
2{
3private:
4    struct Node
5    {
6        explicit Node(bool leaf)
7            : is_leaf(leaf), parent(nullptr), next(nullptr)
8        {
9        }
10
11        bool is_leaf;
12
13        // Keys stored in sorted order.
14        std::vector<int> keys;
15
16        // Leaf nodes: keys[i] maps to values[i].
17        std::vector<RID> values;
18
19        // Internal nodes: one more child than separator keys.
20        std::vector<Node *> children;
21
22        Node *parent;
23        Node *next;
24    };
25};

The values vector is only used by leaf nodes, whereas children is only used by internal nodes. Keeping these vectors separate makes the different responsibilities of each node explicit.

Each node also has a parent pointer, which helps us propagate splits upwards, and a next pointer, which links leaf nodes together for efficient ordered scans.

We will also maintain ownership of all allocated nodes in a vector ofstd::unique_ptr. This keeps the node objects alive while allowing the tree to use ordinaryNode* pointers for parent-child relationships.

1private:
2    std::vector<std::unique_ptr<Node>> nodes_;
3
4    Node *root_;
5    std::size_t max_keys_;
6
7    Node *create_node(bool is_leaf)
8    {
9        nodes_.push_back(std::make_unique<Node>(is_leaf));
10        return nodes_.back().get();
11    }

The constructor initializes an empty tree and sets the maximum number of keys allowed per node. We require at least three keys per node to keep this implementation's splitting behaviour meaningful.

1public:
2    explicit BPlusTree(std::size_t max_keys = 4)
3        : root_(nullptr), max_keys_(max_keys)
4    {
5        if (max_keys < 3)
6        {
7            throw std::invalid_argument(
8                "B+ tree max_keys must be at least 3");
9        }
10    }

Finding the correct leaf

Before implementing insertion and search, we need a way to navigate through the tree. Starting at the root, we examine the separator keys and select the child that could contain the target key. We repeat this process until we reach a leaf.

Our internal-node convention is that keys[i] stores the minimum key in children[i + 1]. Therefore, a separator divides the key ranges of two adjacent children.

We use std::upper_bound to find the first separator strictly greater than the target key. The position of that separator is also the index of the child we should visit. If the target equals a separator, we go to the child on its right.

1Node *find_leaf(int key) const
2{
3    Node *current = root_;
4
5    while (!current->is_leaf)
6    {
7        auto it = std::upper_bound(
8            current->keys.begin(),
9            current->keys.end(),
10            key);
11
12        std::size_t index = static_cast<std::size_t>(
13            std::distance(current->keys.begin(), it));
14
15        current = current->children[index];
16    }
17
18    return current;
19}

For example, given separator keys [20, 40], a search for 12 visits the first child, a search for 30 visits the second child, and a search for 40 visits the third child. The method returns the leaf where the key should be, whether or not the key actually exists.

Implementing search

Once we have located the appropriate leaf, searching is straightforward. Because leaf keys are sorted, std::lower_bound finds the first key that is greater than or equal to the target. If it matches the target, we use its position to retrieve the corresponding RID.

1bool search(int key, RID &rid) const
2{
3    if (root_ == nullptr)
4    {
5        return false;
6    }
7
8    Node *leaf = find_leaf(key);
9
10    auto it = std::lower_bound(
11        leaf->keys.begin(),
12        leaf->keys.end(),
13        key);
14
15    if (it == leaf->keys.end() || *it != key)
16    {
17        return false;
18    }
19
20    std::size_t index = static_cast<std::size_t>(
21        std::distance(leaf->keys.begin(), it));
22
23    rid = leaf->values[index];
24    return true;
25}

Returning a boolean lets the caller distinguish between a successful lookup and a missing key. When the key exists, the function writes the associated RID into the reference passed to it.

Inserting a key into a leaf

Insertion follows the same navigation process. We first find the leaf where the new key belongs, then insert the key and its RID at the same position to preserve their correspondence and keep the keys sorted.

This implementation supports unique keys only. If the key already exists, insertion returns false without replacing the existing RID.

1bool insert(int key, const RID &rid)
2{
3    if (root_ == nullptr)
4    {
5        root_ = create_node(true);
6        root_->keys.push_back(key);
7        root_->values.push_back(rid);
8        return true;
9    }
10
11    Node *leaf = find_leaf(key);
12
13    auto it = std::lower_bound(
14        leaf->keys.begin(),
15        leaf->keys.end(),
16        key);
17
18    std::size_t index = static_cast<std::size_t>(
19        std::distance(leaf->keys.begin(), it));
20
21    if (it != leaf->keys.end() && *it == key)
22    {
23        return false;
24    }
25
26    leaf->keys.insert(it, key);
27    leaf->values.insert(
28        leaf->values.begin() + index,
29        rid);
30
31    if (leaf->keys.size() > max_keys_)
32    {
33        split_leaf(leaf);
34    }
35
36    return true;
37}

A leaf can temporarily contain max_keys + 1 keys after an insertion. When that happens, we split it into two leaves. This is the main mechanism that keeps the tree balanced as more keys are inserted.

Splitting a leaf node

To split a leaf, we divide its sorted keys and RIDs around the midpoint. The left leaf keeps the first half, while a new right leaf receives the remaining entries. We then update the leaf links so that ordered scans can still move through every leaf.

1void split_leaf(Node *leaf)
2{
3    Node *right = create_node(true);
4
5    std::size_t middle = leaf->keys.size() / 2;
6
7    right->keys.assign(
8        leaf->keys.begin() + middle,
9        leaf->keys.end());
10
11    right->values.assign(
12        leaf->values.begin() + middle,
13        leaf->values.end());
14
15    leaf->keys.resize(middle);
16    leaf->values.resize(middle);
17
18    // Insert the new leaf into the linked leaf chain.
19    right->next = leaf->next;
20    leaf->next = right;
21
22    right->parent = leaf->parent;
23
24    insert_into_parent(leaf, right);
25}

Splitting the leaf is only part of the operation. The parent must also learn that the original leaf now has a new right sibling. We delegate this responsibility to insert_into_parent.

Maintaining separator keys

Whenever the children of an internal node change, its separator keys must be updated. Instead of manually calculating each separator during every split, we use a helper to rebuild them from the children.

The min_key helper descends through the leftmost child until it reaches a leaf. The first key in that leaf is the minimum key in the entire subtree.

1int min_key(Node *node) const
2{
3    while (!node->is_leaf)
4    {
5        node = node->children.front();
6    }
7
8    return node->keys.front();
9}

An internal node with children [C0, C1, C2] needs two separator keys: the minimum key in C1 and the minimum key in C2. There is no separator for C0 because it is the leftmost child.

1void rebuild_keys(Node *node)
2{
3    node->keys.clear();
4
5    if (node->is_leaf)
6    {
7        return;
8    }
9
10    for (std::size_t i = 1;
11         i < node->children.size();
12         ++i)
13    {
14        node->keys.push_back(min_key(node->children[i]));
15    }
16}

This helper keeps the relationship between children and separators consistent. It also makes the splitting logic easier to understand, because we can rearrange child pointers first and then reconstruct the separator keys.

Inserting a split node into its parent

After a leaf splits, we insert the new right sibling immediately after the original leaf in the parent's child vector. We then rebuild the parent's separator keys.

There are two cases to handle. If the split node was the root, we create a new internal root with the two resulting nodes as its children. Otherwise, we insert the right sibling into the existing parent.

1void insert_into_parent(Node *left, Node *right)
2{
3    if (left->parent == nullptr)
4    {
5        Node *new_root = create_node(false);
6
7        new_root->children.push_back(left);
8        new_root->children.push_back(right);
9
10        left->parent = new_root;
11        right->parent = new_root;
12
13        rebuild_keys(new_root);
14        root_ = new_root;
15        return;
16    }
17
18    Node *parent = left->parent;
19
20    auto it = std::find(
21        parent->children.begin(),
22        parent->children.end(),
23        left);
24
25    std::size_t index = static_cast<std::size_t>(
26        std::distance(parent->children.begin(), it));
27
28    parent->children.insert(
29        parent->children.begin() + index + 1,
30        right);
31
32    right->parent = parent;
33
34    rebuild_keys(parent);
35
36    if (parent->keys.size() > max_keys_)
37    {
38        split_internal(parent);
39    }
40}

Notice that inserting a sibling can cause the parent itself to overflow. If that happens, we must split the internal node as well. This is why the process can propagate from a leaf towards the root.

Splitting an internal node

Splitting an internal node differs from splitting a leaf. Internal nodes store child pointers rather than record RIDs, so we divide the children into two groups. The right half is moved into a new internal node, and each moved child's parent pointer must be updated.

1void split_internal(Node *node)
2{
3    Node *right = create_node(false);
4
5    std::size_t middle = node->children.size() / 2;
6
7    right->children.assign(
8        node->children.begin() + middle,
9        node->children.end());
10
11    node->children.resize(middle);
12
13    for (Node *child : right->children)
14    {
15        child->parent = right;
16    }
17
18    right->parent = node->parent;
19
20    rebuild_keys(node);
21    rebuild_keys(right);
22
23    // The parent may overflow too, so splitting can propagate upwards.
24    insert_into_parent(node, right);
25}

Once the child pointers have been redistributed, we rebuild the separator keys for both internal nodes. We then insert the new right node into the parent using the same helper as before. If the original node was the root, this creates a new root; otherwise, the split may continue upwards.

Putting it all together

We now have the core operations needed for an in-memory B+ tree: navigating to a leaf, searching for a key, inserting a key and RID, rebuilding separator keys, and splitting overflowing nodes.

The key idea is that every split preserves the ordering of the keys and updates the parent-child relationships. Leaf splits also maintain the linked list used for ordered scans. Internal splits can propagate upwards until the tree has enough room or a new root is created.

This implementation is an in-memory index: it does not yet persist tree nodes to disk or integrate the index with the buffer pool. Those would be natural next steps when extending the database engine.