Trie Node Metadata and Top K Precomputation

Raw trie traversal only gets you to the prefix node. The magic of production autocomplete is what you store at each node to avoid expensive subtree walks. Every node maintains four critical fields: end (count of words ending here), size (total words in subtree), maxfreq (highest frequency descendant), and topK (precomputed array of best K completions). This metadata transforms autocomplete from a tree traversal problem into a cache lookup problem.

The topK field is the performance linchpin. When you reach the "sea" node, instead of exploring thousands of descendant words, you immediately return a fixed size array of the 5 or 10 best completions like ["search", "seattle", "season"] with their scores. This list is computed bottom up during index build time by aggregating child topK lists and merging with local words, sorted by a composite rank combining query frequency, click through rate, and recency. A C++ implementation can return five predictions in approximately 347 microseconds because it is just pointer dereferences and array access.

Updating topK is where complexity emerges. When "seahawks" surges in popularity during football season, you must propagate rank changes up the tree from leaf to root, potentially touching dozens of ancestor nodes. Naive per query updates create write amplification and cache invalidation storms. Production systems batch updates over one to five minute windows, aggregate click signals, rebuild topK in a background pipeline, then atomically publish a new immutable snapshot. Google search and Airbnb use this snapshot model to balance freshness with system stability.

The tradeoff is staleness versus load. Precomputed topK makes reads lightning fast (tens of thousands of queries per second per core for cache resident prefixes) but introduces minutes of lag for trending queries. Systems handle breaking news or viral searches by maintaining a small overlay structure (a heap or mini trie) for hot emerging queries that merges with the base topK at serve time, adding two to five milliseconds of latency but capturing trends within seconds.

💡 Key Takeaways

•Each trie node stores end (word count), size (subtree words), maxfreq (best descendant frequency), and topK (precomputed best K completions array). This turns subtree search into array lookup.

•TopK lists are built bottom up during batch indexing by merging child topK arrays and local words, sorted by composite rank (frequency, Click Through Rate, recency). Updates happen every one to five minutes to avoid write amplification.

•A single core can process tens of thousands of autocomplete requests per second when topK is cache resident. Reported C++ implementations return five predictions in approximately 347 microseconds for short prefixes.

•Write amplification is the failure mode. A single word popularity change can require updating topK in dozens of ancestor nodes. Production systems batch updates and rebuild tries periodically rather than updating per query.

•Systems balance freshness and load with overlay structures. A small heap or mini trie captures trending queries in real time and merges with base topK at serve time, adding two to five milliseconds latency but reducing staleness from minutes to seconds.

📌 Examples

Airbnb location search: Node for "new yo" stores topK: [{"new york", 8.2M searches, 0.42 CTR}, {"new york city", 3.1M, 0.38 CTR}, {"new york hotels", 890K, 0.22 CTR}]. Query returns this array in O(1) after O(6) walk, no subtree scan.

Amazon product autocomplete: During Prime Day, "fire tv stick" surges from rank 8 to rank 2 under "fire". Batch job recomputes topK for "f", "fi", "fir", "fire" nodes over five minute window, publishes new snapshot atomically to all serving shards.

Google Trends integration: When "worldcup 2026" goes viral, overlay heap captures spike in real time. Serve path merges overlay (two ms cost) with base topK from last snapshot, surfacing trend within 10 seconds instead of waiting five minutes for next batch rebuild.

← Back to Search Autocomplete (Trie) Overview