The prefix problem
Autocomplete must, on every keystroke, find the best completions for the text typed so far. Running a full search per keystroke is wasteful. A trie, or prefix tree, solves this directly.
How a trie works
Each node represents one character, and a path from the root spells a prefix. Walking down the tree by the typed characters lands on the node for that prefix in time proportional to the prefix length, not the number of phrases stored.
- Children of that node spell the possible completions.
- Storing a weight at terminal nodes lets you return the most popular suggestions first.
Practical refinements
- A plain trie can be large, so engines often use a compressed form or a finite state structure that merges shared suffixes.
- Precomputing the top completions at each node avoids scanning the whole subtree on every keystroke.
- Latency matters because suggestions fire on every keypress, so these structures usually live in memory.
Key idea
A trie indexes phrases by shared prefixes so autocomplete finds completions in time proportional to the prefix length, with weights ranking popular suggestions.