34.6 Trie or prefix index?

Step 5: Deep dives (10 minutes)

A trie (Chapter 19) stores queries letter by letter; every prefix is a node. To serve "dat", walk d → a → t, then you'd need the top 5 queries below that node. Walking the subtree per request is far too slow for "d", which has the largest subtree and the most traffic.

The fix: store the top 5 at every node, computed when the trie is built. Then a request is: walk to the node, return its stored list. And once each node carries its answer, you don't need the tree at serving time at all: a flat table from prefix string to its top 5 is the same data, and it fits any key-value store, shards easily by prefix, and caches perfectly.

Figure: precompute the answer for every prefix; serving becomes a single lookup.

In the chapter's code, a trie with top-5 at each node and a flat prefix table built from the same search log return identical suggestions for every prefix tested; the table has about 32,000 prefixes for 20,000 distinct test queries.

Our pick: build with whatever is convenient offline (a trie, or a batch job emitting prefix → query pairs), serve from a flat prefix table in an in-memory KV store, sharded by prefix. Watch for hot shards: one-letter prefixes are tiny in number but huge in traffic, so cache them everywhere (34.9).

Memory code: "Store the answer at every prefix; then the tree can stay at home."