2. 倒排索引原理：数据结构、词项与文档映射、压缩技术
倒排索引（Inverted Index）是全文检索与搜索引擎的核心数据结构。它通过“词项→文档列表”的映射，将线性扫描的 O(n) 复杂度降低为 O(1) 查找 + 倒排列表合并。本节从数据结构、映射机制与压缩技术三个层面展开，为后续领域建模中的版本管理与嵌套文档索引奠定基础。
2.1 倒排索引核心数据结构
倒排索引由两个主要部分组成：词典（Dictionary）与倒排列表（Posting List）。词典存储所有不重复的词项（Term），每个词项指向一个倒排列表；倒排列表记录包含该词项的所有文档 ID 及位置信息。
| 组件 | 存储内容 | 典型实现 | 查询作用 |
|---|---|---|---|
| 词典 | 词项字符串、词频（DF）、指向倒排列表的指针 | 哈希表、B+ 树、有限状态转换器（FST） | 快速定位词项是否存在，获取倒排列表入口 |
| 倒排列表 | 文档 ID 序列、词频（TF）、位置偏移、字段标识 | 有序数组、跳跃表、位图 | 合并多个词项的文档集合，计算相关性 |
| 位置信息 | 词项在文档内的偏移位置列表 | 变长整数数组、差值编码 | 短语查询、邻近搜索、高亮定位 |
关键设计原则：词典必须支持快速单点查找（O(1) 或 O(log n)），倒排列表必须支持高效合并与跳跃遍历。领域建模中，文档嵌套结构会引入多级字段路径，词典需要存储“字段路径:词项”的复合键。
2.2 词项与文档映射机制
倒排索引的映射过程分为索引构建与查询合并两个阶段。构建阶段将文档集合转化为词典与倒排列表；查询阶段根据用户输入词项，合并倒排列表返回结果。
2.2.1 索引构建流程
- 分词（Tokenization）：将文档文本切分为词项序列，去除标点、统一大小写。
- 语言处理（Normalization）：词干提取、停用词过滤、同义词扩展。
- 倒排记录生成：为每个词项记录 (docID, tf, positions) 三元组。
- 排序与合并：按词项排序后，合并相同词项的记录，形成倒排列表。
- 词典写入：将词项与倒排列表指针写入词典结构。
2.2.2 查询合并策略
| 查询类型 | 合并算法 | 时间复杂度 | 应用场景 |
|---|---|---|---|
| AND（与） | 双指针归并，取交集 | O(m + n) | 精确匹配、过滤条件 |
| OR（或） | 双指针归并，取并集 | O(m + n) | 模糊搜索、同义词扩展 |
| PHRASE（短语） | 位置偏移滑动窗口匹配 | O(k * p) | 精确短语、引文搜索 |
| NOT（非） | 差集运算 | O(m + n) | 排除特定文档 |
领域建模启示：在嵌套文档结构中，每个字段路径（如
author.name）可视为独立字段域。倒排索引需要为每个字段域维护独立的词典空间，或使用复合键 field_path:term 进行统一索引。版本管理场景下，同一文档的不同版本会共享词项但拥有不同 docID 范围。
2.3 倒排列表压缩技术
倒排列表通常包含大量整数序列（文档 ID、位置偏移），直接存储会占用巨大空间。压缩的目标是在不损失查询性能的前提下，将存储空间压缩至原始大小的 20%~40%。
2.3.1 常用压缩算法对比
| 算法 | 原理 | 压缩比 | 解码速度 | 适用场景 |
|---|---|---|---|---|
| 差值编码 (Delta Encoding) | 存储相邻文档 ID 的差值，而非原始 ID | 中等 | 极快 | 所有倒排列表的基础预处理 |
| 变长整数 (Varint) | 每个字节用 7 位存储数据，1 位标识是否继续 | 2x~4x | 快 | 通用整数压缩，实现简单 |
| Simple-8b | 将多个小整数打包到 64 位字中，选择最优编码模式 | 3x~6x | 中等 | 批量解码，适合 SSD 存储 |
| PForDelta (PFD) | 大部分数据用固定位宽编码，异常值单独存储 | 4x~8x | 中等 | 高压缩比需求，CPU 密集型 |
| Roaring Bitmap | 将整数区间拆分为 2^16 大小的块，块内用位图或数组 | 5x~10x | 快 | 大规模集合运算，位图加速 |
2.3.2 差值编码 + Varint 示例
假设原始文档 ID 序列为 [5, 12, 23, 45, 67]，经过差值编码后变为 [5, 7, 11, 22, 22]。再使用 Varint 编码将每个差值压缩为 1~2 个字节：
原始序列: [5, 12, 23, 45, 67]
差值序列: [5, 7, 11, 22, 22]
Varint 编码: [0x05, 0x07, 0x0B, 0x16, 0x16]
存储空间: 5 字节 (原始需 20 字节，压缩比 4x)
压缩选型注意：领域驱动设计中，文档嵌套结构会导致倒排列表长度分布极不均匀。顶层字段的倒排列表可能包含百万级文档 ID，而深层嵌套字段可能只有几十个。建议对长列表使用 PForDelta 或 Roaring Bitmap，对短列表使用 Varint 或 Simple-8b，避免统一算法带来的空间浪费。
2.3.3 压缩对查询性能的影响
- 解码开销：每次合并操作需要解码倒排列表，压缩比越高，解码耗时越长。
- 跳跃表配合：在差值编码基础上构建跳跃表，可以跳过大量无需解码的文档 ID，减少解码次数。
- 块级解码：现代搜索引擎（如 Lucene）采用块级压缩，每次解码一个块（128~256 个文档 ID），平衡压缩比与解码速度。
- 内存 vs 磁盘：热数据（高频词项）的倒排列表常驻内存，使用 Roaring Bitmap 加速；冷数据使用高压缩比算法存储于磁盘。
版本管理场景下的压缩策略：当同一文档存在多个版本时，倒排列表中的文档 ID 需要携带版本号（如
docID_version）。建议将版本号编码到文档 ID 的高位，保持差值编码的连续性。例如：docID << 16 | version，这样同一文档的不同版本在倒排列表中自然相邻，差值更小，压缩效果更好。