The Trie

A trie stores a set of strings by making each key a path from the root. One edge carries one symbol of the alphabet, and the node reached by following c, a, t is the node for the prefix "cat". A key is present when its path exists and the node at the end is marked terminal; the node itself holds no copy of the key, because the path already spells it.

Two keys that share a prefix share the nodes for that prefix. "cat", "car", and "cart" occupy one chain of three nodes plus two branches, not three separate strings. Nothing is ever compared: navigation dispatches on one symbol at a time, so no key comparison of any length occurs during a lookup.

Take the trie holding "cat", "car", "cart", and "dog", and ask whether "car" is in it. The search begins at the root with the whole key in hand and no idea where the answer lives. It reads the first symbol, c, and looks for a child edge labelled c. One exists, so the search steps onto it and is now at the node for the prefix "c" — meaning it has already discarded "dog" and everything else starting with d, without looking at any of them.

It reads a and takes the a edge, reaching the node for "ca". It reads r and takes the r edge, reaching the node for "car". The key is now spent, so the search stops and asks one question: is this node marked terminal? It is, so "car" is present. Three symbols, three edges, and not one character comparison against a stored key — the only thing that decided the answer was which edges existed along the way.

A missing edge ends the search immediately. Looking up "cot" reads c, steps to the "c" node, reads o, finds no o edge, and reports absence at depth two, having never read the third symbol. Reaching a node with the key spent is also not enough on its own: "ca" is a real path in this trie but its node carries no terminal mark, so "ca" is a prefix of stored keys and not a stored key itself.

Lookup of a key of length m reads one symbol, selects the matching child, and repeats. It fails as soon as a child is missing. The cost is O(m) in the worst case and it does not depend on n, the number of keys stored: a dictionary of ten keys and a dictionary of ten million answer a five-character query in the same five steps.

Insertion walks the same path and allocates a node wherever the child is absent, then marks the final node terminal, again O(m). Deletion clears the terminal mark and then removes nodes back up the path while they have no children and no mark of their own. The bound is stated per key length rather than per key count, which is the property that separates a trie from every comparison-based structure such as the red-black tree.

The child pointers have to live somewhere, and the choice of layout dominates the memory profile. A node holding one array slot per symbol gives O(1) child selection and costs σ pointers per node — 2 KB per node for 8-byte pointers over 256 byte values, whether the node has one child or two hundred. A node holding a sorted list of occupied symbols costs bytes proportional to the actual children but selects a child in O(log σ) or by linear scan.

The waste is concentrated near the leaves. In a trie over natural-language words, most nodes below the second level have a single child, so a full array layout stores one pointer and 255 nulls. Measured against the keys themselves, a naïve trie can occupy an order of magnitude more memory than the concatenated strings. The next three cards are all responses to that fact. Space complexity is the binding constraint here, not time.

Path compression collapses every chain of single-child nodes into one node that stores the whole skipped substring. A trie holding only "internationalization" degenerates to a 20-node chain; compressed, it is one node carrying the full string. The result is called a radix tree, or a Patricia trie after Morrison's 1968 formulation, which applied the same idea one bit at a time.

The rule that follows is a bound on shape: every internal node in a compressed trie has at least two children, so a set of n keys produces at most n − 1 internal nodes regardless of key length. Lookup gains a step — on reaching a compressed node the search must compare the stored substring against the corresponding slice of the query — but that comparison is a memcmp over contiguous bytes rather than a sequence of pointer dereferences.

Path compression removes chains but leaves the tree tall wherever branching is dense. Level compression attacks the other direction: where the top k levels of a binary trie are nearly full, replace them with a single node of 2^k children indexed by the next k bits of the key. One array read then consumes k levels of descent. Nilsson and Karlsson combined both transformations into the LC-trie in 1999.

The parameter is a density threshold: expand a subtree into a 2^k-way node when at least some fraction of the 2^k slots would be occupied. Setting the threshold low buys depth with memory, setting it high does the reverse. The Linux kernel's IPv4 forwarding table is an LC-trie for exactly this reason, and a full BGP view of roughly 800,000 routes resolves in about 50 ns using around 64 MiB.

A third response is to let each node choose its own representation. The adaptive radix tree of Leis, Kemper, and Neumann defines four node types by capacity — 4, 16, 48, and 256 children — and promotes or demotes a node as its child count crosses a boundary. A node with three children costs a 4-entry key array and 4 pointers; a node with two hundred costs the full 256-slot array that makes child selection a single indexed read.

The small types keep sorted key arrays that a linear or SIMD-assisted scan searches in a few instructions, and the 48-entry type keeps a 256-byte index into a dense pointer array, so child lookup stays O(1) without paying 256 pointers. Combined with path compression, the design was measured to hold node overhead near the level of a well-tuned hash table while keeping keys in sorted order, which a hash table cannot do.

