什么是倒排索引

前言

上周四被面试官问到了倒排索引，虽用过 ES，但不知道这玩意儿说不过去啊。

倒排索引（Inverted Index）是一种用于快速查找文档或文档集合中包含特定词汇的数据结构。与传统的正排索引（Forward Index）不同，倒排索引是通过词汇表（词汇-文档关系表）来构建的。

在倒排索引中，每个词汇都会映射到包含该词汇的文档列表。当需要查找包含特定词汇的文档时，只需直接查询倒排索引，而不需要遍历整个文档集合。

基本原理：

1. 收集文档：首先，需要收集要建立索引的文档，这可以是文本文档、网页、数据库记录等。
2. 分词：对每个文档进行分词，将文档中的文本切分成词汇。这个过程通常包括去除停用词（常见但无实际意义的词汇）等预处理步骤。
3. 建立词汇表：建一个词汇表，其中包含所有文档中出现过的词汇。这个词汇表可以看作是一个映射，将每个词汇与包含该词汇的文档列表关联起来。
4. 构建倒排索引：对每个词汇，创建一个倒排列表（Inverted List），记录包含该词汇的文档的位置或标识。倒排列表通常按照文档的频率或其他相关信息进行排序。
5. 查询：当需要查询包含特定词汇的文档时，直接查找倒排索引，找到包含该词汇的文档列表。这使得检索效率非常高效。

实际示例（结合正排索引）

正排索引：

假设有一本书，这本书有一个正排索引。正排索引记录了这本书的每一页的内容以及对应的页码。我们可以根据页码迅速找到书中的任意一页。

倒排索引:

然后，假设按照内容中的词汇，建立倒排索引，记录每个词出现在这本书的哪些页。

参考文献

[1] 倒排索引-维基百科