Typeahead with a trie: an interactive autocomplete simulator

Search-as-you-type suggestions are usually served from a trie, a tree with one character per edge, so every query that starts with the same letters shares the same path. Typing a prefix walks down the tree one character at a time; the suggestions are the most popular queries below that node. To answer within the few milliseconds between keystrokes, each node keeps its top suggestions precomputed instead of searching its subtree.

The playground has a trie of 54 popular searches. Type into the box, or click a branch, and compare the nodes visited with and without a cached top list at each node.

How a trie stores queries

Each node is a prefix; its children are the characters that can come next. “weather”, “weather radar” and “webmail” share the nodes for “w” and “we”, then branch. Finding the node for a prefix takes one step per character, however many queries are stored: 3 steps for “wor” whether the trie holds 54 queries or a billion. Nodes that end a query store its count.

Why each node caches its top k

Finding the node is cheap; finding the best completions below it is not. Without a cache, the engine must visit every node under the prefix, collect every query and sort them. Under “w” that is the whole trie, about 400 nodes in the playground and billions in a real one, and the shortest prefixes, the ones typed first, have the largest subtrees. Storing the top 5 or 10 at every node turns each keystroke into a walk plus one read. The cost is memory, k entries per node, and work on every update: a query becoming more popular may change the top list of every node on its path.

Typeahead at scale

• Build offline: aggregate query logs every hour or day, rebuild the trie with fresh counts and top lists, and swap it in. Suggestions need to be good, not up to the second.
• Shard by prefix: split the trie by first characters across servers, with hot prefixes such as single letters replicated more.
• Cache at the edge: the suggestions for short prefixes are the same for everyone and change slowly, so a CDN or the browser can serve most keystrokes.
• Blend in trends and the user: merge in a small, fast-updating list of trending queries and the user’s own history, and filter out offensive suggestions.
• Debounce on the client and cancel stale requests, so fast typing does not send a request per character.

Compressed tries (radix trees) merge chains of single-child nodes to save memory, and finite-state transducers, used by Lucene’s suggesters, compress further still.

A trie with cached suggestions in code

class Node:
    __slots__ = ("children", "top")
    def __init__(self):
        self.children, self.top = {}, []          # top: [(count, query)], best first

def insert(root, query, count, k=5):
    node, path = root, [root]
    for ch in query:
        node = node.children.setdefault(ch, Node())
        path.append(node)
    for n in path:                                # every prefix of the query may now rank it
        entries = [e for e in n.top if e[1] != query] + [(count, query)]
        n.top = sorted(entries, reverse=True)[:k]

def suggest(root, prefix):
    node = root
    for ch in prefix:                             # one step per character typed
        node = node.children.get(ch)
        if node is None:
            return []
    return [q for _, q in node.top]               # no subtree search

In a system design interview

For typeahead, separate the read path from the build: “An offline job aggregates the last week of searches, builds a trie with the top 10 completions cached at every node, and ships it to suggestion servers every hour. A keystroke is a lookup of at most a few dozen nodes in memory. Prefixes of one or two characters are served from the CDN. A separate stream adds trending queries within minutes.” Expect the follow-ups: memory size, how updates reach every server, personalisation, and typo tolerance.

Read the guide to tries and autocomplete, see the inverted index for full search once the user presses enter, or watch a strong candidate design typeahead search.

Questions people ask