Tries and Radix Trees: Structures Keyed by Prefix

A hash table finds an exact key fast. A balanced tree finds a key and its neighbours in sorted order. Neither answers this well: give me every key beginning with "rec".

A hash table cannot, because hashing deliberately destroys the relationship between similar keys, and "recall" and "receipt" land in unrelated slots. A sorted tree can, since shared prefixes sort adjacently, but every comparison costs a full string comparison, and it cannot answer the routing variant of the question: which of my stored prefixes is the longest one matching this key?

A trie answers both, because it does something neither of the others does. It stores the key in the shape of the structure itself, one character per level, so a prefix is not something you search for. It is a location.

In a trie, no node stores a whole key. Each edge carries one character, and a key is the concatenation of characters along the path from the root.

Storing car, cat, card and cow gives the shape above. The words car, cat and card share the path c-a, so that path exists once and is walked by all three. A node is marked as terminal to record that a key ends there, which is how card can extend car without either being lost.

Two consequences follow immediately. Lookup costs the length of the key and is completely independent of how many keys are stored, because you never compare against other entries. And every key sharing a prefix lives in one subtree, so prefix search is: walk to that node, then collect everything beneath it.

This independence from n is the trie's distinctive property, and worth stating carefully.

A hash table lookup is constant on average but must compute a hash over the whole key and then compare the full key to confirm a match. A balanced tree does about log n comparisons, each of which may compare long strings. A trie walks one node per character: at most as many steps as the key is long, whether the trie holds a thousand keys or a billion.

The catch is that a step is a child lookup, and how you store children decides everything. An array of 26 pointers per node is a single index, and enormous. A hash map per node is compact and slower. A sorted array of present children is a small binary search and cache-friendly. Real implementations agonise over this choice.

The naive trie is often unusable, and the reason is chains of single-child nodes.

Store the single key "internationalization". That is 20 characters, so the trie allocates 20 nodes, each holding one character and a child pointer table, and 19 of them have exactly one child. You have spent 20 node allocations to represent one string that a hash table would store in one.

The waste is worst exactly where you would want a trie: long keys with few shared prefixes. A node with a 256-entry pointer array for byte keys costs a kilobyte or two on a 64-bit machine, and almost all of it is null. This is the point at which most people conclude tries are a textbook curiosity.

The fix is direct. If a node has exactly one child, it carries no information: there is no decision to make there. So merge it into its child.

A radix tree, also called a compressed trie or Patricia trie, stores a string fragment on each edge rather than a single character. The chain for "internationalization" collapses from 20 nodes into one node holding the whole string. Nodes now exist only where keys actually diverge, so the node count is bounded by the number of keys rather than by their total length.

The savings are large in practice. Redis's rax implementation stores compressed prefixes inline in the node struct, and its documentation reports the technique cutting memory several-fold for string sets with long shared prefixes. Lookup logic barely changes: instead of matching one character per node, you match a fragment.

IP routing cannot use a hash table, and the reason is a different question shape.

A routing table does not store destinations, it stores network prefixes such as 10.0.0.0/8 and 10.1.0.0/16. An arriving packet for 10.1.2.3 matches both, and the rule is that the most specific one wins: the longest prefix match. A hash table can only answer whether an exact key is present, so it cannot express "most specific match" at all without probing every possible prefix length.

A trie answers it by construction. Walk the destination address bit by bit from the root, remembering the last node marked as a route. When you can walk no further, that remembered node is the longest matching prefix. The Linux kernel uses a compressed trie for exactly this, and BGP routers apply the same structure to IPv4 tables that now exceed a million entries.

Once you recognise the shape, radix trees appear in a lot of infrastructure.

Autocomplete is the obvious one: the user's typed characters are a path, and the candidate completions are the subtree below it. Ordering the results then needs a separate signal, usually a score stored at the terminal nodes.

Redis Streams index entries by a radix tree keyed on time-ordered ids stored big-endian, so nearby entries share long prefixes and compress well, which is precisely the case radix trees handle best. HTTP routers match URL paths, which are prefix-structured by design. Filesystems such as Btrfs index blocks this way. Ethereum's state is a Merkle Patricia trie, a radix tree in which every node is a hash of its children, so the same structure that locates a key also proves its value.

You now have the full set from this path, and they separate cleanly by the question being asked.

The honest caveat is that a trie is a specialist. For exact lookup a hash table is faster and simpler, and a radix tree carries more pointer indirection and worse locality than a flat table. Reach for one when the prefix relationship is genuinely part of the problem, not merely because the keys happen to be strings.

Few languages ship a trie in the standard library, so you will use a package or write one. A minimal version is short:

def insert(root, word):
    node = root
    for ch in word:
        node = node.setdefault(ch, {})
    node["$"] = True          # terminal marker

def starts_with(root, prefix):
    node = root
    for ch in prefix:
        if ch not in node:
            return None
        node = node[ch]
    return node               # subtree of all completions

Three things to watch. Decide your alphabet first: bytes are simpler and Unicode-safe, characters are more intuitive but explode the branching factor. Use a terminal marker that cannot collide with a real symbol. And if the key set is static, build a compact immutable form once rather than a pointer structure, since the write path is where tries are most wasteful.