倒排索引压缩能显著降低存储和IO开销，是大规模搜索引擎的必备技术。文章介绍gamma、delta编码等一元压缩方法，以及VByte和PForDelta等高性能编码方案，分析各方案在压缩率和解码速度上的权衡，讨论索引压缩对查询吞吐量的实际影响和最优编码选择策略。

岗位关联

需要学习索引压缩(gamma/delta/VByte/PForDelta)，倒排索引压缩能显著降低存储和IO开销，是大规模搜索引擎的必备技术。这一知识点在搜索引擎基础 > 38.1.2 倒排索引与查询处理中承上启下，连接基础理论与工程实践。

目录
  1. 可视化演示
  2. 倒排索引与压缩的必要性
  3. 文档ID间距(d-gap)
  4. Gamma编码
  5. Delta编码
  6. VByte (Variable Byte)编码
  7. PForDelta (Patched Frame of Reference Delta)
  8. 压缩技术对比与实际应用
  9. AI 应用场景
  10. Python 演示
  11. 常见问答
  12. 常见误区
  13. 参考来源

可视化演示

展示倒排索引压缩技术：d-gap间距转换、Gamma一元编码、VByte变长字节和PForDelta批量编码，交互切换对比各方案。

本节配有交互动效（进入视口后自动加载，约 3KB）。

倒排索引与压缩的必要性

倒排索引(inverted index)是搜索引擎中最核心的数据结构，它建立了从词项(term)到文档列表的映射。每个词项的倒排列表(posting list)包含一系列倒排记录(posting)，每条记录通常包含文档ID(docID)、词频(TF)和词项在文档中的位置信息。当文档集合达到数亿甚至数十亿规模时，倒排索引的存储开销极为可观，可能占据数百GB甚至TB级的磁盘空间。

倒排索引的巨大体积不仅带来存储成本，更关键的是导致查询时的I/O开销增大。搜索引擎在处理查询时，需要从磁盘读取相关词项的倒排列表并解码，I/O时间往往占据查询延迟的主要部分。因此，索引压缩技术应运而生，其核心目标是在显著减少存储空间和I/O开销的同时，保持快速的解码能力，使得查询响应不会因解压而明显变慢。

评估索引压缩技术的性能通常从三个维度进行：压缩率（bits/docID，即平均每个docID占用的比特数，越低越好）、解码速度（docs/sec，即每秒能解码的文档数，越高越好）和随机访问能力（能否直接定位和解码第k个值）。不同编码方法在这三个维度上各有权衡，实际系统需要根据应用场景选择合适的方案。

CR=SoriginalScompressedCR = \frac{S_{original}}{S_{compressed}}

文档ID间距(d-gap)

倒排列表中的docID天然具有单调递增的特性，因为文档是按ID顺序处理的。直接存储原始docID意味着数值通常很大（如文档ID可能达到数百万甚至数亿），需要较多的位数来表示。文档ID间距(d-gap)变换利用了这一单调递增特性，将原始的绝对docID序列转换为相邻docID的差值序列。

具体而言，对于倒排列表中的docID序列[docID_1, docID_2, ……, docID_n]，d-gap变换后得到[d_1, d_2, ……, d_n]，其中d_1 = docID_1（第一个值保持不变），d_i = docID_i - docID_{i-1}（后续值为相邻docID的差）。由于docID单调递增，所有d-gap都是正整数，且通常远小于原始docID。例如，序列[1000, 1005, 1008, 1010]经d-gap变换后变为[1000, 5, 3, 2]，后续值显著减小。

d-gap变换是所有后续整数编码技术的基础预处理步骤。它本身并不直接减少存储位数（差值序列和原始序列的信息量相同），但通过大幅减小数值范围，使得后续的变长编码（如Gamma、Delta）和分块编码（如PForDelta）能够用更少的位数表示每个值。实际统计表明，经过d-gap变换后，大部分间距值集中在较小的数值范围内，这为高效压缩创造了条件。

di=docIDi−docIDi−1,d1=docID1d_i = docID_i - docID_{i-1}, \quad d_1 = docID_1

Gamma编码

Gamma编码是由Elias提出的一种通用变长整数编码方法，特别适合编码较小的正整数。其基本思想是将整数x的表示分为两部分：长度部分（用一元编码表示）和偏移部分（用二进制编码表示）。Gamma编码的设计使得小数值占用很少的位数，而大数值占用较多的位数，这与d-gap变换后数据中小数值占多数的特性高度契合。

