Suggestions as you type
Typeahead shows likely completions while a user types a query. Each keystroke fires a lookup that must return the best matches in milliseconds, so the design favors precomputed structures over live scans.
The prefix tree
The core structure is a trie, a tree where each path spells a prefix. From a prefix node you can reach all completions that start with it. Tries make prefix lookup fast.
To rank suggestions, each node stores the top completions for its prefix, precomputed by popularity, so a lookup returns ready ordered results instead of scanning the subtree.
Serving and updates
- Tries for popular prefixes are kept in memory and often cached at the edge.
- Suggestions are ranked by frequency, recency, and personalization.
- The trie is rebuilt or updated from query logs on a schedule, since new trends emerge.
Cutting cost
- The client debounces, waiting a moment between keystrokes so it does not query on every letter.
- Results are cached by prefix so common prefixes are nearly free.
Key idea
Typeahead serves ranked completions per keystroke from an in memory trie that stores precomputed top results per prefix, with debouncing and caching to keep latency low.