Designing a Search Autocomplete System: Tries, Prefix Indexes, and Ranking at Scale

Autocomplete looks easy. User types three characters, your system returns ten suggestions in under 100ms. The first implementation works fine: a sorted list of strings, a binary search, done. Then traffic grows, your query corpus reaches tens of millions of unique strings, you add freshness signals, personalization, and regional bias, and suddenly you have a system that can ruin your p99 latency if you get any piece of it wrong.

This guide covers the full design of a production autocomplete system. Not the interview sketch, the real thing: data structures, storage topology, ranking pipeline, read path, write path, caching layers, and where each approach breaks down.

What Makes Autocomplete Hard at Scale

The naive implementation fails on three axes simultaneously.

Latency budget is brutal. Users experience autocomplete as instant or broken. The practical budget from keystroke to rendered suggestions is 100ms end-to-end. Subtract network RTT (30-60ms on a good day), rendering time (10-20ms), and you have 20-40ms for your backend to find and rank results. That is not much time to do anything interesting.

The prefix space is enormous. A corpus of 100 million unique queries has billions of valid prefixes. You cannot precompute and cache every one. A naive in-memory hash map of all prefix-to-results mappings for a mid-size search product would require hundreds of gigabytes of RAM.

Ranking changes continuously. The right suggestions for “py” at 9am on a Monday after a major Python release are different from the right suggestions at 11pm on a Friday. Freshness, trending topics, and personalization signals mean the ranked list for any given prefix is a moving target. You cannot precompute it once and call it done.

These three constraints, latency, space, and dynamism, define the design space for everything that follows.

Data Structures: Tries and Weighted Prefix Trees

The Basic Trie

A trie (prefix tree) stores strings character by character. Each node represents one character, and the path from root to a node spells out a prefix. A terminal node marks the end of a complete string.

interface TrieNode {
  children: Map<string, TrieNode>;
  isTerminal: boolean;
  query?: string;
  score: number;
}

function buildTrie(queries: Array<{ query: string; score: number }>): TrieNode {
  const root: TrieNode = { children: new Map(), isTerminal: false, score: 0 };

  for (const { query, score } of queries) {
    let node = root;
    for (const char of query.toLowerCase()) {
      if (!node.children.has(char)) {
        node.children.set(char, { children: new Map(), isTerminal: false, score: 0 });
      }
      node = node.children.get(char)!;
    }
    node.isTerminal = true;
    node.query = query;
    node.score = score;
  }

  return root;
}

function lookup(root: TrieNode, prefix: string): TrieNode | null {
  let node = root;
  for (const char of prefix.toLowerCase()) {
    if (!node.children.has(char)) return null;
    node = node.children.get(char)!;
  }
  return node;
}

Lookup is O(p) where p is the prefix length. That is fast. The problem is retrieval: to find the top-K results under a prefix node, you need a DFS or BFS over all descendants, which can be O(n) in the worst case for a popular short prefix.

Weighted Tries with Precomputed Top-K

The standard fix is to precompute the top-K results at every interior node during construction. Each node stores not just the current character but the highest-scoring completions reachable from that node.

const TOP_K = 10;

interface WeightedTrieNode {
  children: Map<string, WeightedTrieNode>;
  topK: Array<{ query: string; score: number }>;
}

function buildWeightedTrie(
  queries: Array<{ query: string; score: number }>
): WeightedTrieNode {
  const root: WeightedTrieNode = { children: new Map(), topK: [] };

  // Insert all queries
  for (const { query, score } of queries) {
    let node = root;
    for (const char of query.toLowerCase()) {
      if (!node.children.has(char)) {
        node.children.set(char, { children: new Map(), topK: [] });
      }
      node = node.children.get(char)!;
    }
    // Bubble up the score to every ancestor
    propagateScore(root, query, score);
  }

  return root;
}

