Autocomplete found the prefix and still timed out

A hypothetical autocomplete service finds the node for prefix a in microseconds, then spends seconds walking its descendants to choose five suggestions. The algorithm review had promised O(prefix length).

That bound described reaching the prefix, not answering the user's question.

Charge for the output you actually need

A trie follows characters along edges. Navigating a prefix of length $L$ can take $O(L)$ under constant-time edge access. Enumerating matching completions also costs the visited subtree and output. Precomputing top-K candidates at prefix nodes trades query work for memory and update/rebuild cost.

Naive fixed child-pointer arrays waste space for sparse alphabets. Radix compression merges single-child paths; double-array tries or finite-state representations offer other compact layouts. Unicode normalization, tokenization, case rules, and ranking policy belong to the index contract, not just UI polish.

The user types two words in either order

A prefix structure cannot efficiently answer arbitrary multi-term document queries. Build an inverted index mapping each term to a sorted posting list of document IDs, with frequencies and positions as needed.

For lists of lengths $M$ and $N$, two-pointer intersection costs $O(M+N)$. If one list is much shorter, galloping/skipping can reduce comparisons; express its useful bound as $O(M\log(1+N/M))$ when $M\le N$, including the equal-size case. Dense posting regions can use bitmaps and word-wise intersection. Delta/block compression trades decode CPU for reduced memory bandwidth.

Phrase queries need positions; arbitrary substring matching may need n-grams or other indexing, not merely a word posting list. Start with the required matching semantics.

Ranking is a different question from membership

BM25 uses term frequency with saturation and document-length normalization:

$$\text{score}(D,Q)=\sum_{q\in Q}\text{IDF}(q)\frac{f(q,D)(k_1+1)}{f(q,D)+k_1(1-b+b|D|/\text{avgdl})}$$

Here $f$ is term frequency, $|D|$ document length, and avgdl average length. One common smoothed IDF form is $\ln(1+(N-n_q+0.5)/(n_q+0.5))$. Parameters and exact engine variants must be tuned/verified; a formula does not establish relevance on your corpus.

A term present in most documents produces a large candidate set. Intersect selective terms early, use compressed postings/skip information, and measure ranking cost. “Stop words” cannot simply disappear if the product needs phrases containing them.

Keep the index derived and recoverable

Use the outbox/CDC path for updates and versioned deletes. Publish immutable search generations or segment changes through a safe boundary, keep rebuild capacity separate from serving capacity where needed, and monitor freshness lag. Partitioning by tenant can help locality and access control; distributing by document can improve balance but makes queries fan out.

Autocomplete ranking may use delayed aggregate popularity rather than per-keystroke synchronous tree mutation. State how fresh popularity must be and whether suggestions can expose private terms.

Mental model: navigation finds a candidate space. Enumeration, ranking, updates, and permissions decide the real query cost.

Transfer: the five private suggestions

---

Source trail: 13-trie-data-structure-and-inverted-index. See the source map for consolidation and reference-retained material.