B+ Tree Insertion Demo — order n=3 (leaf cap 3, internal cap 4 pointers). Splits: leaf 2|2, internal 3|2

Root Internal Leaf (records)
Insert up to key:
Current height: 1

    STRUCT Node:
    bool leaf
    keys[]          // leaf: record keys; internal: separator keys
    children[]      // only for internal nodes
    parent

FUNCTION INSERT(tree, k):
    L ← FIND_LEAF(tree.root, k)
    INSERT_IN_LEAF(L, k)
    IF |L.keys| ≤ 3: return
    SPLIT_LEAF(L)               // may cascade up

FUNCTION FIND_LEAF(x, k):
    WHILE x is internal:
        // choose smallest i with k < x.keys[i]; else take last child
        i ← LOWER_BOUND(x.keys, k)
        x ← x.children[i]
    RETURN x

FUNCTION INSERT_IN_LEAF(L, k):
    i ← LOWER_BOUND(L.keys, k)
    INSERT L.keys at position i value k

FUNCTION SPLIT_LEAF(L):         // 4 keys → 2|2
    leftKeys  ← L.keys[0..1]    // two keys
    rightKeys ← L.keys[2..3]    // two keys
    R ← new leaf with keys = rightKeys
    L.keys ← leftKeys
    sep ← R.keys[0]             // separator promoted to parent

    IF L is root:
        P ← new internal node
        P.keys ← [sep]
        P.children ← [L, R]
        set parents; tree.root ← P
        RETURN

    // insert R as L's right sibling in parent
    P ← L.parent
    j ← index of L in P.children
    INSERT P.children at (j+1) value R
    INSERT P.keys at j value sep
    R.parent ← P

    IF |P.children| ≤ 4: RETURN
    SPLIT_INTERNAL(P)           // may cascade up

FUNCTION SPLIT_INTERNAL(M):     // 5 children → split 3|2 and promote
    // children: C0 C1 C2 C3 C4; keys: K1 K2 K3 K4  (Ki separates Ci-1 & Ci)
    leftChildren  ← [C0, C1, C2]
    rightChildren ← [C3, C4]
    promote ← K3                 // first key of right part

    leftKeys  ← [K1, K2]
    rightKeys ← [K4]

    // rewire
    L ← M                        // reuse M as left node
    R ← new internal node
    L.children ← leftChildren;   L.keys ← leftKeys
    R.children ← rightChildren;  R.keys ← rightKeys
    set parents of rightChildren to R

    IF M was root:
        P ← new internal node
        P.keys ← [promote]
        P.children ← [L, R]
        set parents; tree.root ← P
        RETURN

    // insert R into parent
    P ← M.parent
    j ← index of L in P.children
    INSERT P.children at (j+1) value R
    INSERT P.keys at j value promote
    R.parent ← P

    IF |P.children| > 4: SPLIT_INTERNAL(P)

FUNCTION LOWER_BOUND(a[], k):
    // returns smallest i with a[i] ≥ k, else a.length
    lo ← 0; hi ← |a|
    WHILE lo < hi:
        mid ← (lo + hi) // 2
        IF a[mid] < k: lo ← mid + 1
        ELSE: hi ← mid
    RETURN lo