倒排索引（Inverted Index）

倒排索引（Inverted Index）

一、先从正排索引说起

要理解倒排索引，先看正排索引是什么。

正排索引（Forward Index）是我们最自然的思考方式：从文档出发，找出文档里包含哪些词。

文档ID → 内容 → 提取所有词

举个例子，假设有三篇文章：

正排索引就是按文档整理出词汇表：

这种结构存数据没问题，但搜索的时候很慢。

比如用户搜“苹果”，需要遍历所有文档，逐个检查是否包含这个词。文档少还好，如果有几百万篇文章，每次都全表扫描，效率极低。

二、什么是倒排索引

倒排索引（Inverted Index）的思路正好反过来：

从词出发，记录这个词出现在哪些文档里。

把上面的数据倒过来：

这就是倒排索引。用户搜“苹果”，直接从倒排索引里找到这个词对应的文档列表，瞬间返回结果。

三、两者对比

打个比方：

• 正排索引 = 一本书前面的目录，按章节找内容
• 倒排索引 = 一本书后面的关键词索引，按词找位置

四、倒排索引的组成

倒排索引由两部分组成：

1. 词项字典（Term Dictionary）

按字母顺序排列的所有词，每个词指向它的倒排列表。

苹果 → [Doc1, Doc2] 手机 → [Doc1, Doc3] 拍照 → [Doc3] ...

2. 倒排列表（Posting List）

每个词对应的文档列表，通常会存储：

存储的越详细，查询功能越丰富，但存储空间也越大。

五、构建过程

第一步：文档分词

原始文档：

• Doc1: “苹果手机好用”
• Doc2: “我喜欢吃苹果”

分词后：

• Doc1: [“苹果”, “手机”, “好用”]
• Doc2: [“我”, “喜欢”, “吃”, “苹果”]

第二步：建立词到文档的映射

第三步：记录附加信息（增强版）

有了位置信息，就能支持“苹果手机”这种短语搜索，因为可以判断“苹果”和“手机”在Doc1中相邻出现。

六、查询过程

用户搜索“苹果手机”：

1. 分词：[“苹果”, “手机”]
2. 查倒排索引：
   • 苹果 → [Doc1, Doc2]
   • 手机 → [Doc1, Doc3]
3. 求交集（AND）：两个词都出现的文档 → [Doc1]
4. 返回结果：Doc1

如果是 OR 查询，则合并列表 → [Doc1, Doc2, Doc3]

七、与 BM25 的关系

BM25 是计算搜索结果相关性的算法，它的核心就是基于倒排索引。

score(D, Q) = Σ IDF(q) × (TF × (k₁+1)) / (TF + k₁ × (1 - b + b × |D|/avgDL))

用到的数据都来自倒排索引：

• TF（词频）：倒排列表里存着
• IDF（逆文档频率）：根据词在多少个文档中出现计算

所以倒排索引是搜索引擎的基础，BM25 是排名的算法。

八、在向量数据库中的应用

像 Milvus 支持稀疏向量，底层用的就是倒排索引的思路：

# 稀疏向量本质上就是 {词: 权重} 的倒排格式sparse_vector={"苹果":0.8,"手机":0.6}# 查询时，也是用倒排索引快速定位collection.search(data=[{"苹果":0.7,"手机":0.5}])

稠密向量（BERT、BGE）做语义搜索，倒排索引（BM25、SPLADE）做关键词匹配，两者经常结合使用。

九、优缺点

优点

• 查询速度快，O(1) 级别
• 支持布尔查询（AND/OR/NOT）
• 可扩展性强，适合海量数据

缺点

• 构建需要时间，更新成本高
• 存储空间比原文本大（需要存索引）
• 无法处理同义词、语义匹配（这一点靠稠密向量补救）

十、典型应用场景

总结

倒排索引的核心思想就一句话：

不查文档找词，而是查词找文档。

这种反向的思路，让全文搜索从全表扫描变成了查字典，速度提升了成百上千倍。无论是 Google 搜索、数据库索引，还是向量检索，背后都离不开倒排索引。