Home Data Structures and Algorithms with C++ B-Trees in C++

Lesson 16 of 48

In Progress

← Previous Next→

B-Trees in C++

Yasin Cakal

B-Trees are a type of self-balancing tree data structure that can store large amounts of data and allow for efficient retrieval, insertion, and deletion. B-Trees are particularly useful for situations where access times for large amounts of data need to be kept to a minimum. In this article, we will explore how B-Trees work and the time and space complexities associated with their operations. We will also learn how to implement a B-Tree in C++ and provide some coding exercises to test the reader’s understanding of the material.

What is a B-Tree?

A B-Tree is a self-balancing tree data structure that offers efficient retrieval, insertion, and deletion operations. It is characterized by the following properties:

All internal nodes have two or more children.
All leaf nodes are at the same depth.
All keys in the nodes are arranged in increasing order.

The root node of a B-Tree can have any number of children, while each other node must have a minimum number of children (typically two). This minimum number of children is known as the order of the B-Tree. The order of a B-Tree is usually denoted by the letter “m”.

The number of keys that a node can contain is equal to the order of the tree minus one. For example, if the order of a B-Tree is 3, then each node can contain up to two keys. This is known as the node’s capacity.

Time Complexity

When it comes to time complexity, B-Trees offer the following performance metrics:

Access: O(log n)
Search: O(log n)
Insertion: O(log n)
Deletion: O(log n)

These metrics are based on the average case, but in the worst case, the time complexity for all operations is O(n).

Space Complexity

The space complexity of a B-Tree is equal to O(n), which is the worst-case scenario. This means that the B-Tree will take up more space than a regular binary tree.

Implementing a B-Tree in C++

Now that we have a basic understanding of how a B-Tree works, let’s look at how to implement one in C++. The most important aspect of a B-Tree is the node structure. Each node contains a list of keys and a list of pointers to other nodes.

struct Node {
    int* keys; // Array of keys 
    Node** pointers; // Array of pointers to other nodes
};

We can then create a B-Tree class that will contain the root node and any other necessary information.

class B_Tree {
private:
    Node* root;
    int order; // The order of the B-Tree

public:
    B_Tree(int order); 
    void insert(int key); 
    void remove(int key); 
    Node* search(int key); 
};

The constructor for the B-Tree class will take the order of the B-Tree as a parameter and initialize the root node to null.

B_Tree::B_Tree(int order) {
    this->order = order;
    this->root = nullptr;
}

The insert() method is used to add a new key to the B-Tree. We can implement this method by first checking if the root node is null. If it is, then we can create a new root node with the given key. Otherwise, we need to traverse the tree to find the appropriate place for the new key.

void B_Tree::insert(int key) {
    // If the root is null, create a new root node
    if (this->root == nullptr) {
        this->root = new Node();
        this->root->keys = new int[this->order - 1];
        this->root->pointers = new Node*[this->order];
        this->root->keys[0] = key;
        this->root->pointers[0] = nullptr;
    }
    // Otherwise, traverse the tree to find the appropriate place for the new key
    else {
        // Traverse the tree
    }
}

The remove() method is used to remove a key from the B-Tree. This can be done by first searching for the key and then deleting it from the node.

void B_Tree::remove(int key) {
    // Search for the key in the tree
    Node* node = search(key);
    if (node == nullptr) {
        return;
    }
    // Delete the key from the node
    // Code omitted for brevity
}

The search() method is used to search for a key in the B-Tree. This can be done by traversing the tree and comparing the keys in each node to the searched key.

Node* B_Tree::search(int key) {
    // If the root is null, return null
    if (this->root == nullptr) {
        return nullptr;
    }
    // Otherwise, traverse the tree
    else {
        // Traverse the tree
    }
}

Conclusion

In this article, we have explored the B-Tree data structure and how to implement it in C++. We have learned about the time and space complexities associated with its operations and how to use them to efficiently store and retrieve large amounts of data. With this knowledge, we can now start using B-Trees in our data structures and algorithms with C++.

Exercises

Create a function that takes in a B-Tree and prints out all its elements in order.

void printTree(B_Tree* tree) {
    // If the root is null, return
    if (tree->root == nullptr) {
        return;
    }
    // Otherwise, traverse the tree and print out the elements
    else {
        traverseTree(tree->root);
    }
}

void traverseTree(Node* node) {
    int numKeys = node->order - 1;
    
    // Print out the keys
    for (int i = 0; i < numKeys; i++) {
        cout << node->keys[i] << " ";
    }
    
    // Traverse the subtrees
    for (int i = 0; i < node->order; i++) {
        if (node->pointers[i] != nullptr) {
            traverseTree(node->pointers[i]);
        }
    }
}

