B-tree Implementation in C++

A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and search operations. It is widely used in database indexing and file systems due to its ability to maintain balance and minimize disk I/O by storing data in a hierarchical manner.

Program Structure

The C++ implementation of a B-tree will include:

1. B-tree Node Structure: Defining the structure of a B-tree node, including the keys and child pointers.
2. Insertion Operation: Implementing the insertion function to add keys to the B-tree while maintaining its properties.
3. Search Operation: Implementing the search function to find keys in the B-tree.
4. Traversal Operation: Implementing traversal to display the keys in sorted order.

Code Implementation

#include <iostream>
#include <vector>
#include <algorithm>

class BTreeNode {
public:
    std::vector<int> keys;  // Vector to store keys
    std::vector<BTreeNode*> children;  // Vector to store pointers to child nodes
    bool isLeaf;  // Flag to check if the node is a leaf
    int degree;  // Minimum degree (defines the range for number of keys)

    BTreeNode(int degree, bool isLeaf);

    void traverse();

    BTreeNode* search(int key);

    void insertNonFull(int key);

    void splitChild(int i, BTreeNode *y);

    friend class BTree;
};

class BTree {
private:
    BTreeNode *root;
    int degree;

public:
    BTree(int degree) : root(nullptr), degree(degree) {}

    void traverse() {
        if (root != nullptr)
            root->traverse();
    }

    BTreeNode* search(int key) {
        return (root == nullptr) ? nullptr : root->search(key);
    }

    void insert(int key);
};

BTreeNode::BTreeNode(int degree, bool isLeaf) : degree(degree), isLeaf(isLeaf) {
    keys.resize(2 * degree - 1);
    children.resize(2 * degree);
}

void BTreeNode::traverse() {
    int i;
    for (i = 0; i < keys.size(); i++) {
        if (!isLeaf)
            children[i]->traverse();
        std::cout << " " << keys[i];
    }

    if (!isLeaf)
        children[i]->traverse();
}

BTreeNode* BTreeNode::search(int key) {
    int i = 0;
    while (i < keys.size() && key > keys[i])
        i++;

    if (keys[i] == key)
        return this;

    if (isLeaf)
        return nullptr;

    return children[i]->search(key);
}

void BTree::insert(int key) {
    if (root == nullptr) {
        root = new BTreeNode(degree, true);
        root->keys[0] = key;
    } else {
        if (root->keys.size() == 2 * degree - 1) {
            BTreeNode *s = new BTreeNode(degree, false);
            s->children[0] = root;
            s->splitChild(0, root);
            int i = 0;
            if (s->keys[0] < key) i++; s->children[i]->insertNonFull(key);
            root = s;
        } else {
            root->insertNonFull(key);
        }
    }
}

void BTreeNode::insertNonFull(int key) {
    int i = keys.size() - 1;

    if (isLeaf) {
        while (i >= 0 && keys[i] > key) {
            keys[i + 1] = keys[i];
            i--;
        }
        keys[i + 1] = key;
    } else {
        while (i >= 0 && keys[i] > key)
            i--;

        if (children[i + 1]->keys.size() == 2 * degree - 1) {
            splitChild(i + 1, children[i + 1]);

            if (keys[i + 1] < key) i++; } children[i + 1]->insertNonFull(key);
    }
}

void BTreeNode::splitChild(int i, BTreeNode *y) {
    BTreeNode *z = new BTreeNode(y->degree, y->isLeaf);
    z->keys.resize(degree - 1);

    for (int j = 0; j < degree - 1; j++) z->keys[j] = y->keys[j + degree];

    if (!y->isLeaf) {
        for (int j = 0; j < degree; j++) z->children[j] = y->children[j + degree];
    }

    y->keys.resize(degree - 1);

    for (int j = root->keys.size(); j >= i + 1; j--)
        children[j + 1] = children[j];

    children[i + 1] = z;

    for (int j = root->keys.size() - 1; j >= i; j--)
        keys[j + 1] = keys[j];

    keys[i] = y->keys[degree - 1];
}

int main() {
    BTree t(3);

    t.insert(10);
    t.insert(20);
    t.insert(5);
    t.insert(6);
    t.insert(12);
    t.insert(30);
    t.insert(7);
    t.insert(17);

    std::cout << "Traversal of the constructed tree is: ";
    t.traverse();

    int key = 6;
    (t.search(key) != nullptr) ? std::cout << "\nPresent" : std::cout << "\nNot Present";

    key = 15;
    (t.search(key) != nullptr) ? std::cout << "\nPresent" : std::cout << "\nNot Present";

    return 0;
}

Explanation

B-tree Node Structure

The BTreeNode class represents a node in a B-tree. It contains:

• keys: A vector to store the keys in the node.
• children: A vector of pointers to child nodes.
• isLeaf: A boolean flag indicating if the node is a leaf node.
• degree: The minimum degree (t) of the B-tree, which defines the minimum and maximum number of keys a node can have.

Insertion Operation

The insert() function in the BTree class handles the insertion of keys into the B-tree. If the root is full, it creates a new root and splits the old root. The insertNonFull() function is called to handle insertion into non-full nodes. The splitChild() function splits a full child node into two nodes, ensuring that the B-tree properties are maintained.

Search Operation

The search() function in the BTreeNode class searches for a given key in the B-tree. It recursively searches through the nodes until it finds the key or determines that the key is not present.

Traversal Operation

The traverse() function in the BTreeNode class performs an in-order traversal of the B-tree, printing the keys in sorted order. This is useful for verifying the structure and contents of the B-tree.

Conclusion

The B-tree is an essential data structure for database indexing due to its ability to maintain balance and efficiently handle large amounts of data. This C++ implementation provides a basic but functional B-tree that supports insertion, search, and traversal operations, making it a useful tool for managing indexed data in databases.