function propagateScore(
  root: WeightedTrieNode,
  query: string,
  score: number
): void {
  let node = root;
  const entry = { query, score };

  const insertIntoTopK = (n: WeightedTrieNode) => {
    n.topK.push(entry);
    n.topK.sort((a, b) => b.score - a.score);
    if (n.topK.length > TOP_K) n.topK.pop();
  };

  insertIntoTopK(node);
  for (const char of query.toLowerCase()) {
    node = node.children.get(char)!;
    insertIntoTopK(node);
  }
}

function getTopK(
  root: WeightedTrieNode,
  prefix: string
): Array<{ query: string; score: number }> {
  let node = root;
  for (const char of prefix.toLowerCase()) {
    if (!node.children.has(char)) return [];
    node = node.children.get(char)!;
  }
  return node.topK;
}

Now lookup is O(p) and retrieval is O(1) (just return the precomputed list). The cost is memory: every node stores up to K entries, and the trie itself has O(total characters) nodes. For 100 million queries averaging 30 characters each, the trie has roughly 3 billion character nodes before compression. You need PATRICIA tries or radix tries to make this fit in memory.

Radix Tries for Memory Efficiency

A radix trie (compressed trie) merges nodes that have only one child into a single edge labeled with the shared substring. This cuts memory dramatically for sparse prefixes.

interface RadixNode {
  label: string; // Can be multiple characters
  children: Map<string, RadixNode>;
  topK: Array<{ query: string; score: number }>;
}

In practice, a compressed trie on a 100M-query corpus at 10 top-K entries per node fits in roughly 8-12 GB of heap memory, which is manageable on a single large instance. For global products with regional variation, you shard by prefix character range or by language/locale.

Storage: In-Memory vs. Distributed

Single In-Memory Instance

For corpora up to ~50 million unique queries with modest update frequency (rebuilding once per hour), a single in-memory weighted trie works. You load it at startup, serve reads from it, and swap it atomically on rebuild. Zero external dependencies, sub-millisecond lookups.

The rebuild cycle is the gotcha. Rebuilding a 100M-query trie takes 3-8 minutes depending on hardware. During rebuild, you serve the old trie. When the new trie is ready, you atomically swap the pointer. This means your freshness lag equals your rebuild interval.

Distributed Prefix Sharding

At Google/Bing/Amazon scale, you shard by prefix. Common approaches:

• Alphabetical sharding: prefixes starting with a-g on shard 1, h-m on shard 2, etc. Simple, but uneven (more queries start with common letters).
• Hash-based sharding: consistent hashing on the first N characters. Better balance, but you lose the ability to route by prefix locality.
• Tiered architecture: hot prefixes (short, high-traffic) on dedicated high-memory nodes; long-tail prefixes on cheaper storage with slower lookup.

The read path fans out to one or two shards per query (primary + fallback), aggregates top-K results, re-ranks, and returns within latency budget.

Ranking Signals

Returning the most-searched queries is the minimum. Real autocomplete systems layer multiple signals.

Popularity (global). The raw query frequency, usually normalized over a 30-day rolling window. This is the baseline score and dominates for short prefixes with high ambiguity.

Freshness. Trending queries need to surface before the 30-day window reflects them. You apply a recency boost to queries whose frequency is accelerating. A simple approach is exponential moving average: weight recent hours more heavily than last week.

function computeFreshnessScore(
  hourlyBuckets: number[], // 168 hours = 7 days
  decayFactor: number = 0.95
): number {
  let score = 0;
  let weight = 1.0;
  for (let i = hourlyBuckets.length - 1; i >= 0; i--) {
    score += hourlyBuckets[i] * weight;
    weight *= decayFactor;
  }
  return score;
}

Personalization. User’s own recent queries and click history shift rankings for that user. This is typically a lightweight reranking layer applied after the trie returns a candidate set, not baked into the trie itself.

Contextual signals. Device type, locale, time of day, and session context. A mobile user in Tokyo at 8am gets different suggestions than a desktop user in New York at 3pm.

The practical architecture: the trie returns the top-50 candidates based on global popularity, and a thin reranking layer applies personalization and contextual boosts before slicing to top-10 for the response. The reranking runs in under 5ms, preserving the latency budget.

The Read Path

A single autocomplete request flows like this:

