B-Trees, One Split at a Time

This is the second entry in the data structures series. The red-black tree tutorial showed a binary tree repairing itself with colors and rotations. A B-tree solves the same broad problem with a different shape. It keeps several sorted keys in each node, then repairs overflow by splitting full nodes.

The demo below uses the same structure as the red-black tree piece: XState owns the tutorial trace, Phaser renders the current snapshot, and the URL records the values, step, and autoplay setting. Press Random to generate another insertion order, then watch where splits happen.

The reason B-trees are worth learning is not academic neatness. They sit underneath the systems people use every day: database indexes, storage engines, and filesystems. PostgreSQL, MySQL InnoDB, and SQLite all use B-tree or B-tree-like indexes because wide, shallow trees reduce the number of pages touched during lookup.

Read the red-black tree tutorial first if you want the binary-tree version beside it.

Jump to the interactive tree.

What a B-tree promises

A B-tree is built for shallow search. Instead of storing one key per node, each node stores a small sorted array of keys and points to child ranges between those keys. In storage systems, that shape matters because one node can map well to a disk or memory page.

This tutorial uses minimum degree 2, the smallest useful version. Each node can hold at most three keys. Non-root nodes hold at least one key. All leaves stay at the same depth. That last rule is the balancing promise: the tree grows evenly.

Insertion descends through ranges

Searching a B-tree node is a local ordered-array problem. If the node has keys 10 and 20, values below 10 go left, values between 10 and 20 go through the middle child, and values above 20 go right. Insertion follows those ranges until it reaches a leaf.

That is why the visualization highlights both the current node and the child chosen on descent. The node is acting like an index page. The child is the next page that can contain the inserted key.

Full nodes split before descent

The repair rule is simple: never descend into a full node. If the next child already has three keys, split it first. The median moves up into the parent. The smaller keys stay in the left sibling. The larger keys move into a new right sibling.

This top-down version makes the animation easier to reason about. By the time insertion reaches the target leaf, that leaf has room. The algorithm does not need to walk back upward to repair overflow.

Root splits grow the tree

A B-tree gets taller only when the root is full and must split. That creates a new root with one promoted median and two children. Every existing leaf moves one level lower together, so the equal-depth leaf invariant survives.

This is different from the intuition many people carry from binary trees. Growth happens at the top. Leaves receive keys, but height changes only when the old root cannot accept another key.

Why this pairs well with red-black trees

Red-black trees keep nodes small and use color metadata to bound height. B-trees keep nodes wide and use split rules to bound height. Both are balanced search trees, but they optimize for different costs. One makes pointer-heavy in-memory updates predictable. The other reduces the number of pages touched during search.

Seeing the two tutorials side by side makes the tradeoff concrete. Red-black insertion asks, what color is the uncle? B-tree insertion asks, is the child full before we enter it? The repair vocabulary changes, but the goal stays the same: preserve ordered search while preventing pathological height.

What to watch for

Step through the demo once just watching capacity. Nodes tolerate one, two, and three keys. On the fourth key, the median must move up. Step through again watching height. The tree remains short because each node carries more search information than a binary node can.

Once those two ideas separate, B-trees become less abstract. A split is not an afterthought. It is the balancing operation that lets a wide tree stay shallow.