B-Tree Visualizer

Most explanations of search trees count comparisons. That is the wrong unit for an index in storage, where the expensive act is fetching the block that holds a key. Comparing keys inside it is close to free.

Open Data Structures puts numbers on the gap. The computer its author wrote on had a hard disk with an average access time of 19 milliseconds and a solid state drive at 0.3 milliseconds, while main memory answered in under 0.000113 milliseconds. Memory was more than 2,500 times faster than the solid state drive and more than 160,000 times faster than the disk. Both drives also read whole blocks of 4,096 bytes, so asking for one byte delivers four thousand. The external memory model built on that observation charges a fixed price for moving a block and nothing for work done inside memory.

The cost that shaped the tree

Under that price list a binary tree is a poor deal. Each node holds one key, so each step down is a fresh block read that halves the search and no more. A binary search over a million sorted records needs about 20 comparisons, and if each one lands on a different block, that is 20 reads.

The B-tree’s answer is to make each node as wide as a block. It generalizes the binary search tree by letting a node have many children, so a single read narrows the search by a factor of hundreds instead of two. Height then grows with the logarithm of the number of keys taken to that much larger base, and the tree stays short.

The rules that keep every leaf level

Sources disagree about what the order of a B-tree means, so it pays to fix one meaning and keep it. Bayer and McCreight, and later Comer, defined the order as the minimum number of keys in a node other than the root. Knuth avoided the ambiguity by defining the order m as the maximum number of children. The tool uses Knuth’s order everywhere.

With order m, every node has at most m children and so at most m minus 1 keys. Every node except the root has at least m/2 children, rounded up, and the root may have as few as two. All leaves sit on the same level. Some books state the same rules with a minimum degree t, the fewest children a non-root node may have: t is m/2 rounded up, and when m is even, m is exactly 2t. Open Data Structures uses that form, calls the minimum B, and gets the 2-4 tree as the case B = 2.

The keys inside an internal node are separators. If a node holds keys a1 and a2, everything in its left subtree is smaller than a1, everything in the middle subtree lies between them, and everything to the right is larger. A search is therefore one read per level and a short scan inside each node.

Those rules pin the height from both sides. A tree whose nodes are all full holds m to the power h + 1, minus 1, keys at height h, which gives the shortest possible height for n keys. At the other end, the B-tree article on Wikipedia quotes Comer and the textbook by Cormen and colleagues for the tallest possible height: the floor of the base-d logarithm of (n + 1)/2, where d is the minimum number of children. The tool counts the nodes each search reads and checks the level count against both bounds after every step. In its own test runs, every tree from 1 to 3,000 keys at orders 3 to 8 stayed inside them.

Growing at the root

Insertion never makes a leaf deeper. A new key goes into the leaf where a search for it ends. If that leaf is now one key over its limit, it splits into two nodes, and the median key moves up into the parent as a new separator. Each half keeps at least the minimum, because the limits were chosen so that an over-full node always divides into two legal ones.

The parent may overflow in turn and split, and so on up the path. Only when the root itself splits does a new root appear above it, holding one key and two children. That is the only moment the tree gets taller, and it gets taller everywhere at once, which is why every leaf stays at the same depth. The B+ tree article puts it in one line: these trees grow at the root and not at the leaves.

Splits can be scheduled two ways. The tool splits from the bottom up, after the key has landed. The alternative splits every full node on the way down and never returns to a parent.

A worked example makes the rule concrete. Set the order to 4, which is a 2-3-4 tree, and insert 5, 10, 15, 20, 22, 24 and 29. The root holds 10 and 20, and the rightmost leaf holds 22, 24 and 29, which is full. Now insert 25. The leaf would hold four keys, so it splits around 24, which moves up; the root becomes 10, 20 and 24, and the leaves on the right are 22 alone and 25 with 29. That matches the drawing in the 2-3-4 tree article, which reaches it by splitting on the way down. Search for 25 afterwards and the tool reports two page reads.

Deletion, the careful half

Deletion is where hand-written B-trees usually go wrong, because the minimum can now be broken from below. Removing a key from a leaf is easy when the leaf has a key to spare. Removing a separator from an internal node is not, since that key holds two subtrees apart. The standard repair replaces it with its predecessor, the largest key in the left subtree, or its successor, the smallest in the right. Both live in leaves, so every deletion becomes a deletion from a leaf.

If that leaf drops below the minimum, the tree first tries to borrow. When an adjacent sibling has a key to spare, the separator in the parent comes down into the short node and the sibling’s nearest key goes up to replace it, a rotation through the parent. When neither sibling can spare one, the short node merges with a sibling, and the separator between them comes down into the merged node. The parent has lost a key and may itself be short, so the repair climbs. A root left with no keys is removed and its only child takes over, and the tree becomes one level shorter everywhere at once.

The tool names the case each deletion hits. Its test runs of 3,000 random operation sequences at every order from 3 to 8 reached every one of them, from a plain leaf removal to a merge between two internal nodes, with every invariant checked after each step.

B+ trees, ranges and the 1972 paper

The variant most often found in storage is the B+ tree. The dictionary kept by the National Institute of Standards and Technology defines it as a B-tree in which keys are stored in the leaves. Internal nodes hold copies of keys only to route a search, and the leaves are linked in order. A leaf split copies the first key of the new right leaf up into the parent instead of moving it, so every key still lives in some leaf.

The linked leaves are the point. To answer a query for every key from 20 to 60, the tree is searched once for 20 and then read sideways along the chain until a key passes 60. The cost is the height plus the leaves that hold the answer. Open Data Structures adds a second reason the shape pays: with fan-outs in the hundreds or thousands, 99 percent or more of the data sits in the leaves, so the internal nodes can often stay in memory and a search costs a single block read.

Rudolf Bayer and Edward McCreight invented the structure while at Boeing’s research laboratories, to manage index pages for large random access files. Their paper was first circulated in July 1970 and published in Acta Informatica in 1972 as “Organization and maintenance of large ordered indexes”. They never explained the B. Comer listed balanced, broad and bushy as candidates, noted that others read it as Boeing, and suggested thinking of them as Bayer trees. His survey of 1979, less than ten years after the first paper, already called the structure ubiquitous and a de facto standard for file organization.

The ideas kept arriving. Bayer and Unterauer’s prefix B-trees of 1977 store only key prefixes in the index part. Lehman and Yao in 1981 gave each node one extra link pointer, so that concurrent processes recover from each other’s splits while locking only a few nodes. Graefe’s 2011 survey of modern techniques runs to about 200 pages.

What it does not promise

A B-tree is not the fastest structure for every job. If a program never needs keys in order, Open Data Structures notes that external memory hashing answers lookups in constant expected time. The rules only promise half-full nodes, which is why the B* variant keeps them at least two-thirds full. And the classic tree is tuned to one known block size; Bender, Demaine and Farach-Colton showed that the same optimal bound can be reached without knowing it, across every level of a memory hierarchy.

The page arithmetic in the tool is an illustration of that tuning, not a measurement of any product. A 4,096-byte page with 8-byte keys and 8-byte pointers holds 256 children, since 256 pointers and 255 keys take 4,088 bytes. At that fan-out a million keys need exactly three levels, whether the nodes are full or half empty, so three page reads find any of them. Real systems add headers, variable-length keys and caches, and none of that is modelled here.