Tries: Why Autocomplete Doesn't Scan Every Word

Google, Slack, and your IDE’s search box serve autocomplete suggestions in under 10 milliseconds, even with billions of indexed terms. The naive approach—scanning a database for every keystroke—is doomed by cardinality. The breakthrough is elegant: structure the dictionary so that every keystroke lands in exactly one subtree, and cache the best answers there.

Left: flat-list matching is O(N·p); right: trie prefix walk is O(p), independent of dictionary size N.

The Naive Approach Dies Fast

Imagine a dictionary of 10 million English words (realistic for a search engine or spell-checker). A user types “car”. Your SQL query reads:

SELECT word FROM dictionary WHERE word LIKE 'car%' ORDER BY popularity DESC LIMIT 10;

The database must:

1. Check every row against the prefix “car” (or scan an index).
2. Return matching rows (e.g., car, card, care, cart).
3. Rank them by frequency.
4. Limit to 10.

This is O(N·p) per keystroke: scan all N words, compare against prefix of length p. On each new character, the query runs again. A user typing “c-a-r-p-e-n-t-e-r” triggers 9 full dictionary scans. At millions of concurrent users, your database is bottlenecked by CPU and IO.

Worse: the cost doesn’t drop as the prefix narrows. After typing “carp”, you’ve still checked millions of words; you just filtered down to 5 candidates.

Enter the Trie: O(p) Regardless of Dictionary Size

A trie (or prefix tree) is a tree where each edge is labeled with a character, and each node represents a prefix. For example, with words {car, card, care, cart, cat, dog}:

        ∅ (root)
       / \
      c   d
     / \   \
    a   t   o
   /|\   \  \
  r e t   \  g
  |/|     (CAT)
  * * *

Here:

• The path c → a → r reaches a node labeled * (terminal), meaning “car” is a word.
• The descendants of c → a → r are {e, t, d} — the suffixes after “car” that form valid words.
• All words starting with “car” are only reachable via the c → a → r path.

Finding all words starting with “car” is now a single tree walk: start at root, follow the edges c, then a, then r. You land on one node. Everything in its subtree is a candidate. Cost: O(p) where p = 3 (the prefix length). The dictionary size is irrelevant.

Radix Tries: Trading Traversals for Memory

The trie above uses one node per character. For long, branching-free chains, this is wasteful. The path c → a → r could be collapsed into a single edge labeled “car”, saving two node allocations:

    ∅ (root)
   / \
  "car" "dog"
  /||\  |
 e t d (DOG)
 | | |
 * * *

This is a radix trie (or compressed trie). Now the tree has 7 nodes instead of 10 for the same vocabulary. Memory savings grow with word length: a chain of 10 characters becomes 1 edge + 1 node instead of 10.

The cost: comparisons. A standard trie compares one character per node; a radix trie compares a whole edge label per node. Modern tries use string comparison (faster than byte-by-byte) and memoization to amortize this.

Real-world savings: A trie over 1 million words compresses to ~12–20 KB with radix compression, vs ~40 KB without. For a mobile app or in-memory database, that margin matters.

Top-k Heaps: Caching the Best Answers

Here’s the trap: after the c → a → r walk, your trie node may have 50,000 descendants (all words starting with “car” in a corpus). Your autocomplete feature returns the top 10 most popular. Traversing 50,000 descendants to find the 10 most frequent is O(N log k) per query — back to scanning, just a smaller set.

Solution: cache a top-k heap at each trie node. Before deployment, traverse the trie once. At each node, compute a min-heap of the k most frequent words in its subtree, where k is typically 5–10. Store this heap as metadata alongside the node.

At query time:

1. Walk the trie to prefix “car” (O(p)).
2. Read the cached heap (O(1) lookup).
3. Extract the top k (O(k log k), usually < 1 ms).

The complexity is now O(p + k log k), where k is small (5–10) and p is prefix length. Dictionary size is gone from the equation.

Trade-off: The heap occupies extra memory (~200 bytes per node for k=10), and if word frequencies change, you must rebuild heaps (expensive, so usually done offline or during off-peak hours).