Descending to the node for a prefix and then traversing its subtree yields every key with that prefix, in lexicographic order, at a cost of O(p + z) for a prefix of length p and z keys reported. No key outside the answer set is examined, because keys outside the set are not in the subtree. This is the operation autocomplete needs, and the reason a trie is chosen over a hash index for that job.

Ordering falls out of the same property. Visiting children in symbol order at every node produces the keys in sorted order, so a trie supports range scans and successor queries the way a skip list or a balanced search tree does. Ranking the completions — most-frequent-first rather than alphabetical — requires storing an aggregate at each node, typically the maximum score in the subtree, and descending greedily against it.

IP forwarding does not ask whether a key is present. It asks which of the stored prefixes is the longest one that the destination address begins with, since 10.0.0.0/8 and 10.1.0.0/16 may both be installed and the more specific route must win. A trie answers this by descending on the address bits and recording the most recent terminal node passed; when descent stops, that record is the answer.

The cost is one descent, bounded by the address width — 32 steps for IPv4 and 128 for IPv6 in an uncompressed binary trie, far fewer once path and level compression apply. No other index does this directly: a hash table would need one probe per possible prefix length, and an ordered structure would need a predecessor search followed by a check that the candidate is actually a prefix of the query.

Scanning one text for many patterns at once uses a trie of the patterns plus one extra pointer per node. The failure link of a node points to the node for the longest proper suffix of that node's string that is itself a prefix of some pattern. When the automaton has no edge for the next input symbol, it follows failure links until an edge exists or it reaches the root, and it never rewinds the input.

Aho and Corasick showed in 1975 that the resulting machine reports every occurrence of every pattern in O(t + z) time for text length t and z matches, after O(Σm) preprocessing over the total pattern length, independent of how many patterns there are. ClamAV matches its signature set with an Aho-Corasick automaton in libclamav/matcher-ac.c, and Snort's detection engine uses the same construction for multi-pattern rule matching.

A hash table lookup is often described as O(1) against a trie's O(m), and for string keys that comparison is wrong. Hashing a key of length m reads all m bytes, and a successful probe then compares the full key to confirm the match, so the hash path also touches Θ(m) bytes. What differs is the access pattern: the hash table reads the key twice in two contiguous runs, while the trie reads it once but chases a pointer per level, which is a potential cache miss per level.

The trie earns its place on what a hash table cannot do at all: ordered iteration, range and prefix queries, longest-prefix match, and a worst case that does not degrade under adversarial keys, since there are no collisions to force. It gives those up in exchange for higher per-node overhead and pointer chasing. Where only exact membership is needed and order is irrelevant, a hash table or a Bloom filter in front of one is the smaller structure.

A trie gives O(m) lookup, insertion, and deletion in the key length with no dependence on the number of keys, prefix enumeration in output-sensitive time, longest-prefix match in one descent, sorted iteration for free, and no hash function or collision policy to tune. Shared prefixes are stored once, which for URL sets, IP prefixes, and dictionary words removes a large fraction of the redundancy in the raw key set.

The costs are memory and locality. An uncompressed trie over a wide alphabet spends most of its space on null child slots, and every level of descent is a dependent load that the prefetcher cannot anticipate. Path compression, level compression, and adaptive nodes each recover part of that, at the price of a more complicated node format, a rebalancing or promotion step on update, and code that is substantially harder to get right than the array-of-children version.

The Linux kernel stores the IPv4 forwarding information base as an LC-trie in net/ipv4/fib_trie.c, replacing the earlier hash-based table; the kernel's own documentation cites Nilsson and Karlsson for the construction, and the structure serves every longest-prefix-match route lookup the host performs. Redis keeps a radix tree implementation, rax, in src/rax.c and uses one radix tree per stream keyed by entry ID, one for the consumer group's global pending-entries list, one per consumer, and one mapping client IDs to client structures for key-invalidation tracking.

Apache Lucene stores its term dictionary as a finite state transducer over the sorted terms, with the block-tree writer grouping 25 to 48 terms per block and the FST acting as the in-memory index into those blocks; a 10-million-document Wikipedia index with 9.8 million distinct terms compiles to a 69 MB FST. DuckDB builds an adaptive radix tree for every index it creates, using it both to enforce primary-key and unique constraints and to serve equality and range filters, with a persistence format that writes the ART to disk rather than rebuilding it on load. Signature scanners take the automaton route: ClamAV and Snort both match their pattern sets with Aho-Corasick tries.

A trie makes each key a path over the alphabet, so lookup, insertion, and deletion cost O(m) in the key length and never depend on how many keys are stored. Shared prefixes are stored once, the subtree under any node is exactly the set of keys with that prefix, and a single descent that remembers the last terminal node answers longest-prefix match.

The price is per-node overhead and a dependent memory access per level. Path compression removes single-child chains and bounds internal nodes at n − 1, level compression trades memory for depth where branching is dense, and adaptive node types size each node to its actual child count. Those three transformations are what separate the textbook trie from the ones running in kernels, search indexes, and database engines.