Autocomplete turns a half-typed query into a finished thought. Behind the suggestion dropdown is usually a trie: a tree-shaped index that finds every stored string sharing a prefix in time proportional to the prefix length, not the collection size.
How a trie works
Each node in a trie represents one character, and each path from the root spells a stored string. To find completions for 'neur', you walk four edges down from the root, then collect everything in the subtree: 'neural', 'neural network', 'neuron', and so on. No scanning, no scoring — just pointer chasing.
function insert(root, phrase) {
let node = root;
for (const ch of phrase) {
node.children = node.children || {};
node.children[ch] = node.children[ch] || { count: 0 };
node = node.children[ch];
node.count += 1;
}
node.phrase = phrase;
}
Store a popularity count at each node so suggestions can be ranked by frequency rather than alphabetically.
What to index for suggestions
Good autocomplete indexes phrases users actually want, not raw vocabulary:
- Past questions and popular queries from your own logs.
- Topic titles from the knowledge base.
- Canonical entity names recognized by entity matching.
Cap the collection at a few thousand phrases. Beyond that, suggestion quality depends more on ranking than coverage, and the trie stays small enough to build at load time.
Ranking suggestions
Collect up to a few dozen subtree matches, then rank them:
- Exact-prefix frequency: phrases users picked before rank first.
- Shorter completions before longer ones at equal frequency.
- Recency boost for the current session's topics.
Return the top five to eight. Long dropdowns slow users down instead of speeding them up, and every extra row costs rendering latency on low-end devices.
Tries versus full search
Autocomplete and document search solve different problems. A trie answers 'which known phrases start with this prefix?' while an inverted index answers 'which documents contain these terms?' Use the trie for the live dropdown as the user types, then run full BM25 retrieval when they submit. The two structures complement each other.
Handling typos in prefixes
Strict tries fail on the first mistyped character. For typo-tolerant suggestions, combine the trie with edit-distance matching: if a prefix has no subtree, retry with one-character edits before giving up. One level of fuzziness catches most slips without noticeably slowing the dropdown.
Performance notes
A trie of 5,000 phrases uses well under a megabyte and answers prefix lookups in microseconds. Build it once from a JSON phrase list, or persist it in IndexedDB alongside your search index. Debounce input by 100 to 150 milliseconds so fast typists trigger one lookup per pause instead of one per keystroke.