System Design › High-Level Design

Design Typeahead / Search Autocomplete — System Design

Design search autocomplete end to end: why the trie (prefix tree) is the right data structure, precomputing top-k suggestions at each node, the offline log-aggregation pipeline, in-memory serving, caching and sharding.

Shiv Pandey

Oct 10, 2026 | 214 views

Design Typeahead / Search Autocomplete — System Design

🟠 High-Level Design · Senior → 🔴 the trie deep dive

Start typing in Google's search box and it instantly suggests completions, ranked by popularity, before you've finished the word. That's typeahead (autocomplete / search suggestions), and "design it" is a favourite interview because it forces a specific, elegant data structure — the trie — and a real trade-off between fresh results and blazing speed. Let's design it end to end.

The whole design in one line: store popular search phrases in a trie (prefix tree) with the top suggestions precomputed at each node, so that as the user types a prefix you jump to that node and return its ready-made top-k list in a couple of milliseconds.

Step 1 — Requirements

Functional: given a prefix the user is typing, return the top ~5–10 most popular matching suggestions; update as they type each character.
Non-functional: extremely low latency — suggestions must appear within ~100 ms or they're useless; it's massively read-heavy (every keystroke is a query); results can be slightly stale (a suggestion list that's an hour old is fine).

🟠 That "slightly stale is fine" point is the key that unlocks the whole design — it lets us precompute.

Step 2 — The naive approach (and why it fails)

You could run a database LIKE 'prefix%' query on every keystroke. But that's a scan, it's slow, and you'd do it billions of times a day across all prefixes — far too expensive and too slow for a per-keystroke budget. We need a structure built specifically for prefix lookups.

Step 3 — The trie

🔴 A trie (prefix tree) stores strings by their characters: each node is a character, and a path from the root spells out a prefix. All words starting with "ca" live under the root → c → a subtree. To find completions for a prefix, you walk down the tree following the prefix's characters, then everything below that node is a match.

🔴 But walking the whole subtree per keystroke to rank matches is still too slow. The crucial optimisation: precompute and cache the top-k suggestions at each node. The "ca" node directly stores ["cat", "car", "cap"] already sorted by popularity. Now a lookup is: walk to the prefix node (fast), return its stored list (instant). No subtree traversal, no sorting at query time. That precomputation is what makes typeahead feel instant.

Step 4 — Where do the suggestions and rankings come from?

🟠 Popularity comes from real search logs. This is a classic offline / online split:

Offline (data pipeline): aggregate query logs — count how often each phrase was searched — over some window. A batch job then builds the trie with the top-k precomputed at every node, and ships it to the serving layer.
Online (serving): the read path just does trie lookups against that prebuilt structure. Fast and simple.

Because we accept slight staleness, we rebuild/refresh the trie periodically (say hourly) rather than updating it on every search — trading perfect freshness for huge speed and simplicity. That's the trade the requirements permit.

Step 5 — Serving & scale

Keep the trie in memory on the serving nodes — RAM-speed lookups are what hit the ~100 ms budget (and each lookup touches memory, ~100 ns, not disk).
Cache hot prefixes at the edge/CDN; a small set of prefixes ("f", "fa", "fac"…) get the vast majority of traffic.
Sharding: the full trie can be large, so shard it by first letter(s) — the "a*" subtree on one set of servers, "b*" on another — and route the request to the right shard.
Debounce on the client: don't fire a request on every keystroke; wait a few tens of ms so fast typers make fewer calls.

Step 6 — Nice extras

🔴 Senior touches: handle typos (fuzzy matching / edit distance), personalise suggestions with user/context signals layered on top of global popularity, and filter inappropriate or trending-abuse terms. These build on the same trie + ranking foundation.

The interview-ready walkthrough

"Autocomplete needs sub-100ms responses on a read-heavy, per-keystroke workload, and slight staleness is acceptable — so I precompute. I store popular phrases in a trie and cache the top-k suggestions at each node, so a lookup is just 'walk to the prefix node, return its stored list.' Rankings come from an offline pipeline that aggregates search logs and rebuilds the trie hourly. I keep the trie in memory, cache hot prefixes at the edge, shard by first letters for size, and debounce on the client. Extras: typo tolerance and personalisation." That nails the data structure, the offline/online split, and the latency story."