Search & Ranking Systems • Search Autocomplete (Trie)Easy⏱️ ~2 min
What is a Trie and Why Autocomplete Uses It
A trie (prefix tree) is a specialized data structure that stores strings by sharing common prefixes across branches. When you type "sea" into Google search, the trie walks three pointers (s→e→a) in O(P) time where P is the prefix length, regardless of how many millions of words are stored. This predictable traversal cost is why tries dominate autocomplete: you get instant prefix matching without scanning the entire dictionary.
The key advantage over sorted arrays or hash tables is structural. A sorted array requires binary search (O(log N)) to find prefix bounds, then scanning to collect matches. Hash tables cannot efficiently enumerate all strings sharing a prefix without storing explicit prefix keys. A trie naturally clusters all "sea" words under one subtree, making enumeration trivial.
Production tries augment basic nodes with metadata to avoid full subtree walks. Each node stores an end flag (is this a complete word?), frequency counters, and crucially, a precomputed list of the top K completions in its subtree. When you query "sea", the system walks to that node in O(P) time, then returns the cached top K list in O(K) time with no further traversal. Google and Amazon use this pattern to keep autocomplete latency under 5 milliseconds for hot prefixes.
The tradeoff is memory. A naive character per node trie consumes multiple bytes per character due to pointer overhead and child node arrays. A 500,000 word English dictionary can balloon to 500 to 900 MB in a simple implementation. Production systems use compressed variants like Directed Acyclic Word Graphs (DAWGs) or Finite State Transducers (FSTs) to cut memory by three to ten times through suffix deduplication and compact transition encoding.
💡 Key Takeaways
•Trie traversal is O(P) where P is prefix length, independent of dictionary size. Typing a three character prefix walks three pointers regardless of whether you have 1,000 or 10 million words.
•Production nodes cache top K completions per prefix to achieve O(P + K) query time. Google search returns suggestions in under 5 ms by avoiding full subtree traversals for hot prefixes.
•Memory overhead is the primary constraint. A 500,000 word English dictionary consumes 500 to 900 MB in naive implementations due to pointer overhead and child arrays per node.
•Compressed tries like DAWGs and FSTs reduce memory by three to ten times through suffix deduplication and compact transition tables, critical for multilingual corpora with millions of entries.
•Tries beat sorted arrays for prefix enumeration. Binary search on sorted arrays is O(log N) to find prefix bounds, then O(K) to scan matches, with no efficient way to maintain per prefix ranking without recreating trie like indexes.
📌 Examples
Google autocomplete: User types "goo", trie walks three nodes in microseconds, returns cached ["google", "google maps", "google translate", "good morning", "google docs"] precomputed from billions of queries.
Amazon product search: Typing "lapt" traverses four nodes, each node stores top 10 products by purchase frequency and availability, returns suggestions in 3 to 8 ms server side before network latency.
Uber location autocomplete: Prefix "san fr" walks six characters, node caches top 5 places sorted by distance from user and search popularity, achieving sub 10 ms P95 latency on hot city prefixes.