前言
上周四被面试官问到了倒排索引，虽用过 ES，但不知道这玩意儿说不过去啊。
倒排索引（Inverted Index）是一种用于快速查找文档或文档集合中包含特定词汇的数据结构。与传统的正排索引（Forward Index）不同，倒排索引是通过词汇表（词汇-文档关系表）来构建的。
在倒排索引中，每个词汇都会映射到包含该词汇的文档列表。当需要查找包含特定词汇的文档时，只需直接查询倒排索引，而不需要遍历整个文档集合。
基本原理：
- 收集文档：首先，需要收集要建立索引的文档，这可以是文本文档、网页、数据库记录等。
- 分词：对每个文档进行分词，将文档中的文本切分成词汇。这个过程通常包括去除停用词（常见但无实际意义的词汇）等预处理步骤。
- 建立词汇表：建一个词汇表，其中包含所有文档中出现过的词汇。这个词汇表可以看作是一个映射，将每个词汇与包含该词汇的文档列表关联起来。
- 构建倒排索引：对每个词汇，创建一个倒排列表（Inverted List），记录包含该词汇的文档的位置或标识。倒排列表通常按照文档的频率或其他相关信息进行排序。
- 查询：当需要查询包含特定词汇的文档时，直接查找倒排索引，找到包含该词汇的文档列表。这使得检索效率非常高效。
实际示例（结合正排索引）
正排索引：
假设有一本书，这本书有一个正排索引。正排索引记录了这本书的每一页的内容以及对应的页码。我们可以根据页码迅速找到书中的任意一页。
| 页码 | 内容 |
|---|---|
| 1 | 书的封面和版权信息 |
| 2 | 序言 |
| 3 | 第一章的内容 |
| 4 | 第一章的继续 |
| ... | ... |
| 200 | 最后一章的内容 |
| 201 | 附录 |
倒排索引:
然后，假设按照内容中的词汇，建立倒排索引，记录每个词出现在这本书的哪些页。
| 词汇 | 出现的书籍和页码 |
|---|---|
| 第一章 | 页3, 页4, ... |
| 最后 | 页200, ... |
| 内容 | 页3, 页200... |
| ... | ... |
参考文献
[1] 倒排索引-维基百科