How to implement a non-preemptive splitting insert in a B-tree?

Question

I am working on implementing a non-preemptive splitting insert function for a B-tree. Below is the structure of my B-tree node:

#define KEYS_NUMBER     4                   // Max number of keys in a node
#define MIN_KEYS        (KEYS_NUMBER / 2)   // Min number of keys in a node
#define CHILDREN_NUMBER (KEYS_NUMBER + 1)   // Max number of children in a node

typedef struct node {
    bool leaf;
    int n;
    int keys[KEYS_NUMBER];
    struct node *children[CHILDREN_NUMBER];
} Node;

I have the following code for my insertNonFull and insertKey functions:

void insertNonFull(Node *node, int key) {
    int i = node->n - 1;

    if (node->leaf) {
        while (i >= 0 && (key < node->keys[i])) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->n = node->n + 1;
    } else {
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;
        if (node->children[i]->n == KEYS_NUMBER) {
            splitChild(node, i, node->children[i]);
            if (key > node->keys[i]) {
                i++;
            }
        }
        insertNonFull(node->children[i], key);
    }
}

void insertKey(Node **tree, int key) {
    Node *r = *tree;

    if (r->n == KEYS_NUMBER) {
        Node *s = createNode();
        *tree = s;
        s->leaf = false;
        s->n = 0;
        s->children[0] = r;
        splitChild(s, 0, r);
        insertNonFull(s, key);
    } else {
        insertNonFull(r, key);
    }
}

When I add the key 15, the B-tree structure before and after the insertion is as follows:

Before inserting the 15th key:

[3, 6, 9, 12]
    [1, 2]
    [4, 5]
    [7, 8]
    [10, 11]
    [13, 14]

After inserting the 15th key:

[9]
    [3, 6]
        [1, 2]
        [4, 5]
        [7, 8]
    [12]
        [10, 11]
        [13, 14, 15]

We can see that the root node splits prematurely. How can I optimize my insert function to prevent this premature split and achieve the following result instead?

[3, 6, 9, 12]
    [1, 2]
    [4, 5]
    [7, 8]
    [10, 11]
    [13, 14, 15]

Any suggestions on how to adjust my insertNonFull and insertKey functions to achieve this?

Answer 1

Insertion is done at leaf node. If this operation causes the node to be overfull, the node is split into two, with the median element promoted. This cascades up the tree.

As I see it, the literature is very fuzzy on the implementation details, specifically, how does it become "overfull" and how do you do this "promotion". After seeing a lot of B-tree implementations, I can think of 3 approaches.

1. Pre-emptively and greedily split any full nodes on the way down the tree, whether needed it or not. This is a very popular approach because of its simplicity. However, as you have noticed, results in a tree that is non-optimal and slightly unbalanced, (although it becomes less noticeable for high B.)
2. Do the steps literally. Either add a parent pointer (double-linking) and an extra temporary overfull entry to every node to help with the transition (update the pointers every time there is a change in topology) or use temporary space (ie an O(log n) stack of pointers to nodes).
3. We know, almost independently, how each of the nodes split on the inserted key, with the exception of 1 hole that gets filled from the child. This means that we can skip directly to the final topology and do the allocation of new nodes and promotion in any order we like; specifically, down the tree instead of up. This also is advantageous because one moves the memory only once. (However, it is a lot of cases.)

Choosing this last approach, on descent from the root to the leaf, we need to keep track of the lowest height node that is not-full. If the path is entirely full of keys, one requires an increase of height. Then you know exactly how many, O(log n), extra nodes you need to complete the insertion.

For example, adding 9 into full 3-tree, where there is no lowest not-full, requires 4 extra nodes to increase the height. The lowest not-full becomes the new root.

Backtrack to the lowest not-full and re-descend, splitting the data and the hole between existing, full child (child 1) node, one entry from the lowest not-full (parent) node, and the newly-allocated (child 2) node. The hole node should have the new key's value, which it will be eventually replaced.

Now the lowest not-full is the child of the previous along the path to the new key. Repeat.

The hole skipped ahead to exactly where insertion should be if we followed all the steps in the bottom-up B-tree algorithm.

The result is as if one had promoted upwards, but we just skipped the intermediate steps. The animations on this visualization from David Galles helped me a lot with my implementation.