Radix trees

The trie of Tries spends a node on every letter. Here an edge carries a whole run of letters instead. Watch the same six words go in.

⋯30void insert(struct rnode *t, const char *w)31{32    for (;;) {33        if (*w == '\0') {34            t->end = true;35            return;36        }37        int k = 0;38        while (k < t->nchild && t->child[k]->label[0] != w[0])39            k++;40        if (k == t->nchild) {41            t->child[t->nchild++] = new_rnode(w, strlen(w), true);42            return;43        }44        struct rnode *c = t->child[k];45        size_t n = 0;46        while (c->label[n] != '\0' && c->label[n] == w[n])47            n++;48        if (c->label[n] != '\0') {49            struct rnode *mid = new_rnode(c->label, n, false);50            memmove(c->label, c->label + n, strlen(c->label + n) + 1);51            mid->child[0] = c;52            mid->nchild = 1;53            t->child[k] = mid;54            c = mid;55            splits++;56        }57        t = c;58        w += n;59    }60}61 62void print_tree(const struct rnode *t, int depth)63{64    for (int i = 0; i < t->nchild; i++) {65        const struct rnode *c = t->child[i];66        printf("%*s%s%s\n", 2 * depth, "", c->label, c->end ? " *" : "");67        print_tree(c, depth + 1);68    }69}⋯78int main(void)79{80    struct rnode *root = new_rnode("", 0, false);81    const char *words[6] = { "car", "cart", "care", "cat", "dog", "do" };82    for (int i = 0; i < 6; i++)83        insert(root, words[i]);84    print_tree(root, 0);85    printf("%d nodes, %d splits\n", nodes, splits);86    free_tree(root);87    return 0;88}

Squeezing out the chains

In the trie of the six words car, cart, care, cat, dog and do, two nodes have a single child and no end mark: c and d. They only pass one letter on to the next node. A radix tree merges each such chain into one edge, labelled with the whole run of letters. The edge “ca” replaces the edges c and a, and the node c between them goes; the edge “do” replaces d and o, and the node d goes.

Nothing is lost. The letters still sit on the way down, now several to an edge, and the end marks stay where words end. After squeezing, every node except the root either ends a word or branches into two or more children. Here the trie’s 10 nodes become 8, c and d gone, and its 9 one-letter edges become 7 edges carrying the same 9 letters: ca, r, t, e, t, do and g.

The code and its cost

A node with a label

struct rnode {
    char label[MAXL];
    bool end;
    int nchild;
    struct rnode *child[MAXC];
};

Each node keeps the label of the edge above it, its end mark, and up to MAXC children. To keep the program short, labels are at most 15 letters (MAXL is 16, with room for the '\0') and a node has at most 8 children (MAXC is 8); a real radix tree would allocate both to fit. sizeof (struct rnode) is 88 bytes: 16 for the label, 1 for the mark, 4 for the count after 3 bytes of padding, and 64 for eight pointers. The children stay in the order they were added. Nodes come from calloc, as in the trie, and two static counters count the nodes and the splits.

Inserting a word

void insert(struct rnode *t, const char *w)
{
    for (;;) {
        if (*w == '\0') {
            t->end = true;
            return;
        }
        int k = 0;
        while (k < t->nchild && t->child[k]->label[0] != w[0])
            k++;
        if (k == t->nchild) {
            t->child[t->nchild++] = new_rnode(w, strlen(w), true);
            return;
        }
        struct rnode *c = t->child[k];
        size_t n = 0;
        while (c->label[n] != '\0' && c->label[n] == w[n])
            n++;
        if (c->label[n] != '\0') {
            struct rnode *mid = new_rnode(c->label, n, false);
            memmove(c->label, c->label + n, strlen(c->label + n) + 1);
            mid->child[0] = c;
            mid->nchild = 1;
            t->child[k] = mid;
            c = mid;
            splits++;
        }
        t = c;
        w += n;
    }
}

Each round of the loop does one of four things:

1. The word is used up. Mark the node: a word ends here.
2. No child starts with the next letter. Hang a new node labelled with the rest of the word, and stop. No two children of a node start with the same letter, so the first letter picks the only possible child.
3. The word follows the child’s whole label. Go down to the child and carry on with what is left of the word.
4. The word leaves the label part-way. Split the edge: make a middle node for the letters both share, keep the rest of the label on the old node, and hang the old node under the middle one. Then carry on from the middle node.

In the clip, cat meets the edge car, shares 2 letters and leaves it: the middle node gets “ca”, and memmove slides “r” and its '\0' to the front of the old node’s label, so the old node, with its end mark and its children t and e, now hangs under ca as r. Then t hangs beside it. do does the same to dog: the middle node do gets the end mark, case 1, on the next round.

The rest of the label moves to the front of the same array. In the clip the two pieces do not overlap: “r” and its '\0' move from bytes 2 and 3 to bytes 0 and 1, and so do “g” and its '\0'. But they may: splitting an edge “carton” after “ca” moves the 5 bytes of “rton” and its '\0' from bytes 2 to 6 onto bytes 0 to 4. memcpy on overlapping memory is undefined behaviour; memmove works as if it copied through a separate buffer, so the code uses memmove.

Printing it

void print_tree(const struct rnode *t, int depth)
{
    for (int i = 0; i < t->nchild; i++) {
        const struct rnode *c = t->child[i];
        printf("%*s%s%s\n", 2 * depth, "", c->label, c->end ? " *" : "");
        print_tree(c, depth + 1);
    }
}

%*s prints an empty string padded to the width given before it, here 2 × depth spaces, so each level is indented two more. A star marks a word’s end:

ca
  r *
    t *
    e *
  t *
do *
  g *
8 nodes, 2 splits

How many nodes

With w words, there are at most w nodes that end a word. A node that branches joins at least two subtrees, each holding at least one word; joining w words that way takes at most w − 1 branching nodes. So besides the root a radix tree has at most 2w − 1 nodes, whatever the words, while a trie can need a node for every letter. The six words here need 7 nodes besides the root.

Binary radix trees and the longest prefix

Routers keep routes for blocks of addresses such as 10.1.0.0/16: every address whose first 16 bits match. They store the routes in a radix tree over the bits of an address, with two possible children per node, 0 and 1. To send a packet, a router follows the address’s bits down the tree and remembers the last node that held a route: the longest prefix match, the most specific route that covers the address.

Running it yourself

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

Worked example

Inserting “carton”. It follows ca, then r, then t, all whole labels, and t has no child starting with o, so a new node labelled “on” hangs under t. No split.

Inserting “ca”. It follows the whole of ca and the word is used up: the ca node gets an end mark. No new node.

Why the root’s label is empty. The root stands for the empty prefix, before any letter.

Three routes. A router holds 10.0.0.0/8, 10.1.0.0/16 and 10.1.2.0/24. The address 10.1.2.3 matches all three, and the /24 wins as the longest. 10.1.9.9 matches the /8 and the /16, and the /16 wins. 10.200.0.1 matches only the /8.

The memory. The eight nodes take 8 × 88 = 704 bytes, against the trie’s 10 × 216 = 2,160 bytes for the same words.

Where it’s used

Network routers. Forwarding tables find the longest prefix that matches each packet’s destination address, in binary radix trees and their variants.

Database indexes. In-memory indexes keep keys in radix trees, where shared beginnings are stored once.

Web servers. URL routers match paths such as /users/42/posts by walking a radix tree of path segments.

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.