AI InterviewSearch…Search problems, topics, or pages…Ctrl KGet started
Skip to content
SD notes

System Design · Note 22 of 22

Design Search Autocomplete (Typeahead)

Intermediate · 7 min read · updated 14 November 2026

Quick answer

How do you design a search autocomplete system?

Store popular queries in a trie and keep, at every prefix node, the top few queries below it ranked by frequency. A keystroke walks one node down and returns that stored list. An offline pipeline aggregates query logs, rebuilds the trie periodically and swaps it onto replicated, cached servers, sharded by prefix when it outgrows one machine.

On this page
  1. Requirements
  2. The trie
  3. Top k at every node
  4. Serving a keystroke
  5. Data collection and rebuild
  6. Scaling it
  7. Interview questions
  8. Common questions

Autocomplete suggests whole queries while the user types. It is read-heavy, latency-critical (every keystroke) and tolerant of slightly stale results.

Requirements

  • Functional: given a prefix, return the top 5–10 queries; ranked by popularity.
  • Non-functional: fast enough to keep up with typing, so the latency target is agreed up front; highly available; suggestions may lag new trends a little.
  • Scale: one request per keystroke, so several requests per search — estimate it with back-of-the-envelope numbers.

The trie

  • One node per character; queries sharing a prefix share its path.
  • A node that ends a query keeps its count (how often it was searched).
A trie built from search queries and their counts

Insert "to" (searched 50 times): one node per letter, and the last node marks a complete query with its count.

0:01 / 0:15Step 1 of 7
Transcript · 7 steps

Top k at every node

  • Each node stores its top k queries below it.
  • Built bottom-up: a node merges its own query with its children's lists.
  • Costs memory; buys a lookup with no subtree scan.
Top 3 suggestions stored at every prefix

Each node stores its top 3 queries so a lookup never scans a subtree. "tre" has one query below it: tree 40.

0:01 / 0:11Step 1 of 4
Transcript · 4 steps

Serving a keystroke

  • Walk one node per typed character, return the stored list.
  • Cost grows with the prefix length, not with how many queries it matches.
  • Debounce in the client, and cache short prefixes — they are the hottest.
Typing "tree": one trie step per keystroke

The user types "t". The service steps one node down from the root and returns the list stored there: to, tree, try.

0:01 / 0:11Step 1 of 4
Transcript · 4 steps

Data collection and rebuild

  • Every search is logged, off the serving path.
  • An aggregator counts queries per window; old windows may weigh less.
  • A builder makes a new trie periodically; replicas swap to it one at a time.
  • The serving trie is read-only: no locks on the hot path.
Logs → counts → new trie → replicas

Every search is logged. While the serving trie (v1) still offers tree 40, try 36, trie 25 for "tr", new queries pile up in the logs.

0:01 / 0:14Step 1 of 5
Transcript · 5 steps

Scaling it

  • Replicas of the trie for read throughput; a load balancer in front.
  • Caching: browser and CDN for popular prefixes, a cache beside the service.
  • Sharding by prefix: ranges like a–ap, aq–c, sized by traffic, not by letter.
  • Filtering: a blocklist for unsafe queries, applied before results leave.
  • Personal or trending results: blended from a smaller, faster path.

Interview questions

  • Why a trie and not a database LIKE query? A LIKE 'pre%' query ranks matches on every request; a trie with stored top k answers in a walk and a read.
  • How do you rank suggestions? By search frequency over a recent window, then adjusted by freshness, personalisation and filters.
  • How do new trends appear? At the next rebuild; for faster trends, a short-window counter blended into the results.
  • How do you shard? By prefix range, with busy prefixes split further so each shard has similar traffic.

Next: back to System Design · Before this: Design a Web Crawler

Common questions

What data structure is used for autocomplete?

A trie (prefix tree): each node is one character, so every query sharing a prefix shares the path to it. Storing the top suggestions at each node turns a lookup into a walk of the prefix's length plus one read.

Why store the top-k suggestions at every trie node?

Without them, a short prefix like "t" would need a scan of its whole subtree on every keystroke. Precomputing the lists offline costs memory but makes each lookup fast and predictable.

How are autocomplete suggestions ranked?

Commonly by how often the query was searched over a recent window, often weighted towards recent days. Real systems add signals such as personal history, location and freshness, and filter out unsafe or unwanted queries.

How often is the autocomplete trie updated?

It is usually rebuilt periodically from aggregated logs — hourly, daily or weekly depending on how fresh suggestions must be — rather than updated on every search. Trending topics can be handled by a smaller, faster path.

How do you scale an autocomplete service?

Replicate the trie for read throughput, cache responses for popular prefixes at the edge or in the browser, and shard by prefix when the trie no longer fits one machine, splitting busy prefixes further so shards carry similar load.

AI InterviewGet started

Design Search Autocomplete (Typeahead System Design)

Design a search autocomplete system: a trie with top-k suggestions per prefix, ranking by frequency, the offline rebuild pipeline, caching and sharding.

  • Subject: System Design
  • Level: Intermediate
  • Reading time: 7 min
  • Updated: 2026-11-14

How do you design a search autocomplete system?

Store popular queries in a trie and keep, at every prefix node, the top few queries below it ranked by frequency. A keystroke walks one node down and returns that stored list. An offline pipeline aggregates query logs, rebuilds the trie periodically and swaps it onto replicated, cached servers, sharded by prefix when it outgrows one machine.

Autocomplete suggests whole queries while the user types. It is read-heavy, latency-critical (every keystroke) and tolerant of slightly stale results.

