倒排索引Inverted index
从分组键找到对应的候选对象列表。
- 核心约束
- 候选归属与分组规则保持一致。
- 适用问题
- 文本检索与向量粗聚类后的候选筛选。
- 边界与取舍
- 在向量 IVF 中，少探测分组会影响召回率。
常见操作#
p、q 为两个倒排列表长度，k 为返回项数；词典查找成本由其实现决定。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 查找某词的倒排列表 | 词典查找 + 读取倒排项 | 哈希词典可期望 ，有序词典可 ；还要考虑词长和解压。 |
| 两个有序列表求交 | 双指针归并的最坏界；跳表、跳跃指针和 galloping 可改变实际工作量。 | |
| 合并多个词的命中结果 | 由访问列表及输出规模决定 | 常先处理较短列表，减少中间结果；排名查询还要读取频率和位置信息。 |
| 新增 / 删除文档 | 与词项数、位置数据和段维护有关 | 例如 Lucene 先写新段，用删除标记并在合并时清理；不是一个固定 操作。 |
时间与空间#
- 时间复杂度
- 查询按访问的倒排项和输出结果计费
- 存储空间
- 词典 + 倒排项 + 可选位置 / 跳跃信息
压缩降低存储和 I/O，但增加解码工作；不能只按文档数给统一空间常数。
概念与变体#
- 文本倒排
- 由词项定位文档或出现位置。
- 向量 IVF
- 由粗量化单元定位候选向量，召回受 nprobe 等配置影响。
工程中的应用#
1 个案例 · 附源码先用粗量化器缩小搜索区域，再扫描被选中的倒排列表。
附源码片段 · 检索与计算
基础原理参考资料
Introduction to Information Retrieval · Boolean query processing有序倒排列表求交和优先处理短列表。
Lucene 9.12 · Index file formats分段索引、倒排与相关文件布局。