Tries and Radix Trees

A trie stores keys by their characters. The path from the root spells the key, and every node stands for a prefix: the node reached by following l and then e stands for "le", whether or not "le" is itself a key. Finding a key costs one step per character, however many keys the trie holds.

Finding every key with a given prefix costs one descent to that prefix's node, and everything below it is an answer. That is what a search box needs on every keystroke and what an internet router needs for every packet. It pays in memory, a node per character with pointers in each, and the radix tree exists to pay less of it.

Keys as Paths

Each edge carries one character. Each node stands for the prefix spelled on the way down to it, and a node is marked when that prefix is a complete key. A trie holding le, lea, lee, leg and guin has one path that spells l, e and then branches three ways, and a second path that spells g, u, i, n with no branches at all.

A lookup walks one edge per character, so its cost is O(length of the key) and does not grow with the number of keys. It never compares two whole keys. Where a search tree compares the query with a stored key at every level, a trie reads each character of the query once and uses it to choose an edge.

Prefix Search

To find every key that starts with a prefix, descend to the prefix's node; the whole subtree below it is the answer. Lantern's autocomplete fires on every keystroke after the second character, so typing a twelve-letter title word sends ten requests. The node for le sits above thousands of terms. In an English word list of 234,456 words, 1,210 start with le, and Lantern's 1.5 million terms, with every author and subject among them, have more.

So the descent is cheap and the enumeration is the real cost, paid on every keystroke. The standard fix is to store each node's ten most popular completions when the index is built at 02:00. It is Chapter 1's time-space trade again, built with the top-k heap of the previous topic: a heap of ten per node, computed once a night, so that a keystroke costs a descent and one read.

The Memory Bill

A shared prefix is stored once, which sounds like a saving. But every node pays for its own object and its own table of child pointers, and a key contributes a node for every character it does not share. Measured on Python 3.15, a trie of the 234,456-word list, built with one small object and one dict per node, has 758,897 nodes, about 3.2 per word, and occupies 154 megabytes: about 200 bytes per node to hold 2.2 megabytes of text.

Scale that to Lantern. At the same rate, 1.5 million terms make about 5 million nodes and about a gigabyte of memory, more than half the size of Lantern's entire 1.8 GB index file and an eighth of its 8 GB server, to hold terms whose text is around 15 megabytes. Library terms, full of names and numbers, share prefixes less than dictionary words do, so the real figure would be higher. A naive trie saves characters and spends pointers.

Radix Trees

Most trie nodes have exactly one child. In the word-list trie above, 62 percent do. A radix tree, also called a Patricia tree after Donald Morrison's 1968 design, merges every chain of single-child nodes into one edge labelled with a string. The chain g, gu, gui, guin becomes a single edge labelled guin.

Every remaining node either branches or ends a key, so a radix tree over n keys has fewer than 2n nodes. The word-list trie shrinks from 758,897 nodes to 314,480, and a lookup now takes a step per branching point rather than per character. The behaviour is identical: the same keys, the same prefix queries, the same answers.

Longest-Prefix Match in IP Routing

A router's forwarding table maps address prefixes to next hops. It might hold a route for every address that begins with 10, a more specific route for addresses beginning with 10.1, and a default route for everything else. Prefixes overlap, and every packet must go to the longest prefix that contains its destination, so a packet for 10.1.2.3 takes the 10.1 route even though the 10 route also matches.

Prefix	Next hop	Contains 10.1.2.3?
0.0.0.0/0 (default)	upstream	yes, 0 bits
10.0.0.0/8	router A	yes, 8 bits
10.1.0.0/16	router B	yes, 16 bits: chosen
10.2.0.0/16	router C	no

A binary trie answers this directly. Walk the destination address bit by bit, remembering the last marked node passed on the way down; when the path ends, the last marked node is the longest matching prefix. For an IPv4 address that is at most 32 steps. The Linux kernel's IPv4 routing table is a compressed trie of this kind, a level-compressed trie. How the table gets filled belongs to Networking Deep Dive.

Choosing a Structure for Autocomplete

A hash table (Chapter 5) cannot answer a prefix query at all, because hashing scatters "le", "lea" and "leg" to unrelated slots. A sorted array of terms can: every term starting with le sits in one contiguous run, and two binary searches find the run's ends, one for le and one for the first possible term after it. The measured word list takes 13.7 megabytes as a sorted Python list of strings, an eleventh of the trie's 154.

A trie earns its memory when queries are many and short, when answers can be precomputed per node, or when a second feature walks the same structure, as Lantern's typo tolerance does in Chapter 9. Autocomplete sends several requests for every search typed, so at the Saturday peak of 300 searches a second it is Lantern's busiest code path. The radix tree's smaller footprint is what lets that structure stay in RAM beside the index.