具体而言，对于正整数x，设N = floor(log2(x))，即x二进制表示的位数减1。Gamma编码的第一部分是一元编码N，即N个0后跟一个1;第二部分是二进制偏移，即x去掉最高位1后的N位二进制表示。例如，x=5（二进制101），N=2，一元编码为001，偏移为01(5减去4等于1，用2位表示)，Gamma编码为00101，共5位。x=1时N=0，一元编码为1，无偏移，Gamma编码为1，仅1位。

Gamma编码的位数为2乘以floor(log2(x))再加1，即与log2(x)成线性关系。对于d-gap变换后常见的较小数值（如1到10），Gamma编码非常高效：编码1仅需1位，编码3需要3位，编码7需要5位。然而，对于较大的数值，Gamma编码的位数增长较快，且一元编码部分（N个0）的空间利用率不高，这时Delta编码或VByte可能是更好的选择。

Lγ(x)=2⌊log⁡2x⌋+1L_{\gamma}(x) = 2\lfloor \log_2 x \rfloor + 1
γ(x)=unary(⌊log⁡2x⌋)+offset(x)\gamma(x) = \text{unary}(\lfloor \log_2 x \rfloor) + \text{offset}(x)

Delta编码

Delta编码同样是Elias提出的通用整数编码方法，是Gamma编码的改进版本。Gamma编码的主要不足在于一元编码部分的空间效率：对于大数值，一元编码N个0需要N位，这部分空间可以被进一步压缩。Delta编码的核心改进在于对长度部分N+1再次使用Gamma编码，而非简单的一元编码，从而减少大数值的编码长度。

具体而言，对于正整数x，设N = floor(log2(x))。Delta编码的第一部分是Gamma编码(N+1)，即对N+1这个数值本身应用Gamma编码；第二部分是二进制偏移，与Gamma编码相同，即x去掉最高位1后的N位。例如，x=100，N=6，Gamma编码(7)为00111(5位)，偏移为100100(6位)，Delta编码为00111100100，共11位。相比之下，Gamma编码100需要2乘以6加1等于13位。

Delta编码的位数约为log2(x)加上2倍的log2(log2(x))，比Gamma编码的2倍log2(x)增长更慢。当x较小时（如x小于等于16），Delta编码与Gamma编码长度相当甚至略长；但当x较大时（x大于等于32），Delta编码明显更短。在实际的倒排索引中，d-gap值既有大量小值也有少量大值，因此Delta编码在整体压缩率上通常优于Gamma编码。

δ(x)=γ(⌊log⁡2x⌋+1)+offset(x)\delta(x) = \gamma(\lfloor \log_2 x \rfloor + 1) + \text{offset}(x)
Lδ(x)=⌊log⁡2x⌋+2⌊log⁡2(⌊log⁡2x⌋+1)⌋+1L_{\delta}(x) = \lfloor \log_2 x \rfloor + 2\lfloor \log_2(\lfloor \log_2 x \rfloor + 1) \rfloor + 1

VByte (Variable Byte)编码

VByte（Variable Byte，变长字节）编码是一种字节对齐的变长整数编码方法。与Gamma和Delta等位级(bit-level)编码不同，VByte以字节为基本单位进行编码，每个字节的最高1位作为继续标志(continuation bit)，低7位存储数据。这种字节对齐设计使得VByte在解码时可以逐字节读取，避免了位级操作的开销，从而获得极快的解码速度。

具体而言，VByte将整数x从低位到高位分割为若干7位组。每个字节中，低7位存放一个数据组，最高位为1表示后面还有更多字节，最高位为0表示当前字节是最后一个。例如，x=300（二进制100101100），分割为两组：低位0101100(44)和高位10(2)。编码为两个字节：第一字节最高位为1表示继续，数据为0101100;第二字节最高位为0表示结束，数据为0000010。VByte编码x所需的字节数为ceil(bitlen(x)除以7)。

VByte的最大优势在于解码速度。由于字节对齐，CPU可以高效地逐字节读取和处理数据，现代CPU的缓存行机制和字节寻址方式对VByte数据特别友好。此外，VByte的实现非常简单，编解码逻辑清晰。然而，字节对齐也带来了空间浪费：每个字节只有7位有效数据，最低效率情况下浪费1/8的空间。因此VByte的压缩率不如PForDelta，但其解码速度通常是最快的。Lucene和Elasticsearch等搜索引擎使用VByte的变体来编码倒排索引。

