第 203 题：倒排索引的压缩，PForDelta与SIMD优化？
题目
倒排索引的压缩，PForDelta与SIMD优化？
完整讲解
一、倒排索引与压缩需求
倒排索引：词项 → 文档 ID 列表（posting list）；便于关键词检索，但 posting 列表 可能很长，存储与内存占用大、缓存不友好。压缩：在保证可解码的前提下减小 posting 的存储与传输量，并尽量不牺牲解码速度。
二、PForDelta
- 思想：将 posting 中的 doc ID 转为差值（delta）序列，再用 PFor（Patched Frame of Reference）：选一个基准位数 b，多数 delta 用 b 位存，超出 b 位的异常值单独存到「补丁」区。解码时先按 b 位批量解，再填异常值。
- 优点：压缩比高、解码可 SIMD 化（按块处理）；适合 delta 分布集中、长列表。实现：选 b（如 90% 的 delta 用 b 位可表示）、块大小与补丁区组织。
三、SIMD 优化
- SIMD（单指令多数据）：CPU 一条指令处理多个数据（如 128/256 bit 一次处理多个整数），适合批量解码整数序列。
- 应用：PForDelta、VByte 等解码时，按块（如 128 个整数）用 SIMD 做并行解码，显著提高吞吐；也可用于比较、合并有序列表（如合并多词 posting 做 AND）。需注意对齐与边界、不同 CPU 指令集（SSE/AVX/NEON）的适配。
四、其他
- VByte：变长整数编码，简单但解码分支多，SIMD 化不如 PFor 直接。SIMD 压缩常与 cache 友好 的块组织结合，减少内存访问延迟。
面试要点
- 能说明倒排索引为何需要压缩（posting 大、存储与缓存）；能简述 PForDelta 思想：delta + 基准位数 + 异常补丁。
- 能解释 SIMD 在解码中的作用：批量整数解码、提高吞吐；能提及与 PForDelta 的配合。
- 能列举其他编码（如 VByte）及 SIMD 在合并 posting 上的应用。
记忆要点
- 倒排压缩=减小 posting 存储；PForDelta=delta+基准位+异常补丁，解码可 SIMD。
- SIMD=批量解码、合并列表；与块组织结合提高 cache 友好与吞吐。