Create a function that takes in a B-Tree and a key, and returns the node containing the key.

Node* searchTree(B_Tree* tree, int key) {
    // If the root is null, return null
    if (tree->root == nullptr) {
        return nullptr;
    }
    // Otherwise, traverse the tree
    else {
        return traverseTree(tree->root, key);
    }
}

Node* traverseTree(Node* node, int key) {
    int numKeys = node->order - 1;
    
    // Check if the key is in the current node
    for (int i = 0; i < numKeys; i++) {
        if (node->keys[i] == key) {
            return node;
        }
    }
    
    // Traverse the subtrees
    for (int i = 0; i < node->order; i++) {
        if (node->pointers[i] != nullptr) {
            Node* result = traverseTree(node->pointers[i], key);
            if (result != nullptr) {
                return result;
            }
        }
    }
    
    // Return null if the key is not found
    return nullptr;
}

Create a function that takes in a B-Tree and a key, and returns the node containing the key or its closest ancestor.

Node* searchTree(B_Tree* tree, int key) {
    // If the root is null, return null
    if (tree->root == nullptr) {
        return nullptr;
    }
    // Otherwise, traverse the tree
    else {
        return traverseTree(tree->root, key);
    }
}

Node* traverseTree(Node* node, int key) {
    int numKeys = node->order - 1;
    Node* closestAncestor = node;
    
    // Check if the key is in the current node
    for (int i = 0; i < numKeys; i++) {
        if (node->keys[i] == key) {
            return node;
        }
        else if (node->keys[i] > key) {
            closestAncestor = node;
            break;
        }
    }
    
    // Traverse the subtrees
    for (int i = 0; i < node->order; i++) {
        if (node->pointers[i] != nullptr) {
            Node* result = traverseTree(node->pointers[i], key);
            if (result != nullptr) {
                return result;
            }
        }
    }
    
    // Return the closest ancestor if the key is not found
    return closestAncestor;
}

Create a function that takes in a B-Tree and two keys, and returns the node containing the lowest common ancestor of the two keys.

Node* commonAncestor(B_Tree* tree, int key1, int key2) {
    // If the root is null, return null
    if (tree->root == nullptr) {
        return nullptr;
    }
    // Otherwise, traverse the tree
    else {
        return traverseTree(tree->root, key1, key2);
    }
}

Node* traverseTree(Node* node, int key1, int key2) {
    int numKeys = node->order - 1;
    Node* ancestor = nullptr;
    
    // Check if the keys are in the current node
    for (int i = 0; i < numKeys; i++) {
        if (node->keys[i] == key1 || node->keys[i] == key2) {
            if (ancestor == nullptr) {
                ancestor = node;
            }
            else {
                return ancestor;
            }
        }
    }
    
    // Traverse the subtrees
    for (int i = 0; i < node->order; i++) {
        if (node->pointers[i] != nullptr) {
            Node* result = traverseTree(node->pointers[i], key1, key2);
            if (result != nullptr) {
                return result;
            }
        }
    }
    
    // Return the ancestor if it was found
    return ancestor;
}

Create a function that takes in a B-Tree and a key, and returns the node containing the predecessor of the key.

Node* predecessor(B_Tree* tree, int key) {
    // If the root is null, return null
    if (tree->root == nullptr) {
        return nullptr;
    }
    // Otherwise, traverse the tree
    else {
        return traverseTree(tree->root, key);
    }
}

Node* traverseTree(Node* node, int key) {
    int numKeys = node->order - 1;
    Node* predecessor = nullptr;
    
    // Check if the key is in the current node
    for (int i = 0; i < numKeys; i++) {
        if (node->keys[i] == key) {
            // Check if there is a predecessor in the current node
            if (i > 0) {
                return node->pointers[i - 1];
            }
            // Otherwise, return the predecessor from the parent
            else {
                return predecessor;
            }
        }
        else if (node->keys[i] > key) {
            predecessor = node;
            break;
        }
    }
    
    // Traverse the subtrees
    for (int i = 0; i < node->order; i++) {
        if (node->pointers[i] != nullptr) {
            Node* result = traverseTree(node->pointers[i], key);
            if (result != nullptr) {
                return result;
            }
        }
    }
    
    // Return null if the key is not found
    return nullptr;
}

Data Structures and Algorithms with C++

Participants 445