1. Client debounce: the client fires a request 150-200ms after the user stops typing, not on every keystroke. This alone cuts backend QPS by 60-80%.
2. Cache check: check the application-level cache (Redis or in-process LRU). Short prefixes (1-3 characters) are cached aggressively because they are identical for all users and extremely high traffic.
3. Trie lookup: O(p) traversal to the prefix node, O(1) retrieval of top-K candidates.
4. Reranking: apply personalization and contextual signals to the candidate set.
5. Response: serialize and return. Responses are small (10 strings), so serialization is negligible.

interface AutocompleteRequest {
  prefix: string;
  userId?: string;
  locale: string;
  maxResults: number;
}

interface AutocompleteResult {
  suggestions: string[];
  fromCache: boolean;
  latencyMs: number;
}

async function handleAutocomplete(
  req: AutocompleteRequest,
  trie: WeightedTrieNode,
  cache: LRUCache<string, string[]>,
  personalizer: Personalizer
): Promise<AutocompleteResult> {
  const start = performance.now();
  const cacheKey = `${req.locale}:${req.prefix}`;

  // Check application cache first
  const cached = cache.get(cacheKey);
  if (cached && !req.userId) {
    return {
      suggestions: cached,
      fromCache: true,
      latencyMs: performance.now() - start,
    };
  }

  // Trie lookup
  const candidates = getTopK(trie, req.prefix);
  if (candidates.length === 0) {
    return { suggestions: [], fromCache: false, latencyMs: performance.now() - start };
  }

  // Rerank with personalization if user context available
  const ranked = req.userId
    ? await personalizer.rerank(candidates, req.userId)
    : candidates.map((c) => c.query);

  const suggestions = ranked.slice(0, req.maxResults);

  // Cache non-personalized results
  if (!req.userId) {
    cache.set(cacheKey, suggestions);
  }

  return { suggestions, fromCache: false, latencyMs: performance.now() - start };
}

Latency targets by prefix length:

Prefix length	Target p50	Target p99
1-2 chars	5ms	15ms
3-5 chars	3ms	10ms
6+ chars	2ms	8ms

Short prefixes are slower because they match more candidates and require more work from the reranking layer, not because trie traversal is slower.

The Write Path

The write path handles two jobs: ingesting new queries from user activity and updating frequencies for existing ones.

Query Ingestion Pipeline

Every user search is a signal. You cannot write directly to the trie on every search (it is an in-memory data structure rebuilt in batch). Instead, you buffer events in a stream, aggregate them, and feed the aggregated counts to the trie rebuild job.

interface QueryEvent {
  query: string;
  timestamp: number;
  locale: string;
  userId?: string;
}

// Runs as a stream consumer (Kafka, Kinesis, etc.)
async function aggregateQueryCounts(
  events: AsyncIterable<QueryEvent>,
  windowMs: number
): Promise<Map<string, number>> {
  const counts = new Map<string, number>();
  const cutoff = Date.now() - windowMs;

  for await (const event of events) {
    if (event.timestamp < cutoff) continue;
    const key = `${event.locale}:${event.query.toLowerCase()}`;
    counts.set(key, (counts.get(key) ?? 0) + 1);
  }

  return counts;
}

The aggregation window determines freshness lag. A 1-hour window with hourly rebuilds means trending queries surface within 1-2 hours. Most production systems use a tiered approach: a fast path for real-time trending detection (stream processing, 5-minute windows) and a slow path for the stable popularity baseline (daily batch aggregation).

Trie Rebuild vs. Incremental Updates

Rebuilding the entire trie is simple and safe: compute new scores, build new trie, atomic pointer swap. The downside is the rebuild time and the compute cost.

Incremental updates are faster but tricky. Updating a node’s top-K list requires re-sorting and potentially evicting a previously top-ranked entry, which means propagating changes up through ancestor nodes. In a concurrent system, this creates locking complexity. Most teams at medium scale choose full rebuilds on a schedule and accept the freshness lag.

Caching Strategy

Three caching layers work together to absorb the read load.

