B-tree

Put the first 100,000 words of “War and Peace” into an index, as a database would: the key is a word and its place in the text, and a page holds up to 128 keys. The result is a tree of three storeys: the root, 16 pages under it and 1251 leaves. To find any of the hundred thousand keys you read three pages. An ordinary binary search tree on the same keys, inserted in the same order, grows to a height of 4800: the conjunction «и» (“and”) occurs 4785 times, its keys come in increasing order of position and line up in a chain. Below, each page of the index is drawn as a strip whose height is how full the page is.

The height does not change whatever you do with the order: three storeys both shuffled and alphabetical. The fill changes. In text order the leaves are 62.5 % full, shuffled 69.4 %, alphabetical exactly half: 1562 leaves instead of 782. And if you switch the split to “at the right edge”, alphabetical order gives leaves 99.9 % full. Why, we will see below; first, why a tree needs pages.

The idea

Disks and memory hand out data in blocks, and reading a whole block costs almost as much as reading one byte of it. So a tree node is made the size of a block: it holds hundreds of keys in order, and between them links to children holding the keys from the gaps. A search reads one page per storey, and with hundreds of children per node there are three to five storeys even for a billion keys. All leaves stay at the same depth: the tree grows not downwards but upwards, when the root splits.

This is a search tree with many keys in a node instead of one: within a page you search by binary search or a scan, but that work happens in memory and costs almost nothing compared with reading the page. How Rudolf Bayer and Edward McCreight invented it at Boeing, why nobody knows what the B stands for, and how B-trees are built inside SQLite is told in the course chapter on indexes; there is also a scene there where you can change the width of a node and see how many storeys are needed. Here: why you cannot do better, how much room goes to waste, and what databases do about it.

Why you cannot read fewer pages

When the data lie on disk, the search time is set not by the number of comparisons but by the number of blocks read: one read costs as much as millions of comparisons in memory. This is how the external memory model counts: a block of B keys is read in one operation, and everything done with it in memory is free.

The B-tree comes right up to this bound. Let a page hold up to 127 keys and 128 children and be filled with at least 63 keys and 64 children; this is a B-tree of minimum degree 64. A full tree of L storeys holds 128^L − 1 keys: three storeys up to two million, four up to 268 million. The sparsest holds 2 · 64^L−1 − 1. For a billion keys both bounds give the same: any such B-tree has exactly five storeys, and by the theorem there cannot be fewer than five reads. A binary search tree even of perfect shape would need 30 storeys, thirty pages per search if every node lies on its own page.

In practice even fewer pages are read: the root and the second storey are needed by every search and almost always sit in memory, so one or two pages come from disk. The article's second problem asks you to count how many storeys an index of a given size can have.

Insertion: a page splits, the tree grows upwards

The variant met most often in databases is called the B+ tree: all keys lie in the leaves, and the pages above hold only separators by which a search chooses which child to go down to. A new key goes down to a leaf and takes its place in it. If the leaf overflows, it splits in two, and the first key of the right half goes up into the parent as a separator. If the parent overflows, it splits too, and so on up to the root. When the root splits, a new root with one separator appears above it; that is the only way the tree gets taller, so all leaves are always at the same depth. No rotations are needed, as in the AVL tree: the balance holds by itself.

Hence the memory guarantee too. A leaf split in half leaves each half at least half the keys, and while keys are only being added, no page except the root is ever less than half full. On deletion a page that has dropped below half is topped up with a key from a neighbour or merged with it, and the guarantee is kept.

How much room stays empty

Half is a lower bound. What you get in practice depends on the order of the keys, and the scene shows it.

Random order. Andrew Yao showed in 1978 that with random insertions the pages of a B-tree with large pages are on average ln 2 ≈ 69 % full. A page that has just split is half full, a full one is full, and pages keep going through this cycle. On the novel's shuffled keys it comes to 69.4 %.

Text order. 62.5 %, less than random. The key is the pair “word, place”, and the places of each word come in increasing order: within its stretch of the index every frequent word is appended at the end, as with insertion in order. Real data again turn out to lie between theory and the worst case.

Increasing. This is how auto-increment row numbers, timestamps and order numbers arrive. Each new key is larger than all others and lands in the rightmost leaf, and after a split the left half never gets another key: all leaves except the last stay half full forever. The index takes twice the room it needs, and a search over it reads twice as many pages.

