Path Compression and the Patricia Trie

An uncompressed trie over byte strings has one node per byte of every key. A key set that shares a long prefix — URLs under a common host, file paths under a common root, identifiers with a fixed namespace — produces long chains of nodes with exactly one child each. Those nodes carry no branching information: following them is a foregone conclusion, and their only content is the character they were labelled with. Compressing them away is the oldest optimization in the field, and the resulting structure is what most working implementations mean when they say “radix tree”.

What the chains cost

Consider a set of a thousand keys that all begin with the same 40-byte prefix. The trie has 40 nodes in a chain above the first branch, each holding a child pointer and a marker, and each is a separate heap allocation. Lookup traverses all 40, touching 40 nodes, of which 39 could be replaced by a single memcmp against a stored 40-byte string.

The waste is quantitative and easy to bound. A node in a compact layout costs at least the size of a pointer plus a header, call it 16 bytes. The chain costs 40 × 16 = 640 bytes to store information that a single string comparison resolves. Across a key set, the number of chain nodes is the total key length minus the number of branching positions, so a dictionary of long keys spends most of its nodes on chains. Deleting the chains replaces each maximal run of single-child nodes with one node, so the node count becomes the number of branching nodes plus the number of keys. Without compression there is one node per character of every distinct prefix, so for a set of long keys the saving is close to a factor of the key length rather than to a factor of two.

The compressed invariant

A Patricia trie stores a node only where the key set branches, plus a node for each stored key. Each edge carries a label: the substring between the parent’s branching position and the child’s. Lookup compares the edge label against the corresponding slice of the query rather than walking one character at a time, so a chain becomes one comparison.

Morrison’s formulation for binary keys uses an index instead of a stored string. Each node records the bit position at which it branches, and a lookup skips directly from bit position to bit position, testing only the bits that actually discriminate. For a key set of fixed-width binary keys — integers, hashes — this makes the node a pair of integers: the branching bit index and two child pointers. A node over a 64-bit key space costs 24 bytes, and the lookup tests one bit per level, so it examines at most 64 bits.

The two formulations differ in what they store. Storing edge labels makes the structure work for arbitrary byte strings and gives exact key recovery during traversal, at the cost of holding a copy of the key bytes in the structure. Storing a branching index works only when a chosen bit position can be compared against the key, which the original formulation achieves by keeping the full keys in a separate array and storing, at each node, both the discriminating bit position and the index of a key that passes through that node; the node itself costs a bit index and two child pointers. The second form is what suffix-tree and suffix-array construction use, and it is why Patricia over integers is so compact.

Lookup in the compressed form

The algorithm is a loop with two operations: compare the edge label against the corresponding slice of the key, then select the child whose edge label is the next key byte.

typedef struct pat_edge {
    unsigned char label;        /* the byte that selects this edge */
    struct pat_node *node;
} pat_edge;

typedef struct pat_node {
    const unsigned char *label; /* edge bytes after the selecting byte */
    unsigned len;               /* label length in bytes */
    bool terminal;              /* a key ends exactly here */
    unsigned count;
    pat_edge edge[];            /* sorted by label */
} pat_node;

/* Walks a compressed trie. Returns the node reached, or NULL on mismatch. */
static const pat_node *lookup(const pat_node *n, const unsigned char *key, size_t klen)
{
    size_t off = 0;
    while (n != NULL) {
        if (n->len > klen - off) return NULL;      /* key ends inside the label */
        if (memcmp(n->label, key + off, n->len) != 0) return NULL;
        off += n->len;
        if (off == klen) return n->terminal ? n : NULL;
        unsigned i = 0;
        while (i < n->count && n->edge[i].label != key[off]) i++;
        n = (i < n->count) ? n->edge[i].node : NULL;
        off++;                                     /* the selecting byte is consumed */
    }
    return NULL;
}

The split between the selecting byte and the stored label is what keeps the comparison cheap: a node’s children are distinguished by one byte, which is stored separately so that the child’s remaining label can be compared with memcmp as a contiguous run.

