1、倒排索引基础
1.1 倒排索引定义
倒排索引（Inverted Index）是信息检索领域的核心数据结构，其设计思想源于“由词找文档”的检索需求。与正排索引“由文档找词”的存储方式相反，倒排索引以词项（Term）为键，记录该词项出现在哪些文档中，以及在该文档中的位置、频率等信息。这种结构使得搜索引擎能够在毫秒级完成对海量文档的全文检索。
核心思想：倒排索引的本质是“词项 → 文档列表”的映射关系。在架构设计中，这种映射的构建效率、存储压缩率和查询性能直接决定了搜索引擎的吞吐量与延迟。
1.2 核心数据结构
倒排索引由两大核心组件构成：词典（Dictionary）和倒排表（Posting List）。两者协同工作，形成完整的检索链路。
| 组件 | 存储内容 | 核心作用 | 典型实现 |
|---|---|---|---|
| 词典 | 所有不重复的词项及其元信息 | 接收查询词，快速定位到对应的倒排表 | 哈希表、B+树、FST（有限状态转换器） |
| 倒排表 | 文档ID列表、词频、位置信息等 | 返回包含该词项的所有文档及匹配细节 | 有序数组、位图、跳跃表、Roaring Bitmap |
1.3 词典（Dictionary）
词典是倒排索引的入口，负责将用户输入的查询词转换为倒排表的指针。在架构设计中，词典需要同时满足低内存占用和高查询吞吐两个约束。
- 哈希表：O(1) 查询复杂度，但内存开销大，不支持前缀/模糊查询。
- B+树：支持范围查询和有序遍历，磁盘友好，但查询复杂度为 O(log n)。
- FST（Finite State Transducer）：Lucene 核心词典实现，将词项压缩为最小 DAG，内存占用极低，支持前缀查询。
架构选型建议：在内存充裕的实时检索场景（如电商搜索），优先使用哈希表；在磁盘索引、海量词项场景（如网页搜索），FST 是业界标准方案。
1.4 倒排表（Posting List）
倒排表是倒排索引的“数据体”，记录了每个词项对应的文档集合。其存储结构直接影响查询合并、排序和过滤的效率。
- 文档ID列表：按升序排列的有序整数数组，支持二分查找和跳表加速。
- 词频（TF）：记录词项在每篇文档中出现的次数，用于 BM25 等相关性打分。
- 位置信息：记录词项在文档中的偏移位置，支持短语查询和邻近搜索。
- Payload：可扩展的附加信息，如文档权重、时间戳、自定义元数据。
// 倒排表逻辑结构示例（JSON 化表示）
{
"term": "搜索引擎",
"doc_freq": 3,
"postings": [
{ "doc_id": 1, "tf": 2, "positions": [15, 42] },
{ "doc_id": 5, "tf": 1, "positions": [7] },
{ "doc_id": 12, "tf": 3, "positions": [23, 56, 89] }
]
}
1.5 正排索引与倒排索引对比
正排索引（Forward Index）以文档为维度组织数据，倒排索引以词项为维度组织数据。两者在存储、查询和更新模式上存在本质差异。
| 对比维度 | 正排索引 | 倒排索引 |
|---|---|---|
| 数据组织 | 文档 → 词项列表 | 词项 → 文档列表 |
| 典型查询 | “文档ID=5 包含哪些词？” | “包含‘搜索引擎’的文档有哪些？” |
| 查询效率 | 按文档ID随机访问，O(1) 单文档读取 | 按词项合并文档列表，O(k) 多文档聚合 |
| 更新模式 | 追加新文档，无需修改已有结构 | 追加文档需更新多个倒排链，写放大明显 |
| 存储冗余 | 词项在每篇文档中重复存储 | 词项只存一次，文档ID列表高度压缩 |
| 典型场景 | 文档详情展示、字段提取 | 全文检索、关键词匹配、相关性排序 |
架构陷阱：倒排索引的写放大效应在实时索引场景中尤为突出。每新增一篇文档，可能涉及数百个词项的倒排链追加操作。业界通过“分段合并（Segment Merge）”和“延迟刷新（Near Real-Time）”策略来缓解这一瓶颈。
1.6 倒排索引与正排索引的协同架构
在成熟的搜索引擎架构中，倒排索引和正排索引并非互斥，而是互补共存。倒排索引负责快速定位候选文档集合，正排索引负责提取文档的完整字段用于展示和二次过滤。
1.7 本章小结
- 倒排索引以“词项 → 文档列表”的映射关系，实现了高效的全文检索。
- 词典（Dictionary）和倒排表（Posting List）是倒排索引的两大核心组件，各自有丰富的实现变体。
- 正排索引与倒排索引在数据组织、查询模式和更新代价上存在显著差异，两者在架构中互补共存。
- 理解倒排索引的基础原理，是后续章节中讨论版本管理、兼容设计和索引迁移的前提。