nbytes(x)=⌈⌊log⁡2x⌋+17⌉n_{bytes}(x) = \left\lceil \frac{\lfloor \log_2 x \rfloor + 1}{7} \right\rceil
byte=c  ∣  d6 d5 d4 d3 d2 d1 d0\text{byte} = c \;|\; d_6\, d_5\, d_4\, d_3\, d_2\, d_1\, d_0

PForDelta (Patched Frame of Reference Delta)

PForDelta(Patched Frame of Reference Delta)是一种高性能的分块压缩方法，由Zukowski等人提出。它结合了固定位宽编码的解码速度优势和变长编码的压缩率优势，是目前搜索引擎中压缩率和解码速度综合表现最好的方法之一。PForDelta将d-gap序列分为固定大小的块（通常128或256个整数），对每个块独立选择最优的编码参数。

PForDelta的核心思想是大部分值用固定位宽b编码，少量异常值单独处理。对于一个块中的n个值，PForDelta选择一个位宽b，使得大部分值（如90%）可以用b位表示。这些正常值直接存入一个b位的数组，解码时只需简单的位提取操作，速度极快。对于超出b位表示范围的异常值(exception)，在其正常值数组位置存储低b位作为占位，将高位部分存入单独的异常值数组，并用bitmap标记哪些位置存在异常值。

异常值处理机制是PForDelta的关键创新。通过将少量大异常值分离处理，PForDelta可以用较小的b值编码大部分数据，同时不丢失任何信息。b值的选择通常通过枚举所有可能值（1到32）并计算总压缩大小来确定最优值。异常值的存储方式有两种：链表方式和bitmap方式。链表方式将正常值数组中异常值位置的低b位复用为指向下一个异常值的指针;bitmap方式则使用一个n位的位图标记异常值位置，便于并行解码。PForDelta配合SIMD指令，解码速度可达每秒数亿个整数。

SPFor=n⋅b+n+∣E∣⋅(32−b)S_{PFor} = n \cdot b + n + |E| \cdot (32 - b)

压缩技术对比与实际应用

四种压缩技术在压缩率和解码速度上各有特点。从压缩率来看，PForDelta最优（利用了数据的局部性和异常值分离），其次是VByte（字节对齐带来一定浪费），然后是Delta（大数值优于Gamma），Gamma最差（一元编码效率低）。从解码速度来看，VByte最快（字节对齐，无需位操作），其次是PForDelta（固定位宽可批量解码，但有异常值处理开销），然后是Delta和Gamma（位级编码，需要逐位解析）。

在实际系统中，编码选择需要综合考虑压缩率、解码速度、随机访问能力和实现复杂度。Lucene和Elasticsearch使用VByte的变体，看重其解码速度和实现简单性；许多搜索引擎使用PForDelta，在压缩率和速度间取得最佳平衡。现代系统还采用SIMD（如AVX2）指令加速解码，如StreamVByte将VByte的控制字节与数据字节分离存储以支持向量化解码，PForDelta也利用SIMD进行批量位提取。

索引压缩技术的发展趋势是在保持高压缩率的同时最大化解码速度。新兴方法如SIMD-BP128、Masked VByte和FastPFor等利用SIMD指令集进一步优化解码性能。此外，随机访问能力也成为重要考量，分块PForDelta配合块内固定b值可以在块级别支持随机访问。在实际工程中，还需要考虑索引构建速度、内存使用和压缩对查询规划（如skipping机制）的影响，综合选择最适合的压缩方案。

Compression Ratio: PForDelta>VByte>Delta>Gamma\text{Compression Ratio: } \text{PForDelta} > \text{VByte} > \text{Delta} > \text{Gamma}
Decoding Speed: VByte>PForDelta>Delta>Gamma\text{Decoding Speed: } \text{VByte} > \text{PForDelta} > \text{Delta} > \text{Gamma}

AI 应用场景

搜索引擎倒排索引存储优化

阶段：数据处理与索引构建

解决的问题：大规模文档集合的倒排索引占用过多存储空间，导致磁盘成本高昂且查询时I/O开销大，严重影响查询响应延迟

具体案例：一个拥有10亿文档的搜索引擎，原始倒排索引约500GB。采用d-gap预处理后配合PForDelta编码，索引压缩至约200GB，存储减少60%，同时查询时磁盘读取量大幅降低，平均查询延迟从50ms降至30ms

