Course contentsShow
← System Design
Lesson 1759 of 1,91942. Real-World System: Search and TypeaheadFree lesson

Trie Space Optimization Techniques

Compressing tries using radix trees, LOUDS, and other techniques to reduce memory footprint at scale.

Trie Space Optimization Techniques

You'll learn how to compress tries to handle millions of words without exhausting memory.

Standard tries are powerful for prefix matching, but they're memory hogs. Each node stores pointers to up to 26 children (for lowercase English), most of which are null. At scale—millions of search terms, multiple languages—this overhead becomes unsustainable. You need compression techniques to keep tries practical.

Why Standard Tries Waste Space

A typical trie node might allocate an array of 26 pointers, but most nodes only have 1-3 actual children. That's 23+ wasted pointer slots per node, multiplied by millions of nodes. For a 10-million-word trie, you're looking at gigabytes of wasted memory.

Radix Trees (Patricia Tries)

Instead of storing one character per node, radix trees compress chains of single-child nodes into edge labels. The word "search" might be stored as one node with edge label "search" instead of six nodes for "s", "e", "a", "r", "c", "h". This drastically reduces node count for sparse branches.

LOUDS (Level-Order Unary Degree Sequence)

LOUDS encodes the trie structure as two bit vectors: one for tree shape (using level-order traversal), another for labels. It achieves near-optimal space—roughly 2 bits per node—at the cost of slightly slower queries (bit-level operations). Perfect for read-heavy workloads where memory is the bottleneck.

Other Techniques

  • Minimal perfect hashing for leaf nodes
  • Pointer compression (use 32-bit offsets instead of 64-bit pointers)
  • Alphabet reduction (map rare characters to shared slots)
  • Lazy loading cold branches from disk

Key Takeaway:
Radix trees, LOUDS encoding, and pointer compression techniques reduce trie memory footprint by 5-10x, making autocomplete feasible for massive dictionaries while maintaining sub-millisecond prefix lookups.