Section 8: The Answer Is Already Written Down - Deep Dive: The Prefix Index
Executive Summary: The origin has 10 ms (N14) to answer "the top 10 completions of this prefix", and the lookup must take well under a millisecond. The answer is to rank before anyone asks: an in-memory radix trie with the top 15 completions stored at every node, so a lookup is a prefix walk plus one short list. This section picks it over six rivals, sizes it at ~20 GB, builds it in one pass, and swaps each daily snapshot in atomically behind a canary.
The interviewer taps the suggestion service on your Section 6 diagram. "Maya's phone sends chicago mara. What happens inside this box?"
"Less than you'd expect, on purpose. The answer for chicago mara was written down before she typed it. The service only has to find it."
Choosing the Structure
| Candidate | Lookup cost | Verdict |
|---|---|---|
SQL LIKE 'prefix%' + ORDER BY score |
Scans every match: millions for a |
Rejected: work grows with prefix popularity |
| Plain trie, top-K by walking the subtree at query time | O(prefix) + the whole subtree | Rejected: same flaw, in RAM |
| Plain trie, top-K stored at every node | O(prefix) + one list | Right idea, wasteful shape: a node per character |
| Radix trie, top-15 at every node | O(prefix) + 15 ids | Chosen (D1): ≤ 200M nodes, ~20 GB |
| Prefix → top-K in a remote KV store (Redis) | A network hop per keystroke | Rejected: over a billion keys, and a hop inside a 10 ms budget |
| Sorted array + binary search | O(log n) to find the range, then top-K over it | Rejected: needs a range-max structure on top to avoid a scan |
| FST (Lucene / Elasticsearch completion suggester) | Very compact (prefix and suffix sharing); top-N found by a weighted best-first search at query time | Good at smaller scale; at 400K QPS, cluster and JVM overhead per query, and the trending and blocklist merge needs a second query or a plugin |
"Anything that ranks at query time pays in proportion to how many queries share the prefix, and the hottest prefixes are the shortest. So I precompute, on the cheapest shape: the radix trie collapses single-child chains into multi-character edges."
Key Insight: A prefix that ends mid-edge has exactly the completions of the node at the edge's end, because every stored string that continues past that point must run along the rest of the edge. So compression loses nothing: top-K is needed per node, never per character.
Quick check before moving on:
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson