倒排索引

倒排索引的目标是：给定一个查询词，快速找到所有包含该词的文档。

核心组成

倒排索引由两部分构成：

词典

词典（Vocabulary / Dictionary）存储所有出现过的词（Term），通常使用哈希表或有序数组实现，支持快速精确查找或前缀查找。

每条词典记录包含：

• Term：词本身；
• Document Frequency（DF）：包含该词的文档总数；
• 指针：指向对应的倒排列表。

倒排列表（Posting List）

倒排列表存储某个词出现的位置信息，每条记录（Posting）通常包含：

• Document ID：文档编号；
• Term Frequency（TF）：该词在文档中出现的次数；
• Position List：词在文档中的位置序列（支持短语查询）；
• Offset：字符级偏移（支持高亮显示）。

"apple" → [(Doc1, TF=2, positions=[3,17]), (Doc2, TF=1, positions=[5])]

构建流程

构建倒排索引的主要步骤：

1. 文本预处理

原始文档经过以下处理后才进入索引：

• 分词（Tokenization）：将文本切分为词语。英文按空格/标点分，中文通常使用分词算法（如 jieba、HanLP）；
• 归一化（Normalization）：统一大小写、全半角等；
• 停用词过滤（Stop Words Removal）：移除 "的"、"is"、"the" 等高频无意义词；
• 词干提取 / 词形还原（Stemming / Lemmatization）：将 "running" → "run"，减少词形变体带来的碎片化。

2. 词频统计

对每个文档，统计每个词出现的次数和位置，生成 <Term, DocID, TF, Positions> 的记录。

3. 排序与合并

将所有记录按 Term 排序，相同 Term 的记录合并为一条倒排列表，最终写入磁盘。

4. 压缩存储

倒排列表通常对 DocID 使用差分编码（Delta Encoding） 后再压缩（如 VByte、FOR、PFOR），大幅降低存储占用。

原始 DocID 列表：[1, 5, 10, 11, 20]
差分编码后：    [1, 4,  5,  1,  9]

查询处理

单词查询

直接在词典中查找词，返回对应倒排列表中的 DocID 集合。

布尔查询

多个词之间用 AND / OR / NOT 组合：

• AND（交集）：对两个有序倒排列表做归并交集，时间复杂度 O(m+n)；
• OR（并集）：归并两个列表取并集；
• NOT：对倒排列表做差集。

查询："apple AND banana"
apple  → [Doc1, Doc2]
banana → [Doc1, Doc3]
结果   → [Doc1]        ← 交集

短语查询

需要 Position 信息。例如查询 "apple banana"，要求 banana 的 position = apple 的 position + 1。

相关性排序（TF-IDF & BM25）

全文搜索不只返回"是否匹配"，还需要按相关性排序。最常用的两种模型：

TF-IDF：

• \(\text{TF}(t,d)\)：词 \(t\) 在文档 \(d\) 中的频率，越高说明越相关；
• \(\text{IDF}(t)\)：逆文档频率，包含该词的文档越少，区分度越强。

BM25（Lucene/ES 默认）：

其中：

• \(k_1\)：词频饱和系数，控制 TF 增长的上限，通常取 1.2 ~ 2.0；
• \(b\)：文档长度归一化系数，\(b=0\) 不归一化，\(b=1\) 完全归一化，通常取 0.75；
• \(|d|\)：文档词数；\(\text{avgdl}\)：语料库平均文档词数。

BM25 在 TF-IDF 基础上加入了文档长度归一化，避免长文档因词频绝对值高而获得不公平的优势，是现代搜索引擎的事实标准（Elasticsearch / Lucene 默认打分算法）。

索引更新

静态索引

一次性构建，不支持增量更新，适合离线批量索引场景。

动态更新策略

实时搜索引擎（如 Elasticsearch）通常采用以下策略：

• 内存缓冲区（In-memory Buffer）：新文档先写入内存中的小索引（Segment）；
• 定期刷新（Refresh）：将内存 Segment 写入磁盘，使其可被搜索（默认 1s）；
• 段合并（Segment Merge）：后台将多个小 Segment 合并为大 Segment，降低查询时需扫描的段数；
• 删除标记（Delete Bitmap）：删除/更新文档时先打标记，Merge 时再物理清除。

与向量索引的对比