B-trees: wide nodes, grown from the top

An AVL tree keeps a million keys within 28 levels, whatever order they arrive in. But each node visit buys just one comparison and a jump to somewhere new in memory. On disk, which reads a page of a few kilobytes at a time, every visit can cost a page read, far slower than any comparison.

A B-tree packs many sorted keys into each node, so one visit picks one branch out of hundreds. Rudolf Bayer and Edward McCreight invented it at Boeing around 1970, and it and its variant, the B+ tree, still hold the indexes of many databases and file systems. It also stays balanced in a new way: an insert never rotates. Nodes fill up, full ones split, and the tree grows only at the top.

order m

The most children a node may have, so a node holds at most m − 1 keys. A 2-3-4 tree has order 4: 1 to 3 keys a node.

keys and ranges

An internal node with k sorted keys has k + 1 children. Each key separates the child on its left, with smaller keys, from the one on its right.

leaf

A node with no children. In a B-tree every leaf is on the same level.

split and median

A node that ends up with m keys, one too many, splits into two nodes side by side, and its middle key, the median, moves up into the parent.

minimum fill

Every node except the root keeps at least ⌈m/2⌉ − 1 keys: 1 in a 2-3-4 tree, 2 at order 5.

borrow and merge

How a delete repairs a node left with too few keys: take one from a sibling through the parent, or join a sibling and pull down the parent's key between them.

This 2-3-4 tree holds 11 keys in 5 nodes. Its root, [30, 50, 80], has four children, one for each range: below 30, 30 to 50, 50 to 80, and above 80.

Inside a node, the search compares the key with the node's keys in order until it meets one at least as large (a big node would use binary search). Then it has either found the key or learned which one child's range could hold it.

Insert follows the same path down, and the new key always joins the leaf it reaches, in sorted order. A leaf that overflows splits: the keys before its median stay, the keys after it form a new node beside it, and the median moves up into the parent. With an even count there are two middle keys; this visualiser sends up the later one, so [10, 15, 20, 25] kept [10, 15] and sent up 20. Usually the parent has room and the splitting stops there.

An AVL tree adds a leaf at the bottom, then rotates when one side grows too tall. A B-tree never lets one side get taller: a split adds a node beside the old one.

Back to the same 2-3-4 tree. Insert 33, then 36, then 38. Before each step, predict which child the key goes down to, whether its leaf will split, and whether a median moving up will overflow the parent.

Here is a split in code, on a leaf of a B-tree of order 5, which holds at most 4 keys. insert_into_leaf puts the new key in sorted order, shifting larger keys right as an array insert does, and split cuts the list around its middle position.

def insert_into_leaf(keys, key):
    keys.append(key)
    i = len(keys) - 1
    while i > 0 and keys[i - 1] > key:
        keys[i] = keys[i - 1]
        i -= 1
    keys[i] = key

def split(keys):
    mid = len(keys) // 2
    left = keys[:mid]
    right = keys[mid + 1:]
    return left, keys[mid], right

leaf = [20, 40, 60, 80]
insert_into_leaf(leaf, 70)
left, up, right = split(leaf)
print('left:', *left)
print('up:', up)
print('right:', *right)

A split is O(m) work on one node, and an insert splits at most once per level on its way back up, so it touches O(log n) nodes. Most inserts split nothing: a split leaves two nodes about half full, so each takes about m/2 more keys before it can split again.

The root has at least 2 children and every other internal node at least ⌈m/2⌉, so each level below the second holds at least ⌈m/2⌉ times as many nodes as the one above. Real B-trees size a node to fill a disk page: with up to 500 children a node, a million keys always take exactly 3 levels and a billion exactly 4; a binary tree needs at least 20 and 30.

Delete works from a leaf too. A key in an internal node is first replaced by its predecessor, the largest key in its left subtree, which always sits in a leaf: delete 30 from the first tree and 25 takes its place in the root. A leaf left below the minimum fill turns to a sibling.

A merge takes a key out of the parent, so the parent can come up short too, and the repair climbs as a split does.

Orders 3 and 4 are called 2-3 and 2-3-4 trees. A 2-3-4 tree is the idea behind red-black trees: draw each node holding 2 or 3 keys as a black node with one or two red children, and splits become colour flips and rotations. Databases mostly use the B+ tree, which keeps every key in linked leaves for range scans; storage engines builds one.

• A B-tree of order m holds up to m − 1 sorted keys a node, and every node but the root at least ⌈m/2⌉ − 1. The keys split the children into ranges, so a search goes down one child per level.
• A new key joins a leaf. An overflowing node splits and its median moves up; only a root split adds a level, so every leaf stays on one level.
• Delete takes keys out of leaves (an internal key is swapped for its predecessor). A short node borrows through the parent or merges with a sibling, and merges can climb to the root.
• Comparisons stay about log₂ n, but node visits fall to the log of n to the base of the fan-out: with 500 children a node, a billion keys take 4 levels.
• Next: storage engines for B+ trees on disk, and red-black trees, 2-3-4 trees in binary form. Practise with Search a Sorted Grid and Check a Binary Search Tree, try Write binary search, or open the B-tree visualiser.