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

Index Compression Techniques

Reducing storage and memory with delta encoding, variable-byte encoding, and bitmap compression.

Index Compression Techniques

You'll learn how to dramatically reduce search index storage and memory footprint using specialized compression methods.

Search engines store massive inverted indexes—billions of document IDs per term. Without compression, these indexes would consume petabytes of storage and overwhelm memory. Compression techniques designed specifically for posting lists can achieve 10-20x space reduction while maintaining query performance.

Delta Encoding

Instead of storing absolute document IDs ([12, 45, 89, 134]), store the differences between consecutive IDs ([12, 33, 44, 45]). Since posting lists are sorted, deltas are typically small numbers requiring fewer bits to represent.

Analogy: Rather than saying "I'm at mile 10, mile 23, mile 45," you say "I went 10 miles, then 13 more, then 22 more." Smaller numbers are easier to compress.

Variable-Byte Encoding

Use fewer bytes for small numbers. Each byte stores 7 bits of data plus a continuation bit indicating whether more bytes follow. The number 127 fits in one byte, while 500,000 needs multiple bytes—but you only pay for what you use.

This pairs perfectly with delta encoding, where most gaps are small.

Bitmap Compression

For very common terms appearing in most documents, bitmaps are efficient: one bit per document (1 = present, 0 = absent). Compress these bitmaps using run-length encoding (RLE) to store sequences like "1000 zeros, then 50 ones."

Choosing the Right Technique

  • Sparse posting lists (rare terms): Delta + variable-byte encoding
  • Dense posting lists (common terms): Bitmap compression
  • Hybrid approaches: Store metadata indicating compression method per term

Key Takeaway: Index compression using delta encoding, variable-byte encoding, and bitmap compression reduces storage by 10-20x without sacrificing query speed, making large-scale search economically viable.