Requirements

  • Functional: given a prefix, return the top 5–10 queries; ranked by popularity.
  • Non-functional: fast enough to keep up with typing, so the latency target is agreed up front; highly available; suggestions may lag new trends a little.
  • Scale: one request per keystroke, so several requests per search — estimate it with back-of-the-envelope numbers.

The trie

  • One node per character; queries sharing a prefix share its path.
  • A node that ends a query keeps its count (how often it was searched).
toreeypieyueto 50tree 40try 36top 35trie 25toy 20true 15
A trie built from search queries and their counts.
  1. Insert "to" (searched 50 times): one node per letter, and the last node marks a complete query with its count.
  2. Insert "tree" (40): it walks 1 existing node ("t") and adds 3 new.
  3. Insert "try" (36): it walks 2 existing nodes ("tr") and adds 1 new.
  4. Insert "top" (35): it walks 2 existing nodes ("to") and adds 1 new.
  5. Insert "trie" (25): it walks 2 existing nodes ("tr") and adds 2 new.
  6. Insert "toy" (20): it walks 2 existing nodes ("to") and adds 1 new.
  7. "true" reuses 2 nodes and adds 2. 7 queries share one trie of 12 nodes: a common prefix is stored once.

Top k at every node

  • Each node stores its top k queries below it.
  • Built bottom-up: a node merges its own query with its children's lists.
  • Costs memory; buys a lookup with no subtree scan.
toto 50reetree 40ytry 36ptop 35ietrie 25ytoy 20uetrue 15stored at "t"to · 50tree · 40try · 36
Top 3 suggestions stored at every prefix.
  1. Each node stores its top 3 queries so a lookup never scans a subtree. "tre" has one query below it: tree 40.
  2. "tr" merges its children's lists ("tre", "tri", "tru", "try") and keeps the best 3: tree 40, try 36, trie 25.
  3. "to" merges its own query with its children's lists ("top", "toy") and keeps the best 3: to 50, top 35, toy 20.
  4. "t" merges "to", "tr" and keeps to 50, tree 40, try 36. The lists are built offline, bottom-up; at query time they are only read.

Serving a keystroke

  • Walk one node per typed character, return the stored list.
  • Cost grows with the prefix length, not with how many queries it matches.
  • Debounce in the client, and cache short prefixes — they are the hottest.
toreeypieyuetree|tree
Typing "tree": one trie step per keystroke.
  1. The user types "t". The service steps one node down from the root and returns the list stored there: to, tree, try.
  2. "tr": one more step down, a new stored list — tree, try, trie. No ranking happens while the user waits.
  3. "tre": one more step down, a new stored list — tree. No ranking happens while the user waits.
  4. "tree" is a whole query; its node offers tree. Each keystroke cost one step and one read, however many queries share the prefix.

Data collection and rebuild

  • Every search is logged, off the serving path.
  • An aggregator counts queries per window; old windows may weigh less.
  • A builder makes a new trie periodically; replicas swap to it one at a time.
  • The serving trie is read-only: no locks on the hot path.
Query logsAggregatorTrie builderReplica 1 · v2Replica 2 · v2v2 — "tr" suggeststry 41tree 40trie 26
Logs → counts → new trie → replicas.
  1. Every search is logged. While the serving trie (v1) still offers tree 40, try 36, trie 25 for "tr", new queries pile up in the logs.
  2. A periodic job aggregates the window: try +5, toy +1, trie +1, true +1. Counting offline keeps writes off the serving path.
  3. The window is added to the stored counts and the builder makes a new trie, v2, recomputing every node's top 3.
  4. Replica 1 swaps to v2 while replica 2 keeps serving v1, so suggestions never stop. In v2, "tr" offers try 41, tree 40, trie 26.
  5. Both replicas serve v2. "try" overtook "tree" — suggestions follow what people search, one rebuild behind.

Scaling it

  • Replicas of the trie for read throughput; a load balancer in front.
  • Caching: browser and CDN for popular prefixes, a cache beside the service.
  • Sharding by prefix: ranges like a–ap, aq–c, sized by traffic, not by letter.
  • Filtering: a blocklist for unsafe queries, applied before results leave.
  • Personal or trending results: blended from a smaller, faster path.

Interview questions

  • Why a trie and not a database LIKE query? A LIKE 'pre%' query ranks matches on every request; a trie with stored top k answers in a walk and a read.
  • How do you rank suggestions? By search frequency over a recent window, then adjusted by freshness, personalisation and filters.
  • How do new trends appear? At the next rebuild; for faster trends, a short-window counter blended into the results.
  • How do you shard? By prefix range, with busy prefixes split further so each shard has similar traffic.

Next: back to System Design · Before this: Design a Web Crawler

Common questions

What data structure is used for autocomplete?

A trie (prefix tree): each node is one character, so every query sharing a prefix shares the path to it. Storing the top suggestions at each node turns a lookup into a walk of the prefix's length plus one read.

Why store the top-k suggestions at every trie node?

Without them, a short prefix like "t" would need a scan of its whole subtree on every keystroke. Precomputing the lists offline costs memory but makes each lookup fast and predictable.

How are autocomplete suggestions ranked?

Commonly by how often the query was searched over a recent window, often weighted towards recent days. Real systems add signals such as personal history, location and freshness, and filter out unsafe or unwanted queries.

How often is the autocomplete trie updated?

It is usually rebuilt periodically from aggregated logs — hourly, daily or weekly depending on how fresh suggestions must be — rather than updated on every search. Trending topics can be handled by a smaller, faster path.

How do you scale an autocomplete service?

Replicate the trie for read throughput, cache responses for popular prefixes at the edge or in the browser, and shard by prefix when the trie no longer fits one machine, splitting busy prefixes further so shards carry similar load.

← Design a Web Crawler