索引压缩
概述
索引压缩（Index Compression）通过差值编码+变长编码将倒排索引从原始文本的 20-40% 压缩至可全内存加载，将磁盘检索转变为内存检索，速度提升 100-1000x。核心利用 Posting List 的有序性和差值分布的幂律特性。
关键内容
-
规模动机：1 亿文档搜索引擎，原始索引约 40GB（50亿对 × 8字节），压缩后 5-10GB 可装入 64GB 服务器内存。
-
差值编码（Delta/Gap Encoding）：Posting List 按 doc_id 升序存储差值（gap = doc_id[i] - doc_id[i-1]）。差值通常远小于原始值（大量小差值），是所有后续编码的前提。
-
VByte（变长字节编码）：每字节最高位（MSB）作延续标志（1=继续，0=停止），低 7 位存数据。小数字（0-127）占 1 字节，中等数字 2 字节，大数字 3-4 字节。压缩比 3-5x，解码速度 ★★★★，工业主流。
-
Elias 编码系列：
- Gamma：
2×⌊log₂(n)⌋+1位，适合极小差值 - Delta：用 Gamma 编码长度前缀，大数时比 Gamma 更高效
-
压缩率更高但解码慢，CPU 不友好
-
PForDelta（Patched Frame of Reference Delta）：批量处理 128 个差值，90% 的值用固定 b 位存储，10% 异常值单独放补丁列表。主体部分可用 SIMD 指令批量解码，压缩比 4-8x，解码速度 ★★★★★，Lucene FrameOfReference 的基础。
-
Simple-9/16：将多个小整数打包进一个 32 位整数（4位选择器+28位数据，9种打包方案），SIMD 友好，小差值密集时优于 VByte。
-
词典压缩（Front Coding）：利用词典有序性，相邻词共享前缀（"automation → e → ic → ion"），词典大小减少 50-70%。Lucene 用 FST（有限状态转换器）：共享前缀+后缀，比 Trie 省 2-3 倍空间。
-
压缩 vs 解码速度权衡：全内存场景（Redis Search/Tantivy）优先快速解码（PForDelta/SIMD-BP128）；磁盘场景（NVMe SSD 已足够快）优先高压缩率减少 I/O。
来源
raw/articles/ai-engineering/search-retrieval/08_index_compression.md— 传统搜索引擎深度解析系列 第8篇