B-Trees and Databases

A binary search tree is good in memory, but when the data lives on a disk every step down the tree is a separate read of one page (usually 8 or 16 KB), and reading a page is thousands of times slower than a memory access. For a billion keys a balanced binary tree has about 30 levels, that is 30 disk reads. A B-tree puts many keys into one node, so that a node fills exactly one page. The tree becomes wide and low: a handful of levels is enough for a billion keys.

Why wide trees

Every level costs one page read. If a node branches into fanout ways, then n keys need about log_fanout(n) levels:

def levels(n, fanout):
    """How many pages must be read to find one of n keys."""
    h, capacity = 0, 1
    while capacity < n:
        capacity *= fanout
        h += 1
    return h

for n in (1_000_000, 1_000_000_000):
    print(n, "binary:", levels(n, 2), "fan-out 100:", levels(n, 100),
          "fan-out 500:", levels(n, 500))

1000000 binary: 20 fan-out 100: 3 fan-out 500: 3
1000000000 binary: 30 fan-out 100: 5 fan-out 500: 4

An 8 KB page holds about 500 entries of 16 bytes (key plus pointer), so the real fan-out is a few hundred.

The structure

A B-tree with minimum degree t (the "order" is often the maximum number of children 2t):

• every node holds t-1 … 2t-1 keys (the root holds 1 … 2t-1) and, if it is not a leaf, one more child than keys;
• the keys of a node are sorted, and the keys of child i lie between keys[i-1] and keys[i]: it generalises a BST;
• all leaves are on the same level;
• the height is h ≤ log_t((n+1)/2).

Search descends from the root: inside a node it finds the position with a binary search (bisect_left), then moves to the child with that index. It costs O(log n) page reads and O(log t) comparisons per page.

Insertion with a split