The Trie

In one line: the trie answers the query shape directly, and then the design keeps optimizing until the tree is barely traversed at all — which is the interesting part.

The structure

A trie is a tree structure where each node stores a character of a string. When a user types "UNIV," the service traverses the trie to the node V, then identifies all terms starting with that prefix.

Storing: UNITED, UNIQUE, UNIVERSAL, UNIVERSITY

        U
        |
        N
        |
        I
      / | \
     T  Q  V
     |  |  |
     E  U  E
     |  |  |
     D  E  R
           |
          S...

Why a trie and not an index — the prefix IS the path

The query is "give me everything starting with these characters," and a trie answers it structurally rather than by searching.

In a trie, a prefix is a path from the root. So finding all completions of "UNIV" is not a search at all — you walk four nodes and everything below you is, by construction, an answer. No comparison, no scan, no filtering.

Compare the alternatives:

Two things make the trie win here.

The lookup cost depends on the prefix, not the corpus. Reaching "UNIV" takes four steps whether the trie holds a thousand queries or two billion. A B-tree's log n grows with the data; a trie's does not.

Shared prefixes are stored once. UNIVERSAL and UNIVERSITY share "UNIVERS" — seven characters stored one time. At two billion queries with enormous prefix overlap, that compression is substantial.

The Yelp chapter's lesson applies in a new domain: one-dimensional ordering could not preserve two-dimensional proximity, and here a hash cannot preserve prefix relationships. In both cases you choose a structure whose shape matches the query's shape.

When the query is structural, pick a structure where the answer is a location rather than a search result.

Each node is one character; a path from the root spells a prefix; terminal nodes carry the query and its frequency. The problem is visible immediately — a long unbranching chain costs one node per character for no branching decision, which is what compression fixes.

Compression

We can optimize the trie by merging nodes with a single branch. This reduces tree depth and traversal time.

UNCOMPRESSED           COMPRESSED
   U                      "UNI"
   |                     /  |  \
   N                 "TED" "QUE" "VERS"
   |                              /   \
   I                          "AL"  "ITY"
 / | \
T  Q  V ...

A radix tree — and it converts pointer-chasing into memory locality

Merging single-child chains gives a radix tree (or Patricia trie), and the benefit is larger than "fewer levels."

The stated gain is depth: "UNIVERSITY" goes from ten nodes to about three. But the real gain is memory access pattern.

An uncompressed trie stores one character per node, so traversing ten characters means ten pointer dereferences to ten separate heap locations — each a potential cache miss. A compressed node holds a whole string contiguously, so one dereference brings the entire segment into cache.

Uncompressed: 10 dereferences, 10 possible cache misses
Compressed:    3 dereferences, 3 possible cache misses

Against Lesson 1's 200 ms budget that sounds trivial, and it is not — at 607,000 requests per second, the constant factor is the difference between nine servers and considerably more.

Reducing pointer chasing matters more than reducing node count, because the cost of a node visit is dominated by whether it is in cache.

Frequencies in terminal nodes

We store the count of how many times a term is searched in its terminal node. If a user types "UNI," the system traverses to UNI, identifies all descendants, and ranks by frequency.

UNITED     15
UNIQUE     20
UNIVERSAL  21
UNIVERSITY 25

Type "UNI" -> UNIVERSITY(25), UNIVERSAL(21), UNIQUE(20), UNITED(15)

Ranking by descendant traversal is O(subtree), and short prefixes are the worst case

This is where the naive design breaks the latency budget.

Typing "UNI" means visiting every descendant of the UNI node, collecting frequencies, sorting, and returning the top ten. The cost is proportional to the size of the subtree, and subtree size is inversely related to prefix length:

Prefix "UNIVERSIT" -> a handful of descendants     -> fast
Prefix "UNI"       -> thousands                    -> slow
Prefix "U"         -> a substantial fraction of the corpus -> unacceptable
Prefix "a"         -> ~4% of everything             -> impossible in 200 ms

And the distribution is exactly backwards from what you want: short prefixes are both the most expensive and the most common, because every user types the first character before the second.

So the naive trie is fastest precisely when it matters least — by the time someone has typed nine characters, they barely need suggestions.

When cost is inversely proportional to how much the user has typed, the common case is the expensive case. That is what the next optimization exists to fix.

This is the move the whole chapter turns on. Cost is inversely related to prefix length — a one-character prefix has the largest subtree — so the queries that arrive first are the expensive ones. Caching top-k at every node removes traversal from the request path entirely.

Precomputing the top-k

Pre-compute and save the top ten suggestions for every prefix in the node. Instead of traversing the trie every time a user types UNIVERS, the system stores a precomputed, sorted list of completions in the node representing that prefix. However, this increases storage usage.

This removes traversal entirely, and it is the design's most important optimization

Store the answer in the node, and the operation changes shape completely:

BEFORE:  walk to prefix node -> visit ALL descendants -> collect -> sort -> take 10
AFTER:   walk to prefix node -> READ the stored list

The cost becomes O(prefix length) with no dependence on subtree size — so "a" costs the same as "universit". The worst case disappears.

That is what makes the 200 ms budget achievable. Lesson 1 argued that no computation may sit on the request path; this is how the ranking computation gets removed from it.

The trade the design names is storage, and it is worth quantifying:

Every prefix node stores 10 suggestions x ~15 characters x 2 bytes = ~300 bytes

Multiplied across every node in the trie, that is a real multiple of the base index. But Lesson 2 established the base is only 60 GB, so even a 5–10× increase stays in the range a memory-resident cluster handles.

Trading storage for the elimination of a traversal is almost always right when the traversal is on a latency-critical path — and it is the same materialize-versus-compute decision that building block made for routes and the newsfeed chapter for feeds.

Note what it also does to updates: with answers baked into nodes, changing one frequency can invalidate the stored lists of every ancestor. A query becoming popular must propagate up the tree. That is precisely why Lesson 6 rebuilds the trie offline rather than mutating it in place.

Incrementing on selection — and the counter-overflow question

If the user selects UNIQUE, the system increments its count to 21.

That is a real-time write on a read-optimized structure, and Lesson 6 explicitly moves it offline for the reason above.

The design's own question about overflow — frequencies growing without bound — has two offered answers, and they differ meaningfully:

Normalize into a fixed range (say 0–1,000). Keeps relative ordering, bounds the integer, and requires periodic rescaling of everything.

Stop incrementing past a threshold, assuming anything that high is already top-ranked. Simpler, and it loses the ability to distinguish among the most popular queries — exactly the ones most often shown.

There is a third the design does not mention and which real systems prefer: time-decayed counts, where older searches weigh less. That solves overflow and solves staleness — a query popular five years ago should not outrank one trending today. Decay converts an unbounded counter into a bounded one and makes the ranking reflect recency for free.

Next: partitioning the trie and updating it without blocking reads.