← All concepts
Scale & distribution
Tries & prefix search
Store strings by their prefixes so 'top suggestions for what the user has typed so far' is one lookup.
Autocomplete must respond on every keystroke. A trie maps each prefix to its children; storing the top-k completions at each node makes a lookup a single walk down the prefix, with no ranking at query time.
See it in action
Play with the idea, then follow it through a real architecture.
Try it: type a prefix
Each letter is one step down the trie. The node you land on already stores its top completions.
root→s→ychildren:
snmTop completions stored at “sy” (6 queries below this node)
- system design120 searches
- system90 searches
- sync70 searches
Laying out diagram…
1/2The user types 'sys'.
- Search box
- — Sends the prefix as you type
- Suggestion service
- — One lookup per keystroke
- Trie shards
- — Top-k completions stored at each prefix
- Query log
- — What people searched
- Trie builder
- — Rebuilds tries daily
How it works
- Build tries offline from query logs, weighting by frequency and recency.
- Shard by prefix range and keep hot prefixes in an in-memory cache.
- Refresh periodically; blend in trending queries from a stream.
Trade-offs
- Memory-hungry; precomputed top-k lists lag behind sudden trends.