2. 倒排索引基础：什么是倒排索引、核心数据结构、在搜索引擎中的应用
2.1 从正排到倒排：索引结构的演进
在信息检索领域，传统数据库使用正排索引（Forward Index）：以文档ID为键，存储文档内容。当需要查找包含某个词的文档时，必须扫描所有文档，效率极低。
倒排索引（Inverted Index）则反转了这种映射关系：以词项（Term）为键，记录该词出现在哪些文档中，以及出现的位置、频率等信息。这种结构是搜索引擎实现毫秒级全文检索的核心基础。
核心思想： 正排索引 = 文档 → 词项；倒排索引 = 词项 → 文档列表。倒排索引将“查找”操作的时间复杂度从 O(N) 降低到 O(1)（基于词典的哈希或跳表查找）。
2.2 核心数据结构
倒排索引由两大核心组件构成：词典（Dictionary / Lexicon）和倒排表（Posting List）。
| 组件 | 存储内容 | 核心作用 | 典型实现 |
|---|---|---|---|
| 词典 | 所有不重复的词项（Term）及其元信息 | 快速定位词项在倒排表中的偏移位置 | 哈希表、B+树、FST（有限状态转换器） |
| 倒排表 | 包含该词项的文档ID列表及位置信息 | 支持布尔查询、短语查询、评分计算 | 有序数组、跳表、位图（Roaring Bitmaps） |
| 词项元信息 | 文档频率（DF）、词频（TF）、偏移指针 | 用于查询优化和相关性评分 | 固定长度编码、变长编码 |
2.2.1 词典（Dictionary）
词典是倒排索引的入口。每次查询首先在词典中查找词项，获取其在倒排表中的位置指针。词典的查询性能直接决定搜索延迟。
- 哈希表：O(1) 查询，但不支持前缀查询和范围查询，内存占用较高。
- B+树：支持有序遍历和前缀匹配，适合磁盘存储，但查询性能略低于哈希。
- FST（Finite State Transducer）：Lucene 核心实现，内存紧凑，支持模糊查询和自动补全，查询性能接近哈希。
2.2.2 倒排表（Posting List）
倒排表是倒排索引的主体，存储了每个词项对应的文档列表。为了节省空间并加速查询，现代搜索引擎对倒排表进行了大量优化。
关键优化技术：
- 差分编码（Delta Encoding）：只存储相邻文档ID的差值，大幅减少整数位数。
- 变长编码（Variable Byte / VInt）：小整数用更少字节存储，压缩比可达 3:1 以上。
- Roaring Bitmaps：将文档ID分桶，桶内使用位图或数组，兼顾压缩率和交集/并集运算性能。
2.3 倒排索引在搜索引擎中的应用
搜索引擎的整个查询生命周期都围绕倒排索引展开。以下是一个典型查询的处理流程：
- 查询解析：对用户输入进行分词、去除停用词、词干还原，生成词项列表。
- 词典查找：在词典中定位每个词项的倒排表指针。
- 倒排表合并：根据查询类型（AND/OR/短语）对多个倒排表进行交集、并集或位置匹配。
- 评分排序：利用 TF-IDF、BM25 等算法计算文档相关性得分，返回 Top-K 结果。
2.4 倒排索引 vs 传统数据库索引
理解倒排索引与传统 B-Tree 索引的差异，有助于在架构设计中做出正确的技术选型。
| 对比维度 | 传统 B-Tree 索引 | 倒排索引 |
|---|---|---|
| 索引对象 | 结构化字段（ID、时间、状态） | 非结构化文本（全文内容） |
| 查询类型 | 精确匹配、范围查询、前缀匹配 | 词项匹配、短语查询、模糊搜索 |
| 相关性排序 | 不支持（仅按字段排序） | 原生支持 TF-IDF、BM25 等评分 |
| 存储结构 | 有序树结构（B+树） | 词典 + 倒排表（跳表/位图） |
| 典型场景 | OLTP 系统、主键/唯一索引 | 搜索引擎、日志分析、推荐系统 |
架构警示： 不要试图用关系数据库的 LIKE '%keyword%' 替代倒排索引。当数据量超过百万行时，全表扫描的延迟会从毫秒级退化到秒级甚至分钟级。倒排索引是搜索引擎的基石，也是业务数据库与搜索系统之间数据同步的核心目标。
2.5 倒排索引的构建与更新
倒排索引的构建分为全量构建和增量构建两种模式。在业务数据库一致性保障场景中，增量构建是核心挑战。
- 全量构建：扫描所有文档，分词后构建完整的词典和倒排表。适用于初始导入或数据重建。
- 增量构建：监听数据库变更事件（CDC），仅对新增、修改、删除的文档更新倒排索引。需要解决“索引与数据库一致”的问题。
2.6 本章小结
- 倒排索引通过“词项 → 文档列表”的映射，实现了对海量文本的毫秒级检索。
- 核心数据结构包括词典（哈希表/B+树/FST）和倒排表（跳表/位图），两者共同决定了索引的查询性能和存储效率。
- 在搜索引擎中，倒排索引支撑了从查询解析、词典查找、倒排表合并到评分排序的完整链路。
- 增量构建是保持倒排索引与业务数据库一致性的关键环节，后续章节将深入探讨 CDC 机制和一致性保障策略。