Autocomplete with tries and precomputed top results
Updated Nov 10, 2026 · 3 min read
Autocomplete shows the most popular searches that start with what you’ve typed so far, and it has to keep up with your fingers. That means an answer in well under 100 ms, for every letter, for everyone typing at once. The trick is to do almost all the work before anyone types.
The trie
A trie, or prefix tree, stores strings one letter per level. The root has a child for each first letter, “p” has a child for each letter that follows it, and so on. Finding everything that starts with “pi” means taking two steps down. The path you walk depends only on how much was typed, not on how many queries exist.
Precompute the top results
Finding the node is quick. Finding the 5 most popular queries below it is not, because below a short prefix like “pi” sit millions of queries. Walking them all per keystroke is far too slow. So each node stores its own top 5, worked out ahead of time. A request walks to the node and reads the list, with nothing to search or sort.
The same idea works without a tree. Many systems keep a key-value store from every prefix to its top 5. Either way, the expensive ranking happens once, offline, instead of on every request.
How much traffic every keystroke makes
Each letter typed can be a request, so autocomplete gets several times the traffic of search itself. Take 500 million searches a day, with 8 letters typed per search.
500,000,000 × 8 = 4,000,000,000 requests a day
÷ 86,400 s ≈ 46,000 requests/s on averageMost of those requests don’t need to happen, so the client and the network do a lot of the work.
| Technique | What it saves |
|---|---|
| Debounce | Wait until typing pauses for about 100 ms, so a quick burst of letters sends one request |
| Browser cache | Backspacing to a prefix you already saw shows its answer without asking |
| Edge cache | Short, popular prefixes are the same for everyone, so a CDN can answer them for a few minutes |
| Cancel stale requests | A slow answer for “pi” can’t overwrite the answer for “piz” |
Rebuilding offline
Popularity changes slowly, so the trie is rebuilt in batches, not updated live. Updating it on every search would turn a structure that’s read tens of thousands of times a second into one that’s also written constantly, and every write would re-sort the top 5 lists all the way up its path.
- Collect the last week of search logs.
- Count how often each query was searched, dropping anything offensive or too rare.
- Build a new trie and store the top 5 at every node.
- Save it as a snapshot file.
- Each server loads the snapshot and swaps it in all at once, so nobody reads a half-built trie.
Keeping it fresh
A weekly build misses the news. When a storm gets a name at noon, people want it suggested by 12:05. Count the last hour of searches separately, in a small fast store, and merge any trending query that matches the prefix into the weekly results at request time. Weight it so one noisy hour can’t push out a week of steady favorites.
How big it gets
Storing the top 5 everywhere costs memory. If each node holds 5 pointers of 8 bytes plus about 60 bytes for its letter, children and counts, that’s about 100 bytes a node. A billion nodes is about 100 GB. That can fit in one large server’s memory, and many deployments simply give every server a full copy.
Splitting it
Once the tries outgrow one server, for example with dozens of languages, they have to be split. Splitting by first letter is the obvious choice and a poor one, because far more searches start with “s” or “c” than with “x” or “q”. Instead, cut the prefix space into ranges sized by measured traffic. A busy letter might get a shard to itself, while quiet ones share. Every prefix still lives on exactly one shard, so a lookup is still one hop, and busy shards get extra replicas.