搜索查询响应加速

阶段：推理部署与在线服务

解决的问题：查询时需要从磁盘读取并解压倒排列表，解码速度直接影响查询延迟，高并发场景下解码成为性能瓶颈

具体案例：电商搜索系统每秒处理10万次查询，使用VByte编码配合SIMD指令优化后，倒排列表解码速度达到每秒5亿个docID，单次查询的倒排列表解码耗时从2ms降至0.3ms，整体查询P99延迟降低40%

推荐系统用户行为序列压缩

阶段：数据预处理与特征工程

解决的问题：用户行为日志中物品ID序列占据大量存储空间，在特征构建和模型训练时数据加载成为瓶颈

具体案例：推荐系统的用户浏览历史日志包含数十亿条记录，每条记录是物品ID序列。使用d-gap加VByte压缩后，存储空间从8TB降至2.5TB，节省约70%，模型训练时的数据加载速度提升3倍

Python 演示

python70 行
import math def compute_dgap(doc_ids):    # 将文档ID序列转换为d-gap差值序列    gaps = [doc_ids[0]]    for i in range(1, len(doc_ids)):        gaps.append(doc_ids[i] - doc_ids[i - 1])    return gaps def gamma_encode(x):    # Gamma编码: 一元编码长度N + 二进制偏移    n = int(math.floor(math.log2(x)))    unary = "0" * n + "1"    offset = bin(x - (1 << n))[2:].zfill(n) if n > 0 else ""    return unary + offset def delta_encode(x):    # Delta编码: 对长度部分(N+1)也使用Gamma编码    n = int(math.floor(math.log2(x)))    length_part = gamma_encode(n + 1)    offset = bin(x - (1 << n))[2:].zfill(n) if n > 0 else ""    return length_part + offset def vbyte_encode(x):    # VByte编码: 每字节7位数据 + 1位继续标志    out = []    while True:        b = x & 0x7F        x >>= 7        if x > 0:            b |= 0x80        out.append(b)        if x == 0:            break    return out def pfordelta_encode(values, b=5):    # PForDelta: 正常值用b位编码, 异常值单独处理    threshold = (1 << b) - 1    normal = []    exceptions = []    bitmap = []    for v in values:        if v <= threshold:            normal.append(v)            bitmap.append(0)        else:            normal.append(v & threshold)            exceptions.append(v >> b)            bitmap.append(1)    return normal, exceptions, bitmap doc_ids = [3, 7, 15, 20, 35, 100, 101, 102]gaps = compute_dgap(doc_ids)print("doc_ids:", doc_ids)print("d-gaps: ", gaps) gamma_total = sum(len(gamma_encode(g)) for g in gaps)print("Gamma total bits:", gamma_total) delta_total = sum(len(delta_encode(g)) for g in gaps)print("Delta total bits:", delta_total) vbyte_total = sum(len(vbyte_encode(g)) for g in gaps)print("VByte total bytes:", vbyte_total) normal, exceptions, bitmap = pfordelta_encode(gaps, b=5)print("PForDelta normal:", normal)print("PForDelta exceptions:", exceptions)print("PForDelta bitmap:", bitmap)
目的：演示d-gap计算及Gamma、Delta、VByte、PForDelta四种索引压缩编码方法的核心实现，对比各编码的输出大小
  1. def compute_dgap(doc_ids):定义d-gap计算函数，将单调递增的docID序列转换为差值序列
  2. gaps = [doc_ids[0]]第一个docID直接保留，作为差值序列的起始值
  3. gaps.append(doc_ids[i] - doc_ids[i - 1])计算当前docID与前一个docID的差值，大幅减小数值大小
  4. n = int(math.floor(math.log2(x)))计算x的最高有效位位置N，确定一元编码长度和偏移位数
  5. unary = "0" * n + "1"一元编码：N个0后跟1，表示数据需要N位偏移
  6. offset = bin(x - (1 << n))[2:].zfill(n) if n > 0 else ""二进制偏移：去掉最高位1后的N位二进制表示，n为0时无偏移
  7. return unary + offset拼接一元编码长度和二进制偏移，得到Gamma编码
  8. length_part = gamma_encode(n + 1)Delta编码关键：对长度N+1使用Gamma编码而非一元编码
  9. b = x & 0x7F取x的低7位作为当前字节的数据位
  10. if x > 0: b |= 0x80如果还有剩余数据，设置最高位（继续标志）为1
  11. out.append(b)将编码后的字节加入输出列表
  12. if x == 0: break所有数据已编码完毕，退出循环
  13. threshold = (1 << b) - 1计算b位能表示的最大值，用于判断异常值
  14. if v <= threshold:判断当前值是否在b位表示范围内
  15. normal.append(v & threshold)异常值：存储低b位作为占位符
  16. exceptions.append(v >> b)异常值高位部分存入单独的异常值数组

