Tries and autocomplete
How search-as-you-type works at scale: tries and prefix indexes, precomputed top-K suggestions per prefix, ranking by popularity and personalisation, building from query logs, fuzzy matching, latency budgets and client-side tricks.
Reading is half of it. See this used in a real interview: walk through Design Search Autocomplete →
Autocomplete has the tightest latency budget in most products: suggestions must appear while the user is still typing, so the whole round trip needs to fit in roughly 100 ms, and the backend usually gets well under 20 ms. It is also extremely read-heavy: every keystroke is a query. The standard design combines a prefix data structure, precomputed answers, aggressive caching and an offline pipeline that keeps rankings fresh.
The trie
A trie (prefix tree) stores strings character by character: each node is a prefix, and its children extend it by one character. Finding everything that starts with "new y" means walking five nodes and then exploring the subtree.
Walking the whole subtree on every keystroke is too slow for popular prefixes ("a" has millions of completions). The key optimisation:
- Store the top K suggestions at every node (K around 5 to 10), already ranked.
- A lookup becomes: walk to the prefix node, return its stored list. Time depends on the prefix length, not on the data size.
The cost is memory (K entries per node) and more work at build time, which is the right trade for a read-heavy system.
Alternatives to an in-memory trie
| Structure | How it answers a prefix | Notes |
|---|---|---|
| Trie with top-K per node | walk the prefix, read the list | fastest; memory-heavy; usually rebuilt offline |
| Key-value map prefix to top-K | one lookup per prefix | simple to shard and cache; precompute all prefixes up to N characters |
| Sorted list or B-tree range scan | scan keys between "new y" and "new z" | fine for small sets |
| Search engine edge n-grams | index every prefix of each term | flexible matching, more latency; see search and indexing |
| Finite state transducers | compact automaton used by Lucene suggesters | very compact, read-only |
For an interview, "a prefix-to-top-K table, built offline and served from memory" is a clear, defensible design.
Ranking suggestions
What goes in the top K:
- Popularity: query frequency from logs, with time decay so trending queries rise quickly and old ones fade.
- Freshness: a breaking-news term should appear within minutes, not after the nightly rebuild.
- Personalisation: the user's own history and location ("pizza near me" means different places). Usually a small per-user layer merged with the global list at request time.
- Filtering: remove offensive, illegal or spammy suggestions with blocklists. See trust and safety.
Building and updating
- Query logs flow into a stream and a data lake.
- A batch job aggregates counts per query over a window (with decay), filters, and computes top-K per prefix.
- The result is published as a new versioned snapshot; servers load it and swap atomically.
- A streaming layer tracks trending queries over the last minutes and merges them in for freshness.
Counting every query exactly is expensive; count-min sketches or sampling give good enough frequencies. See probabilistic data structures and batch and stream processing.
Serving at scale
- Replicate the whole dataset to every server if it fits in memory (often it does); otherwise shard by prefix (with care: "s" is far bigger than "x", so split by the first two or three characters with a mapping table).
- Cache responses for short prefixes at the CDN or edge, since they are shared by everyone and change slowly.
- Client tricks: debounce keystrokes (send after 50 to 100 ms of no typing), cancel stale requests, and cache results locally so backspacing costs nothing. Some apps prefetch suggestions for the next likely character.
Fuzzy matching and typos
Users mistype. Options: edit-distance matching against a dictionary (expensive, so limit to distance 1 or 2), phonetic keys, or a spelling-correction model that rewrites the prefix before lookup. Most systems first try exact prefix matching and only fall back to fuzzy matching when results are few.
Location-aware autocomplete
For places (maps, restaurants), suggestions depend on where the user is. Combine the prefix index with a geospatial filter or boost, for example top-K per prefix per region cell. See geospatial and proximity, Design Yelp and Design Google Maps.
In the interview
Start from the latency budget and the keystroke-level QPS, propose a prefix-to-top-K structure built offline from query logs with decay, serve it from memory with replication and edge caching, add a streaming layer for trends, and mention debouncing on the client. Walk through it fully in Design Typeahead.
Checklist
- Latency budget and keystroke QPS estimated up front.
- Top-K precomputed per prefix; lookups independent of data size.
- Offline build from logs with time decay; atomic snapshot swaps.
- Streaming layer for trending queries.
- In-memory serving, replication or prefix sharding, edge caching for short prefixes.
- Debounce, cancellation and local caching on the client.
- Blocklists and personalisation as layers on top.