← All articles

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.

Rootptop 5pitop 5patop 5pintop 5
Every node keeps the top 5 queries below it, so answering “pi” is two steps and a read.

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 average

Most of those requests don’t need to happen, so the client and the network do a lot of the work.

TechniqueWhat it saves
DebounceWait until typing pauses for about 100 ms, so a quick burst of letters sends one request
Browser cacheBackspacing to a prefix you already saw shows its answer without asking
Edge cacheShort, popular prefixes are the same for everyone, so a CDN can answer them for a few minutes
Cancel stale requestsA 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.

  1. Collect the last week of search logs.
  2. Count how often each query was searched, dropping anything offensive or too rare.
  3. Build a new trie and store the top 5 at every node.
  4. Save it as a snapshot file.
  5. 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.