B+ trees

What if every record sat in a leaf, and the leaves were chained in order? Watch a range read with one descent.

⋯38static const struct bpnode *find_leaf(const struct bpnode *x, int key)39{40    reads++;41    while (!x->leaf) {42        int i = 0;43        while (i < x->n && key >= x->keys[i])44            i++;45        x = x->child[i];46        reads++;47    }48    return x;49}50 51void range(const struct bpnode *root, int lo, int hi)52{53    const struct bpnode *leaf = find_leaf(root, lo);54    while (leaf != NULL) {55        for (int i = 0; i < leaf->n; i++) {56            if (leaf->keys[i] > hi)57                return;58            if (leaf->keys[i] >= lo)59                printf("%d ", leaf->keys[i]);60        }61        leaf = leaf->next;62        if (leaf != NULL)63            reads++;64    }65}⋯92    range(root, 30, 70);93    printf("\n%d nodes read\n", reads);

Signposts and leaves

In a B-tree, a key and its record can sit in any node. A B+ tree separates the two jobs:

• the leaves hold every record, in key order, and each leaf points to the next one;
• the inner nodes hold only signposts: keys that say which way to go, and pointers to children.

A signpost k sends smaller keys to the child on its left and keys equal to k or larger to the child on its right. So a signpost often repeats a key that is also in a leaf: in the clip, 30, 50, 70 and 90 each appear twice. The copy in the inner node only guides the search; the record is the copy in the leaf.

A range query, every key from lo to hi, is then one descent and a walk: go down to the leaf where lo belongs, then read leaves left to right along their links until a key passes hi. The walk never goes back up.

The code and its cost

The node

The full program, range.c, uses one node type for both kinds:

#define MAXK 4

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

An inner node uses keys as signposts and child for its children; a leaf uses keys as its records and next for the link to the leaf on its right. The struct is 72 bytes: leaf at offset 0, 3 bytes of padding, n at 4, the keys from 8 to 23, the five child pointers from 24 to 63, and next at 64. main builds the tree by hand, as Binary trees built its tree, and links the leaves with l1->next = l2 and so on.

The descent

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

find_leaf moves right past every signpost the key is equal to or larger than, then goes down. It counts each node it reads in reads. For 30: at the root, 30 < 50, so child[0]; at the node 30, 30 ≥ 30, so child[1], the leaf 30 40. Three reads.

The walk

const struct bpnode *leaf = find_leaf(root, lo);
while (leaf != NULL) {
    for (int i = 0; i < leaf->n; i++) {
        if (leaf->keys[i] > hi)
            return;
        if (leaf->keys[i] >= lo)
            printf("%d ", leaf->keys[i]);
    }
    leaf = leaf->next;
    if (leaf != NULL)
        reads++;
}

Each leaf is read once, in order. The first key larger than hi ends the query; keys smaller than lo in the first leaf are skipped. For the range 30 to 70 the walk reads two more leaves, 50 60 and 70 80, and stops at 80: 5 nodes read in all.

Inserting

The program builds its tree by hand, but insertion follows the B-tree rules with one difference. A new key goes into its leaf. A full leaf splits in two and copies the first key of the right half up as a new signpost, because that key’s record must stay in a leaf. A full inner node splits as in a B-tree and moves its middle key up, since it was only a signpost. The new leaf is linked between its neighbours, so the chain stays in order.

What it costs

A range query reads one node per level to reach the first leaf, then one leaf per leaf’s worth of keys in the range: about log n + k/B reads for k keys in the range and B keys per leaf. Because inner nodes carry no records, only keys and pointers, many more fit in a block than in a B-tree node, so the tree has fewer levels.

Running it yourself

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

It prints 30 40 50 60 70, then 5 nodes read.

Worked example

Insert 35. The descent goes left of 50, right of 30, to the leaf 30 40, which has room for up to 4 keys: it becomes 30 35 40. No split, and no signpost changes.

Fan-out. An inner node of 4,096 bytes with 8-byte keys and 8-byte child addresses holds k keys and k + 1 addresses in 16k + 8 bytes, so k = 255 keys and 256 children. Three inner levels reach 256³ = 16,777,216 leaves.

The range 55 to 95. The descent reads the root (55 ≥ 50, go right), the node 70 90 (55 < 70, go left) and the leaf 50 60, where 50 is skipped and 60 printed. The walk reads 70 80 and 90 95 and prints all four keys; then next is NULL. 5 nodes read, printing 60 70 80 90 95.

Two checks. How many nodes does the range 10 to 95 read? (7: the root, the node 30, the leaf 10 20, then four more leaves.) Where is the record for 70? (In the leaf 70 80; the 70 in the inner node is a signpost.)

Where it’s used

Database indexes. The B+ tree is the main index structure of relational databases: a query such as “every order between two dates” is one descent and a walk along the leaves.

File systems. Several file systems keep directories and file extents in B+ trees.

Key-value stores. Any store that must answer “every record between these two keys” benefits from leaves kept in order and linked.

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.