B-trees

What if each node held as many keys as one disk block? Watch twenty keys fill a tree of only three levels.

⋯50static void insert_nonfull(struct bnode *x, int key)51{52    int i = x->n - 1;53    if (x->leaf) {54        while (i >= 0 && key < x->keys[i]) {55            x->keys[i + 1] = x->keys[i];56            i--;57        }58        x->keys[i + 1] = key;59        x->n++;60        return;61    }62    while (i >= 0 && key < x->keys[i])63        i--;64    i++;65    if (x->child[i]->n == MAXK) {66        split_child(x, i);67        if (key > x->keys[i])68            i++;69    }70    insert_nonfull(x->child[i], key);71}72 73struct bnode *btree_insert(struct bnode *root, int key)74{75    if (root->n == MAXK) {76        struct bnode *s = new_bnode(false);77        s->child[0] = root;78        split_child(s, 0);79        insert_nonfull(s, key);80        return s;81    }82    insert_nonfull(root, key);83    return root;84}⋯112    for (int k = 1; k <= 20; k++)113        root = btree_insert(root, k);114    int height = 0;

Many keys per node

A disk, or flash memory, does not read one key at a time. It reads a block, often 4 or 16 kilobytes, and the wait for one block is long next to the time to compare thousands of keys already in memory. A search tree on disk should therefore make as few block reads as possible: as few levels as possible.

A B-tree is a 2-3 tree with wider nodes, each sized to fill a block. Its width is set by its minimum degree t:

• every node except the root holds between t − 1 and 2t − 1 keys, and the root holds 1 to 2t − 1;
• a node that is not a leaf has one more child than it has keys, ordered like a 2-3 tree’s;
• every leaf is at the same depth.

The clip uses t = 3, so each node holds 2 to 5 keys. Real B-trees use t in the hundreds.

Inserting works as in a 2-3 tree: the key goes into a leaf, and a node with too many keys splits and sends its middle key up. This program does it one way round: it splits any full node it meets on the way down, before going into it, so there is always room in the parent for the key that comes up.

The code and its cost

The node

The full program, btree.c, stores a node as:

#define T 3
#define MAXK (2 * T - 1)

struct bnode {
    int n;
    int keys[MAXK];
    struct bnode *child[MAXK + 1];
    bool leaf;
};

n is how many of the five keys are in use, child has room for six pointers, and leaf says whether there are any. sizeof (struct bnode) is 80: n at offset 0, the keys from 4 to 23, the pointers from 24 to 71, leaf at 72, and 7 bytes of padding so that an array of nodes keeps its pointers aligned. On a disk the node would be one block, with hundreds of keys.

Searching

while (x != NULL) {
    int i = 0;
    while (i < x->n && key > x->keys[i])
        i++;
    if (i < x->n && key == x->keys[i])
        return true;
    if (x->leaf)
        return false;
    x = x->child[i];
}

In each node, i stops at the first key not smaller than the one sought. If that key is the one, it is found; if not, the search goes down child[i], the subtree between keys[i - 1] and keys[i]. The program runs btree_search for 13, found in the leaf 13 14, and for 21, which ends in the leaf 16 to 20 without finding it: it prints search 13: 1, search 21: 0.

This program looks through a node’s keys one by one. With hundreds of keys per node, real B-trees use a binary search inside the node: halve the range of keys at each comparison, about 10 comparisons for 1,000 keys.

Splitting on the way down

split_child(x, i) splits x->child[i], a full node y with five keys. A new node z takes y’s last two keys (and, if y is not a leaf, its last three children); y keeps its first two; and the middle key, y->keys[2], moves up into x at place i, with z as the child just right of it. Keys and children of x from place i on shift one place right to make room.

insert_nonfull(x, key) adds a key below a node that is not full. In a leaf it shifts larger keys right and puts the key in. In an inner node it finds the child to go down; if that child is full, it splits it first, then compares the key with the one that came up to choose the left or right half:

if (x->child[i]->n == MAXK) {
    split_child(x, i);
    if (key > x->keys[i])
        i++;
}
insert_nonfull(x->child[i], key);

btree_insert handles the one case left: a full root. It makes a new root s with the old root as its only child, splits that child, and continues from s. That is the only way the tree gets taller, so, as in a 2-3 tree, every leaf stays at the same depth.

What it costs

Every inner node but the root has at least t children, so a tree of height h holds at least 2t^h − 1 keys. For n keys, then,

A search or an insertion visits one node per level, so it reads at most h + 1 blocks. With t = 3 and 20 keys the bound is log₃ 10.5 ≈ 2.1, so the height is at most 2, and the program prints height 2.

Removing a key keeps the same rules the other way round: a node that would fall below t − 1 keys borrows one from a sibling, through the parent, or merges with a sibling and takes a key down from the parent. The code is longer and is not shown here.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic btree.c -o btree
./btree

It prints 20 keys, height 2, 6 splits, then search 13: 1, search 21: 0.

Worked example

A billion keys. Take nodes of up to 999 keys (t = 500), and a tree with three levels of nodes, all full: 1 root, 1,000 nodes under it and 1,000,000 leaves, each with 999 keys. That is 999 × (1 + 1,000 + 1,000,000) = 1,000³ − 1 = 999,999,999 keys. A lookup reads three blocks, and a binary search inside each makes at most 10 comparisons, since 2¹⁰ = 1,024 is more than 999.

The same keys in a binary tree. A balanced binary search tree of a billion keys has about 30 levels, since 2³⁰ is about 1.07 billion: 30 block reads if each node were a block.

Insert 21 into the final tree. The root 9 is not full; 21 > 9, so go to 12 15, which is not full either; 21 > 15, so the next child is the leaf 16 17 18 19 20, which is full. It is split before the descent enters it: 18 rises into 12 15, which becomes 12 15 18, and the halves are 16 17 and 19 20. 21 > 18, so it goes into 19 20, giving 19 20 21. Seven splits in all, and the height is still 2.

Two checks. With t = 3, how many keys can a node hold at most? (5, that is 2t − 1.) And at least, if it is not the root? (2, that is t − 1.)

Where it’s used

Database indexes. Most relational databases keep their indexes in B-trees, usually the B+ tree form, with each node one page of the file.

File systems. Several file systems keep directories, or the map from a file to its blocks on the disk, in B-trees.

Key-value stores. Many embedded databases store their whole data set as a B-tree, one page per node.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.