倒排索引的基本概念

索引

索引本质上如图 1 所示，从纵向（即文档）这个维度来看，每列代表文档包含了哪些单词，比如文档 1 包含了词汇 1 和词汇 4，而不包含其他单词。从横向（即单词）这个维度来看，每行代表了哪些文档包含了某个单词。比如对于词汇 1 来说，文档 1 和文档 4 中出现过词汇 1，而其他文档不包含词汇 1。

搜索引擎的索引其实就是实现“单词—文档”矩阵的具体数据结构。可以有不同的方式来实现上述概念模型，比如倒排索引、签名文件、后缀树等方式。但是各项实验数据表明，倒排索引是单词到文档映射关系的最佳实现方式。

:::info 倒排索引与关系型数据库索引类似，会根据关键字做排序。但关系型数据库索引一般是对主键创建，然后索引指向数据内容；而倒排索引则正好相反，它是针对文档内容创建索引，然后索引指向主键，这就是这种索引被称为倒排索引的原因。 :::

倒排索引（Inverted Index）基本概念

• 文档（Document）：文档是搜索引擎处理的基本单位，一切数据都可以看作是文档，如一本书的内容、一个 Word 文档、一条微信聊天记录、一个网页等。
• 文档集合（Document Collection）：由若干文档构成的集合称为文档集合。比如大量的图书或者微信聊天的聊天记录等都可以看作文档集合。
• 文档编号（Document ID）：在搜索引擎内部，会为文档集合内每个文档赋予一个唯一的内部编号，作为唯一标识，偶尔也会简称 DocID。
• 单词编号（Word ID）：搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一标识。
• 倒排索引（Inverted Index）：倒排索引是实现单词—文档矩阵的一种具体存储形式。通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：单词词典和倒排文件。
• 单词词典（Lexicon）：搜索引擎通常的索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针。
• 倒排列表（PostingList）：倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项（Posting）。根据倒排列表，即可获知哪些文档包含某个单词。
• 倒排文件（Inverted File）：所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称为倒排文件，倒排文件是存储倒排索引的物理文件。

倒排索引实例

如图 6 所示的倒排索引已经是一个非常完备的索引系统。有了这个索引系统，搜索引擎可以很方便地响应用户的查询，比如用户输入查询词“Facebook”，搜索系统查找倒排索引，从中可以读出包含这个单词的文档，这些文档就是提供给用户的搜索结果，而利用单词频率信息、文档频率信息即可对这些候选搜索结果进行排序，计算文档和查询的相似性，按照相似性得分由高到低排序输出，此即为搜索系统的部分内部流程。

参考文章：https://gitbook.cn/books/5e81f2fbfb14aa44b0ea286e/index.html 参考书籍：《Elastic Stack 应用宝典》