Twenty order numbers with splitting in half take nine leaves, 56 % full: every leaf except the last got two numbers and will get no more. Databases recognise this case. SQLite, when a new key becomes the largest in the table, does not split the overflowing leaf but starts a new page on the right and puts the one new key into it; the source says the right edge of the tree is left slightly unbalanced but will soon be filled by the next insertions. PostgreSQL, when splitting the rightmost page, leaves the left one filled to the fillfactor share, 90 % by default for B-tree leaves, and fills pages by the same rule when an index is rebuilt from an existing table. Switch the split in the first scene to “at the right edge”: alphabetical order gives 782 leaves 99.9 % full, half as many as with splitting in half.

B+ and ranges: the leaves are a linked list

In a B+ tree the leaves are linked in key order: a linked list of pages. A range query, “all keys from a to b”, goes down from the root to the first key of the range and then walks along the leaves without going back up. All 607 mentions of the word «князь» (“prince”) in the first 100,000 words of the novel come out of the index with full leaves in seven pages: three for the descent and four leaves in a row. Type any word into the scene to see both the descent and the run along the leaves.

A search engine's inverted index is built the same way: for each word, an ordered list of the places where it occurs.

Code

A B+ tree with two split rules, a range search along the linked leaves and a split counter. First a small example, the first twenty distinct words of the novel with four keys per page, then an index of the first 100,000 words with pages of 128 keys in four insertion orders. The numbers in the table match the scene.

order, split             height    pages per level leaves full  splits
text, half                    3          1-16-1251       62.5%   1,250
shuffled, half                3          1-16-1125       69.4%   1,124
alphabetical, half            3          1-24-1562       50.0%   1,561
alphabetical, edge            3           1-12-782       99.9%     781
князь: 607 keys, 7 pages read (3 down, the rest along the leaves)

The last line is printed by the last tree built, the one with full leaves. In Go the key “word and place” is written as a string: the word, a zero byte and the number with leading zeros. Such strings compare the same way as pairs, and the zero byte is smaller than any letter, so «кот» (“cat”) comes before «кота» (“of the cat”).

B-trees are good in main memory too: there the role of the block is played by a processor cache line. For this reason Rust's standard library keeps its ordered map BTreeMap in a B-tree rather than a binary one: the documentation says that in a binary tree every node is a separate allocation and every comparison a potential cache miss. A measurement: searching for existing keys in a binary tree, in a B-tree with pages of 64 keys, and by binary search in a sorted array:

With a thousand keys in Go the binary tree is even faster: it is all in the cache, and the B-tree has more work per page. With a million the B-tree is more than four times faster than the binary one and almost catches up with the sorted array, which can be thought of as a B-tree with one huge page. In Python the B-tree wins from the start: the search within a page is done by bisect, written in C, while the binary tree pays the interpreter for every storey.

What it costs

Memory is O(n) with some slack: every page is at least half full, about 69 % with random insertion. An insertion into the middle of a page shifts up to B keys, but that is work in memory on one block, and compared with reading it, it is free.

Where it is used

Almost everywhere ordered data lie on disk. SQLite keeps both tables and indexes in B-trees; the B-tree is the default index type in PostgreSQL, and MySQL's indexes are built on B-trees too. The Btrfs file system is named after the B-tree it rests on. In memory, BTreeMap in Rust. If there are far more writes than reads, instead of editing pages in place new keys are accumulated in memory and flushed to disk in sorted batches; that is how an LSM tree works, and the batches are later merged by an external sort.

History

Bayer and McCreight described the B-tree in a report of the Boeing research laboratories in 1970, and in 1972 the paper came out in the first volume of the journal Acta Informatica. In 1979 Douglas Comer called a survey of them “The Ubiquitous B-Tree”; the main variant discussed in it is the B+ tree, and it is one of the first places where that name appears. The average fill of ln 2 for random insertions was obtained by Andrew Yao in 1978; for this Yao devised a new method of analysing trees that was later applied to other structures as well. The story of Bayer and McCreight themselves is in the course chapter.

Problems

In the first problem you count how many pages an index will take if keys are inserted one at a time, and notice that the upper storeys are not needed for this. The tests are the words of “War and Peace” and the times of earthquakes from the USGS catalogue. In the second, how many storeys a B-tree with n keys can have, and the catch is that floating-point logarithms go wrong at the boundaries.