B+ Tree Logic (C++)

← Back to Visualizer
// B+ Tree Node Structure
struct Node {
    bool isLeaf;
    int *keys;
    Node **children;
    int size; // Current number of keys
};

// Splitting a Full Node
void splitNode(Node *parent, int i, Node *child) {
    Node *newNode = new Node(child->isLeaf);
    int mid = T - 1; // T is the degree

    // Move keys to new node
    for (int j = 0; j < mid; j++)
        newNode->keys[j] = child->keys[j + T];

    // Move children if not leaf
    if (!child->isLeaf) {
        for (int j = 0; j < T; j++)
            newNode->children[j] = child->children[j + T];
    }
    // ... Promote mid key to parent
}

1. Leaf Split

When a leaf overflows, it splits into two. The first key of the new leaf is copied (not moved) to the parent to act as an index.

2. Internal Split

When an internal node overflows, the middle key is pushed up to the parent, and the node is divided.

3. Linked Leaves

B+ Trees maintain a pointer from one leaf to the next, enabling fast sequential access (Range Queries).

4. Fan-out

Because internal nodes only store keys (no data), B+ Trees have a high fan-out, reducing tree height significantly.