The Trie and the Serving Path

A trie

The natural index for prefix lookup is a trie. One node per character, and every query sharing a prefix shares a path.

Walk to the node for three letters in three steps, and everything below it is every known query starting that way.

Reject the naive next step, and name it while you reject it. Exploring that subtree and ranking by frequency fails, because a popular short prefix has millions of descendants and traversing them inside 10 milliseconds is fantasy.

Precompute at every node

Precompute the answer at every node. That is this design's one big idea. Each node stores its own top five completions, worked out offline by bubbling the best candidates up from the leaves.

Watch what a request does now. It walks the prefix in a handful of pointer hops and reads a ready-made list. No traversal, no ranking, no allocation on the hot path at all.

Pay for it in two currencies. Memory, because storing a list at every node multiplies your structure several times over. And update cost, because one query's count change touches every ancestor's list.

Notice both get paid offline, where they are cheap, so your online path does nothing but read.

Keep memory manageable with the standard compressions. Collapse chains of single-child nodes, since most nodes below a certain depth are chains. Store completions as identifiers into a shared string table instead of repeating strings. Cap the depth you index at around 30 characters.

Land ten million queries in a few gigabytes that way. Production systems often skip the literal pointer trie for a structure that shares suffixes as well as prefixes, and that is how the mainstream search engines hold suggestions in memory.

Let the serving architecture follow from the data fitting in memory. Replicate the whole structure to every machine behind your balancer, with no sharding and no coordination, and add replicas when you need to serve more requests a second.

Put a cache in front for the head of the distribution, since a few thousand prefixes cover a huge share of your requests. Handle updates by snapshot swap: build a new structure, load it alongside, flip a pointer.

// The mistake: walk the subtree and rank. A popular short prefix
// has millions of descendants and 10 ms to work in.
List<String> wrong(String prefix) {
  return rankByFrequency(collectAllBelow(node(prefix)));   // never finishes
}

// Every node already holds its own answer, computed offline by
// bubbling the best candidates up from the leaves.
class Node {
  Map<Character, Node> children;
  String[] top5;                 // the whole trick
}

List<String> suggest(String prefix) {
  Node n = root;
  for (char c : prefix.toCharArray()) {
    n = n.children.get(c);
    if (n == null) return List.of();
  }
  return List.of(n.top5);        // a few pointer hops, then a read
}

Worked example

Lena builds autocomplete for a travel search site with 4 million distinct destination and hotel queries. Version one walks the trie subtree at request time and ranks on the fly; for prefixes of 3-plus characters it responds in 2 ms, but one-character prefixes explore hundreds of thousands of nodes, and 'b' (every beach, Barcelona, Bali, Berlin) takes 240 ms, precisely on the queries users type first. Version two precomputes top-5 lists at build time: a nightly job aggregates counts, bubbles winners up the tree, and writes a 1.9 GB immutable snapshot to S3. Serving nodes map it into memory and answer any prefix, one character or twenty, in under 400 microseconds. Deploys become boring too: a snapshot flip at 4 am, with the old structure kept mapped until in-flight requests drain.