Posting List Compression

A web-scale index has TRILLIONS of (term, doc_id) pairs. Storing them naively at 4 bytes per doc_id would be terabytes. Compression cuts this by 5-10x.

Three classic techniques:

Delta encoding: posting lists are sorted ascending; store differences instead of absolute values.

[42, 100, 105, 200, 1000]
becomes
[42, 58, 5, 95, 800]    (deltas)

Deltas are smaller numbers — easier to compress.

Variable-byte encoding (VByte): small numbers take fewer bytes.

• 0-127: 1 byte
• 128-16383: 2 bytes
• ... The high bit of each byte signals "more bytes follow".

42 -> 0x2A          (1 byte)
58 -> 0x3A          (1 byte)
800 -> 0x86 0x20    (2 bytes; 800 = (6<<7) | 0x20 = 768+32)

Block-based compression: group postings into blocks (128 doc IDs); compress each block. PForDelta, Simple9, Roaring Bitmaps.

For boolean intersection over compressed lists, you typically decompress on the fly. Skip lists store decompressed positions every K postings to enable jumps.

Lucene uses a combination: VByte + skip lists + occasional block recompression. Modern systems (Tantivy, Bleve) refine the same.

For this lesson: implement VByte encode/decode of a single posting list.