搜索索引与查询边界：实时搜索与近实时搜索架构对比 - 第2节
2.1 倒排索引原理：从文档到词项的映射
倒排索引（Inverted Index）是搜索引擎的核心数据结构，它将传统“文档→词项”的正向关系反转，建立“词项→文档”的快速查找路径。这种结构使得搜索引擎能够在毫秒级内定位包含特定查询词的文档集合。
核心思想： 倒排索引以词项（Term）为键，以包含该词项的文档列表（Posting List）为值，实现从查询词到文档的快速映射。
2.1.1 正向索引 vs 倒排索引
| 对比维度 | 正向索引（Forward Index） | 倒排索引（Inverted Index） |
|---|---|---|
| 数据结构 | 文档ID → 词项列表 | 词项 → 文档ID列表 |
| 查询方式 | 遍历所有文档，扫描每个文档的词项 | 直接定位词项，获取文档列表 |
| 时间复杂度 | O(N × L)，N为文档数，L为平均文档长度 | O(1) 或 O(log M)，M为词项数 |
| 适用场景 | 文档内部词频统计、文档聚类 | 全文搜索、关键词匹配 |
以下 SVG 展示了倒排索引的构建过程，从原始文档集合到最终的倒排列表结构：
2.2 文档处理流程：从原始文本到索引词项
原始文档在被加入索引之前，必须经过一系列文本处理步骤。这些步骤的质量直接影响搜索的召回率和准确率。
2.2.1 文档处理三阶段
- 分词（Tokenization）： 将连续文本切分为独立的词项单元。中文分词比英文复杂，需要处理歧义切分（如“南京市长江大桥”）。
- 去停用词（Stop Words Removal）： 过滤掉高频但无实际检索意义的词，如“的”、“是”、“在”、“the”、“a”等，减少索引体积并提升查询效率。
- 词干提取（Stemming）： 将不同形态的词还原为词干形式，如“running”→“run”、“flies”→“fly”，使同一概念的不同变体能够被统一检索。
实践建议： 中文搜索通常不进行严格的词干提取，而是采用词典分词 + 细粒度切分（如二元分词）的组合策略，以平衡精度与召回。
2.2.2 处理流程对比：英文 vs 中文
| 处理步骤 | 英文处理 | 中文处理 |
|---|---|---|
| 分词 | 按空格和标点切分，简单直接 | 需要词典匹配 + 统计模型（如HMM、CRF） |
| 去停用词 | 停用词表较小（约100-200词） | 停用词表较大（约300-500词），含虚词、助词 |
| 词干提取 | Porter Stemmer、Snowball 等算法成熟 | 通常不做词干提取，改用同义词扩展 |
| 归一化 | 小写化、去除标点 | 全角/半角转换、繁简体转换 |
以下 SVG 展示了文档从原始文本到索引词项的完整处理流水线：
2.3 索引存储结构：磁盘与内存的协同
倒排索引的存储结构需要平衡查询速度、更新效率和存储空间。现代搜索引擎通常采用分层存储策略，将热数据放在内存，冷数据放在磁盘。
2.3.1 核心存储组件
- 词项字典（Term Dictionary）： 存储所有唯一词项及其元数据（如文档频率DF）。通常使用B+树或哈希表实现，支持快速词项查找。
- 倒排列表（Posting List）： 每个词项对应的文档ID列表及附加信息（词频、位置等）。采用压缩编码（如差分编码、Variable Byte编码）减少存储空间。
- 词项索引（Term Index）： 词项字典的前缀索引，通常使用FST（Finite State Transducer）存储在内存中，实现O(len(query))的查找复杂度。
- 跳表（Skip List）： 在倒排列表上构建多层索引，加速列表合并操作（AND/OR查询）。
2.3.2 存储结构对比
| 组件 | 存储位置 | 数据结构 | 查询复杂度 | 更新方式 |
|---|---|---|---|---|
| 词项索引 | 内存 | FST（有限状态转换器） | O(len(query)) | 段合并时重建 |
| 词项字典 | 磁盘 + 缓存 | B+树 / 哈希表 | O(log N) | 追加写 + 合并 |
| 倒排列表 | 磁盘 | 差分编码 + 压缩块 | O(K)，K为文档数 | 段内不可变，段级合并 |
| 跳表 | 磁盘 + 内存 | 多层链表 | O(log K) | 段合并时重建 |
注意： 倒排索引的“不可变性”是设计核心。一旦写入段（Segment），索引数据不再修改。更新操作通过新建段 + 段合并（Segment Merge）实现，这保证了读取的高并发性能，但也带来了写放大问题。
2.3.3 Lucene 索引存储架构
以 Lucene 为代表的搜索引擎库采用“段（Segment）”作为索引存储的基本单位。每个段是一个独立的倒排索引，包含完整的词项字典和倒排列表。查询时并行搜索所有段，合并结果。
// Lucene 索引目录结构示例
index/
├── _0.fdt // 存储文档的原始字段值
├── _0.fdx // 字段索引，用于快速定位字段值
├── _0.fnm // 字段元数据（字段名、类型等）
├── _0.nvd // 归一化因子（用于评分）
├── _0.nvm // 归一化因子元数据
├── _0.pos // 词项位置信息
├── _0.pay // 负载数据（payload）
├── _0.tim // 词项字典（Term Dictionary）
├── _0.tip // 词项索引（Term Index），FST结构
├── _0.doc // 倒排列表（文档ID + 词频）
├── segments.gen // 段生成文件
└── segments_N // 段元数据（当前活跃段列表）
以下 SVG 展示了 Lucene 段内索引存储结构的层次关系：
2.4 本章小结
- 倒排索引 是搜索引擎的基石，通过“词项→文档”的映射实现快速查询。
- 文档处理流程 包括分词、去停用词、词干提取三个核心步骤，中文处理比英文更复杂。
- 索引存储结构 采用分层设计：内存中的FST词项索引 + 磁盘上的B+树词项字典 + 压缩倒排列表 + 跳表加速。
- 段（Segment） 是索引存储的基本单位，段内数据不可变，通过段合并实现更新。