Two details matter. The length check must come before the memcmp, or a key shorter than the label makes the comparison read past the end of the key buffer — the classic off-by-one in compressed trie code. And the branching byte is consumed by the branch, so the offset advances past it; a structure that branches on a byte without advancing will re-examine it at the child and loop, or silently build a trie over the wrong key positions.

The comparison cost is the sum of edge label lengths along the path, which is at most the key length and typically much less, because branching happens early. Stated precisely: a lookup compares each byte of the key at most once, so it is O(L) for keys of length L, and the number of node visits is the number of branching levels, which is bounded by the number of keys rather than by their length.

Insertion requires finding the split point

Inserting a key into a compressed trie means walking until either the key is exhausted or an edge label mismatches. At the mismatch position, the existing edge must be split: a new node is created at the common prefix of the old label and the remaining key, the old edge label is shortened, and the new key’s suffix becomes a second child.

The split position is the length of the common prefix of the two strings, computed by a byte-by-byte comparison or by a word-at-a-time trick that XORs 64-bit chunks and counts trailing zeros. The latter reduces the comparison to one operation per eight bytes, which is what libraries whose split path is hot adopt. On a little-endian machine the first differing byte is the number of trailing zero bytes of the XOR divided by eight; on a big-endian machine it is the leading zeros. Getting that backwards does not simply preserve the trie: it produces a structure that disagrees with the ordering the split positions imply, so ordering queries silently return wrong answers while membership tests still pass.

Splitting also has to move the terminal marker. If the old edge terminated a key and the new key extends it, the split node becomes terminal and the old node stays as a child. If the new key is a prefix of the old label, the new key’s node is terminal and the old edge hangs below it. Both cases are the same code path if the terminal flag is treated as a property of the position rather than of a node, which is the connection to marking key boundaries in a trie.

Deletion and the re-merge

Removing a key clears its terminal marker and then merges: a node with a single child and no terminal marker is redundant, so its edge label is concatenated with the child’s and the node is freed. This is the inverse of the split, and it must run upward, because merging a node can leave its parent with a single child.

The merge step is where compressed tries are easiest to get wrong under concurrency, because it frees a node that another thread may be reading. A reader that has just loaded a child pointer and is comparing against the child’s label can find the label freed and reallocated. Solutions are the usual ones — reader-writer locks per subtree, or an epoch-based reclamation scheme that defers the free — and they are covered in concurrent updates to prefix trees.

There is a structural subtlety in the merge: concatenating two labels may require allocating a new buffer, since the parent’s label storage may not be adjacent to the child’s. An implementation that stores labels inline in the node (a short-string optimization) can merge without allocation when the combined length fits; one that stores pointers must copy. The copy is bounded by the maximum key length, so it does not change the asymptotic cost, but it does add an allocation to every deletion that merges.

Where compression stops paying

Compression removes chains, not branching. A key set with high branching at shallow depth — random 16-byte hashes, for example — has almost no chains to remove, so a compressed trie over hashes saves little and adds a comparison per edge. This is why hash-keyed structures use a radix tree over the integer form of the hash (as described in radix trees over fixed-width integer keys) rather than a compressed byte trie: the useful compression there is in the fan-out, not in the path length.

Compression also interacts badly with incremental insertion when labels are stored inline. A split requires shortening an existing label and creating two new ones, which is three memory operations per insertion at the split point instead of one pointer store. The uncompressed trie is faster to mutate and slower to read; the compressed one is the reverse. Which matters depends on the read-to-write ratio of the workload, and on how much of the savings falls on the read path.

The final limitation is that compression does not change the number of cache misses per lookup in proportion to the bytes saved. A lookup in a compressed trie touches one node per branching level, and each touch is a dependent load. Removing 39 chain nodes removes 39 misses, which is the win; but the remaining branching nodes are still scattered, and no compression scheme fixes that. Fixing it requires controlling where nodes are allocated, which is what the flat-array layouts do and what the adaptive node layouts of the adaptive radix tree address from the other direction: keeping branching high and nodes small.