常见问答

为什么倒排索引压缩首先要进行d-gap变换?
d-gap变换将单调递增的docID序列转为差值序列，大幅减小数值大小。例如[1000, 1001, 1005, 1010]变为[1000, 1, 4, 5]，后续编码可以使用更少的位数表示。d-gap本身不改变信息量，但为变长编码创造了更小的数值条件。
Gamma编码和Delta编码分别适合什么场景?
Gamma编码适合数值较小的场景(如高频词的d-gap通常很小)，而Delta编码对较大的数值更高效。当x大于等于32时，Delta编码比Gamma编码更节省空间。实际索引中两种编码的适用性取决于d-gap的数值分布。
VByte为什么解码速度快?
VByte是字节对齐的，每个字节包含7位数据和1位继续标志。字节对齐使得CPU可以高效地逐字节读取，避免了位级操作的开销，且现代CPU的缓存行和字节寻址机制对字节对齐数据友好。实现也非常简单，分支少。
PForDelta如何处理异常值?
PForDelta选择一个位宽b，使得大部分(如90%)值可以用b位表示。对于超出b位范围的异常值，在正常值数组中存储其低b位作为占位，将高b位以上的部分存储在单独的异常值数组中，并用bitmap标记哪些位置有异常值。解码时将低b位与异常值数组中的高位拼接恢复原始值。
为什么搜索引擎普遍采用PForDelta?
PForDelta在压缩率和解码速度之间取得了良好平衡。它利用d-gap数据中大部分值较小的特点，用固定位宽快速解码正常值，仅对少量异常值进行特殊处理。配合SIMD指令，解码速度可达数亿docs每秒，同时压缩率优于VByte。
压缩率和解码速度之间为什么存在权衡?
高压缩率通常需要更复杂的编码(如变长位编码)，导致解码时需要逐位解析，增加CPU开销。而高解码速度通常需要字节对齐或固定位宽(如VByte)，但这会浪费部分空间。PForDelta通过分块和异常值处理在两者间取得平衡，是这种权衡的典型方案。

常见误区

误区压缩率越高越好，应该始终选择压缩率最高的编码方法

正解压缩率和解码速度存在权衡，过高的压缩率可能导致解码速度大幅下降。在查询密集的搜索引擎中，解码速度往往比存储空间更重要，需要在两者间取得平衡。

为何常见：直观上认为压缩节省空间总是好的，忽略了查询时解码的开销。

误区d-gap变换本身就是一种压缩方法

正解d-gap变换只是数据预处理步骤，将绝对值转为差值，本身并不减少存储位数。真正的压缩由Gamma、Delta、VByte、PForDelta等编码方法完成，d-gap为这些编码创造了更小的数值条件。

为何常见：d-gap确实大幅减小了数值大小，容易让人误认为它就是压缩。

误区VByte压缩率最低所以不应该使用

正解VByte虽然压缩率不如PForDelta，但解码速度最快且实现简单。Lucene和Elasticsearch使用VByte变体正是因为其解码速度和简单性在工程实践中非常重要，尤其在查询量大的场景下解码速度比存储空间更关键。

为何常见：只关注压缩率指标而忽略解码速度这一同等重要的维度。

误区PForDelta的固定位宽b是全局固定的值

正解PForDelta的b值是动态选择的，通常对每个块枚举可能的b值（1到32），选择使总压缩大小最小的b值。不同块的数据分布不同，最优b值也不同，这是PForDelta自适应优势的体现。

为何常见：PForDelta名字中的Frame of Reference暗示固定位宽，容易误解为全局固定。

误区异常值在PForDelta中会被丢弃以换取压缩率

正解异常值不会被丢弃，而是单独存储在异常值数组中。正常值数组中对应位置存储异常值的低b位，解码时将低b位与异常值数组中的高位拼接，完整恢复原始值，不丢失任何信息。

为何常见：异常值单独处理容易被误解为舍弃，实际上只是分离存储。

参考来源