Browser cache. The client caches responses keyed by (prefix, locale). A short TTL (30-60 seconds) is appropriate for long prefixes where rankings change slowly. For short prefixes where trending queries can shift the list in minutes, skip browser caching or use a very short TTL (5-10 seconds).

CDN cache. For non-personalized requests, the response is identical for all users sharing a locale. A CDN can cache and serve these responses with edge-level latency (5-20ms from the user). Cache key must include locale and exclude any user-specific headers. TTL follows the same logic as browser cache.

Application cache (in-process or Redis). A local LRU cache on each backend instance handles the hot prefix set. The top 1,000 prefixes by traffic often account for 40-60% of total QPS. An in-process LRU with a 10,000-entry capacity eliminates trie lookups for those entirely.

import LRU from 'lru-cache';

const prefixCache = new LRU<string, string[]>({
  max: 10_000,
  ttl: 30_000, // 30 seconds
  updateAgeOnGet: false,
});

Cache invalidation on trie rebuild: the simplest approach is to flush the application cache when the new trie goes live. Redis supports atomic cache invalidation by namespace (delete all keys matching locale:*). In-process LRUs can be swapped alongside the trie pointer.

Tradeoffs

Approach	Latency	Memory	Freshness	Complexity
In-memory weighted trie, full rebuild	Sub-ms lookup	8-15 GB for 100M queries	Rebuild interval (1-24h)	Low
Distributed prefix sharding	5-20ms (network hop)	Scales horizontally	Same as rebuild interval	High
Real-time incremental updates	Sub-ms after update propagation	Same	Minutes	Very high
Database-backed prefix search (SQL LIKE)	50-500ms	Low (disk)	Real-time	Very low
External search engine (Elasticsearch prefix query)	10-50ms	Medium	Near real-time	Medium
CDN-cached trie responses	5-20ms from edge	Distributed	TTL-bound	Low (ops)

For most products, the in-memory weighted trie with periodic full rebuilds is the right default. Move to distributed sharding only when your corpus size exceeds what fits on a single high-memory node, or when global latency requirements force edge deployment.

Production Considerations

Memory pressure. Monitor heap usage continuously. A memory leak in the trie build path can cause OOM during rebuild, leaving the old trie serving stale data indefinitely. Use off-heap storage (mmap or native allocators) for very large tries on JVM or Node.js runtimes.

Rebuild coordination. In a multi-instance deployment, stagger rebuilds across instances. Rebuilding all instances simultaneously creates a thundering herd on the data pipeline and a period where no instance is serving fresh data. Use a distributed lock to ensure only one instance rebuilds at a time, or use blue-green deployment where the new trie fleet goes live before the old fleet is decommissioned.

Harmful query filtering. Your autocomplete will surface queries you do not want it to surface: slurs, private information patterns, legally sensitive terms. Build a blocklist layer applied at trie construction time and at serve time. The serve-time check handles newly added blocklist entries between trie rebuilds.

Cold start. A new deployment with no query history has no popularity signal. Seed the initial corpus with curated popular queries and handle the bootstrapping period explicitly. Do not let a cold trie serve an empty response set.

Observability. Track prefix-level cache hit rates, trie lookup latency distributions, and the freshness lag between a query first appearing in logs and appearing in autocomplete results. The freshness lag metric will tell you faster than anything else when your write pipeline is degraded.

Prefix length cutoffs. Prefixes shorter than two characters produce too many low-signal completions and create enormous trie nodes. Prefixes longer than 15-20 characters are almost always better served by a full-text search than autocomplete. Define and enforce these bounds at the API layer.

Closing Thought

The core insight of autocomplete system design is that the read path and write path operate on fundamentally different timescales, and the architecture has to embrace that asymmetry rather than fight it. The read path needs sub-millisecond in-memory lookup. The write path can tolerate minutes or hours of lag in exchange for correctness and operational simplicity. The weighted trie with periodic full rebuilds respects this asymmetry. Every optimization after that is about shrinking the lag, extending the scale, or improving signal quality, but the foundation holds across several orders of magnitude of traffic growth.