Building and Maintaining a Trie

In production systems:

• Insertion: O(p) per word. Compare each character against the trie path; create nodes as needed.
• Deletion: Mark nodes as “not terminal” (a tombstone) rather than removing them. This avoids rebuilding the tree and invalidating heaps.
• Frequency updates: If a word’s popularity rank changes (e.g., trending), update its frequency counter. Rebuild the top-k heaps for affected ancestors.

A million-word trie is built once (from a dictionary file) and then rebuilt periodically (nightly, or every hour for trending). Most production autocomplete systems pre-build the trie offline and ship it as a binary blob in the app or database.

When to Use a Trie

Use a trie when:

• You need prefix matching (autocomplete, IP routing, spell-checking).
• The prefix is much shorter than the full term (p << word length).
• You need fast exact-prefix matches on a large set.

Avoid a trie when:

• You need substring or fuzzy matching. A trie won’t find “carpet” from “pet”. For that, use an inverted index + edit distance.
• Your vocabulary is tiny (< 1,000 words). A sorted array and binary search might be simpler.
• You need ordered iteration over all keys. Tries are slow for “all words starting with nothing”; use a B-tree instead.

Why Tries Beat Databases

A query engine cannot do better than O(N) if forced to scan rows. A trie gives you O(p) by exploiting the structure of the problem: prefixes share characters. By grouping words by prefix at build time, you pay a one-time cost and then query in constant time (modulo prefix length).

Databases optimize for arbitrary predicates; tries optimize for one query: “give me all X starting with prefix P.” If that’s your workload, a trie is orders of magnitude faster.

Putting It Together

Production autocomplete: radix compression reduces memory; top-k heap caches ranked results, eliminating descendant traversal.

The full stack is:

1. Radix trie for O(p) prefix navigation.
2. Top-k heap at each node for instant top-k extraction.
3. Persistence layer (mmap’d file, Redis cache, or database blob) so the trie survives restarts.
4. Lazy rebuild of heaps when frequencies drift beyond a threshold.

Google Search, AWS autocomplete, and Slack all use variants of this. The trie is so fundamental to prefix problems that it’s a standard interview question. The next time you type “pyth” and see “python”, “pytest”, “pytorch” ranked by relevance, you’re watching a trie at work.

The Tradeoff: Memory for Speed

Radix tries with top-k heaps are not free. A 1-million-word dictionary consumes ~15–20 MB in memory. A top-k heap per node (at even 1% of nodes) adds another 2–3 MB. For a browser-based autocomplete, that’s feasible; for a device with 64 MB RAM, it’s not.

Solutions:

• Tiering: Cache the global top-k in memory, stream full results for miss cases.
• Compression: Use binary formats (e.g., Trie-DAG), not JSON or text.
• Sampling: Build the trie only for popular terms; use a fallback for tail.

The choice is yours: pay CPU now (scan on every keystroke) or pay memory once (build a trie).

1. Understand the Problem

   Prefix matching scales badly without structure: O(N) per keystroke on a flat dictionary.

2. Trie Intuition

   A trie groups words by shared prefix. A prefix walk is a single path from root to the prefix node, O(p).

3. Radix Optimization

   Collapse single-child chains into multi-character edges. Saves 60% memory; comparison cost amortized by modern string-comparison hardware.

4. Top-k Heap Cache

   Precompute k best results per node. Query-time: extract from heap, O(k log k), typically < 1 ms.

5. Deployment

   Build trie offline from dictionary. Ship as binary blob or Redis cache. Rebuild heaps when word frequencies drift.

Key Takeaways

• Tries are O(p) for prefix search, independent of dictionary size.
• Radix compression cuts memory by 60%, critical for mobile and embedded autocomplete.
• Top-k heaps eliminate traversal, returning ranked results instantly.
• Not always the answer: use tries for exact-prefix problems; use inverted indexes for substring/fuzzy.

The trie is a timeless data structure because it solves a real, recurring problem elegantly. Every search box you use today rests on centuries-old tree wisdom.