倒排索引

定义

倒排索引(Inverted Index)是一种从内容映射到位置的索引结构:与"文档到词"的正排方向相反,它记录每个词项(term)出现在哪些文档中,故称"倒排"。它是全文检索系统的基石。

结构

倒排索引由两部分组成:词典(term dictionary),存放所有去重后的词项,常用 FST、B 树或哈希组织;倒排表(posting list),记录包含该词项的文档 ID 列表,可附带词频、位置、偏移等信息以支持短语查询和相关性打分。倒排表通常按文档 ID 递增排列并做差值编码压缩。

查询过程

对查询语句分词后,取出各词项的倒排表,通过求交(AND)、求并(OR)得到候选文档,再按 TF-IDF 或 BM25 等模型打分排序。

应用

Lucene、Elasticsearch、Solr 以及各大搜索引擎的核心均为倒排索引;MySQL、PostgreSQL 的全文索引也采用同一思想。