倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。有两种不同的反向索引形式：

  • 一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。
  • 一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。

定义与两种形式讲清了”是什么”，但倒排索引的完整图景还包括：构建流程（分词→词典→posting）、与正排索引的对照、以及工程上的压缩与更新问题。本文补全，让倒排索引从名词变成可解释的机制。

正排 vs 倒排：一次对照

  • 正排（forward index）：文档 → 词列表（doc1: [ai, chip, export]）。”查文档含哪些词” O(1)，但”查含某词的文档”需扫全部文档
  • 倒排（inverted index）：词 → 文档列表（chip: [doc1, doc7, doc99]）。把”查词”的扫描成本预计算成索引，与数据库索引”用空间换查询路径”同一思想

倒排索引的两部分：

  • 词典（dictionary/term dictionary）：全部词项的有序集合（B+Tree 或 FST/哈希），支持词项查找与前缀查询
  • 倒排列表（posting list）：每个词项对应的文档 ID 列表（完全倒排再带词位置/词频，支持短语查询与相关性打分）

构建流程四步

  1. 采集与解析：文档抽取正文（HTML 去标签、PDF 解析）
  2. 分词：英文按空格/标点+词干化；中文需词典/统计分词（IK/jieba/ES IK 插件）——分词质量决定检索质量上限
  3. 归一化：大小写统一、停用词过滤（the/的）、同义词归并
  4. 索引写入：词项入词典、(docId, 位置, 词频) 入 posting；批量构建时先按词排序再合并（MapReduce 式）

查询执行：posting 的布尔运算

查询 “ai AND chip”：取两词 posting list 做有序链表归并交（docId 有序，双指针 O(m+n)）；OR 做并、NOT 做差。短语查询 “ai chip” 再用位置信息验证相邻（位置差=1）。相关性排序（TF-IDF/BM25）用 posting 中的词频与文档长度计算——倒排列表携带的信息量决定了能支持多复杂的查询。

工程问题一：posting 压缩

posting list 可能极长（高频词百万 docId），存储与 IO 是瓶颈。压缩手段：

  • 差值编码（delta encoding）：存相邻 docId 差值（小数字）
  • 变字节/伽马编码（VByte/PForDelta）：小整数用更少字节
  • 跳表（skip list）：posting 上加跳指针加速归并交时的跳过

工程问题二：动态更新

倒排索引天然适合批量构建，实时插入新文档怎么办：

  • LSM 式分段（Lucene/ES 方案）：新文档写入内存段（immutable segment），后台 merge 合并段；删除用 delete bitmap 标记、merge 时物理清除
  • 不可变段带来并发友好（读不加锁）与缓存友好，代价是 merge 的 IO 与”段越多查询越慢”（需控制段数量）

应用面：不止全文搜索

  • 搜索引擎（Google/ES/Lucene）：核心结构
  • 数据库全文索引：MySQL FULLTEXT、PG tsvector 本质都是倒排
  • 日志分析：关键词定位日志行
  • 推荐/广告：item → 用户列表的反向映射同构
  • 编译器/静态分析：符号 → 引用位置表

一句话本质

倒排索引 = 把”内容→位置”的正向关系反转为”关键词→位置”的预计算映射，用构建期成本换查询期 O(词项定位+posting 归并)；词典、posting、压缩、分段更新四件套构成它的全部工程内涵。理解它，ES/数据库全文索引/搜索系统的行为（为什么分词重要、为什么删除是标记、为什么段要 merge）就都有了统一解释。