B-Tree

A B-tree is the balanced, shallow tree most databases use for indexes. Each node holds a sorted run of keys, so a lookup walks from the root down a handful of child pointers instead of scanning every row. Because it stays only a few levels deep, search and insert are O(log n).

Order and the split rule

The order is the branching factor. This demo uses order 4, so each node holds at most 3 keys. Insert a 4th and the node overflows: it splits in two and promotes its middle key up to the parent. Promoting upward — never sideways — is what keeps every leaf at the same depth.

Inserting 10, 20, 5, 6, 12, 30, 7, 17

1. 110, 20, 5 fill the root: [5, 10, 20].
2. 2Insert 6 -> [5, 6, 10, 20] overflows (4 keys). Split, promote the middle key 10, leaving [5, 6] and [20] under a new root [10].
3. 312, 30 go right of 10 -> [12, 20, 30]; 7 goes left -> [5, 6, 7].
4. 4Insert 17 -> the right leaf becomes [12, 17, 20, 30] and overflows. Split, promote 20 up to the root, leaving [12, 17] and [30].

Final tree (order 4):

            [10, 20]
           /    |    \
    [5,6,7] [12,17]  [30]

Every leaf is exactly one step below the root — perfectly balanced.