B-Trees & B+ Trees: Page Fanout, Proactive Splitting & Leaf Sibling Chains

CLRS Minimum Degree $t$ Invariants, Proactive Splitting & B-Tree vs B+ Tree

In CLRS notation, a B-Tree of minimum degree $t \ge 2$ (maximum branching factor $M = 2t$) satisfies:

1. Every node except the root holds at least $t - 1$ keys ($t$ children); the root holds at least $1$ key ($2$ children) if non-empty.
2. Every node holds at most $2t - 1$ keys ($2t$ children). A node with $2t - 1$ keys is full.
3. All leaf nodes reside at the exact same depth $h$, bounded by $h \le \log_t \frac{N + 1}{2}$.

Proactive Top-Down Splitting (Single-Pass Insertion): In an on-disk B-Tree, if we waited until reaching a full leaf to split and propagate median keys back up, we would have to hold exclusive write locks (latches) on the entire root-to-leaf path or re-read ancestor pages from disk. Instead, CLRS splits every full node ($2t - 1$ keys) encountered on the way down into two nodes of $t - 1$ keys each, promoting the median key into the parent (which is guaranteed not to be full because we would have already split it on the step above!). This guarantees single-pass top-down insertion and enables latch crabbing (releasing parent locks as soon as the child is verified safe).

Implementation: In-Memory Cache-Aligned B-Tree Node Split (splitChild)

// C++20: Proactive B-Tree Node Split (CLRS Minimum Degree t, Max Keys = 2t - 1)
#include <vector>
#include <algorithm>

template <typename Key, int T = 4> // T=4 => max 7 keys, 8 children per cache-aligned node
struct BTreeNode {
    bool isLeaf = true;
    std::vector<Key> keys;
    std::vector<BTreeNode*> children;

    explicit BTreeNode(bool leaf) : isLeaf(leaf) {
        keys.reserve(2 * T - 1);
        if (!leaf) children.reserve(2 * T);
    }
};

// Splits full child y = parent->children[idx] (which has 2T - 1 keys) into two nodes of T - 1 keys
template <typename Key, int T>
void splitChild(BTreeNode<Key, T>* parent, int idx) {
    BTreeNode<Key, T>* y = parent->children[idx];
    auto* z = new BTreeNode<Key, T>(y->isLeaf);

    Key medianKey = y->keys[T - 1];
    // Move upper T - 1 keys [T .. 2T-2] from y to z
    z->keys.assign(y->keys.begin() + T, y->keys.end());
    y->keys.resize(T - 1);

    // If internal node, move upper T children [T .. 2T-1] from y to z
    if (!y->isLeaf) {
        z->children.assign(y->children.begin() + T, y->children.end());
        y->children.resize(T);
    }

    // Insert medianKey and new right sibling z into parent
    parent->keys.insert(parent->keys.begin() + idx, medianKey);
    parent->children.insert(parent->children.begin() + idx + 1, z);
}