2、倒排索引核心原理
倒排索引（Inverted Index）是全文检索与搜索引擎的基石数据结构。与正向索引（Forward Index）以文档为中心不同，倒排索引以词项（Term）为中心，记录每个词项出现在哪些文档中，从而将“文档→词项”的映射关系反转为“词项→文档列表”。这种结构使得给定一个查询词，系统能在毫秒级定位到包含该词的所有文档。
2.1 倒排索引的数据结构
一个完整的倒排索引由三个核心部分组成：词典（Dictionary）、倒排列表（Posting List）和倒排文件（Inverted File）。词典存储所有不重复的词项及其元信息；倒排列表存储每个词项对应的文档ID序列及位置信息；倒排文件则是词典与倒排列表在磁盘上的物理存储形式。
| 组件 | 存储内容 | 典型实现 | 内存/磁盘 |
|---|---|---|---|
| 词典 | 词项字符串、文档频率（DF）、指向倒排列表的指针 | 哈希表、B+树、跳跃表 | 常驻内存 |
| 倒排列表 | 文档ID序列、词频（TF）、位置偏移、Payload | 有序数组、可变长编码块 | 磁盘 + 缓存 |
| 倒排文件 | 词典与倒排列表的序列化二进制块 | 分段（Segment）合并存储 | 磁盘持久化 |
2.2 词项与文档ID映射
词项与文档ID的映射是倒排索引的核心逻辑。构建过程分为三个步骤：分词（Tokenization）、归一化（Normalization）和倒排写入（Inversion）。每个文档经过分词后，提取出所有词项，再对每个词项记录其出现的文档ID及位置信息。
2.3 倒排列表的合并
当用户输入多个查询词（如“缓存 一致性”）时，系统需要从词典中分别取出“缓存”和“一致性”的倒排列表，然后执行合并操作。最常见的合并类型是交集（AND）和并集（OR）。
| 合并类型 | 语义 | 算法 | 时间复杂度 |
|---|---|---|---|
| AND（交集） | 文档同时包含所有词项 | 双指针线性扫描，跳过较小DocID | O(N + M) |
| OR（并集） | 文档包含任意一个词项 | 双指针归并，去重输出 | O(N + M) |
| NOT（差集） | 文档包含词项A但不包含B | 双指针扫描，输出A有B无的DocID | O(N + M) |
2.4 倒排列表的压缩
倒排列表可能包含数百万甚至数十亿个文档ID，直接存储会消耗大量磁盘和内存。因此，必须对倒排列表进行压缩。压缩的核心思路是利用文档ID的增量编码（Delta Encoding），将绝对ID转换为相邻ID之间的差值，然后对差值进行可变长编码。
| 压缩算法 | 编码方式 | 压缩比 | 解码速度 | 适用场景 |
|---|---|---|---|---|
| Variable Byte (VByte) | 每字节1位标志位 + 7位数据 | 中等 | 快 | 通用场景，平衡压缩与速度 |
| Simple-8b | 64位字内打包多个小整数 | 高 | 快 | 批量处理，差值分布集中 |
| PForDelta (PFD) | 分块编码，异常值单独处理 | 很高 | 中等 | 大规模索引，高压缩比需求 |
| Roaring Bitmaps | 分桶 + 位图/数组混合 | 高 | 极快 | 现代搜索引擎，支持快速位运算 |
2.5 压缩与合并的协同优化
在实际系统中，压缩和合并不是孤立的两个阶段，而是需要协同设计。例如，使用Roaring Bitmaps时，AND合并可以直接在位图层面执行位与运算，比解码为数组再扫描快一个数量级。而使用VByte编码时，合并前需要先解码，但解码后的数组可以直接用于双指针扫描。
2.6 本章小结
- 倒排索引由词典和倒排列表组成，词典常驻内存，倒排列表存储在磁盘并缓存到内存。
- 词项与文档ID映射通过分词、归一化和倒排写入三步完成，文档ID必须连续递增且列表有序。
- 倒排列表合并使用双指针线性扫描，AND/OR/NOT操作的时间复杂度均为O(N+M)。
- 倒排列表压缩依赖增量编码和可变长编码，Roaring Bitmaps和PForDelta是工业界主流选择。
- 压缩与合并需要协同设计，根据词项频率选择不同的压缩策略以优化整体性能。