什么是正排索引与倒排索引？

前言

正排索引和倒排索引是信息检索场景中常见的概念，比如数据库、搜索引擎等技术中，大部分关系型数据库都是使用正排索引存储记录，一些文档型数据库，比如ES使用的则是倒排数据库。

正排索引与倒排索引

正排索引指的是文档id到文档内容的映射，也就是将每个文档的内容存储在一个文档ID对应的数据结构中 ，便于快速地根据文档ID获取文档内容。例如，在关系型数据库中存储的数据，可以看做是一种正排索引的实现 [code] 文档1: {“搜索引擎”: [1], “是”: [2], “强大”: [3], “的”: [4], “工具”: [5]} 文档2: {“信息检索”: [1], “对于”: [2], “学术研究”: [3], “非常”: [4], “重要”: [5]} 文档3: {“搜索引擎”: [1], “和”: [3], “信息检索”: [5], “密切”: [7], “相关”: [9]} [/code]

倒排索引指的是词项到文档ID的映射，也就是将每个词项出现的文档ID存储在一个词项对应的数据结构中，便于快速地根据词项获取包含该词项的文档ID列表。例如在搜索引擎中使用的索引，就是一种倒排索引的实现 [code] “搜索引擎”: [1, 3] “是”: [1] “强大”: [1] “的”: [1] “工具”: [1] “信息检索”: [2, 3] “对于”: [2] “学术研究”: [2] “非常”: [2] “重要”: [2] “和”: [3] “密切”: [3] “相关”: [3] [/code]

正排索引和倒排索引是搜索引擎实现的核心技术，它们的组合可以快速地根据关键词搜索相关文档，并返回相关度最高的结果

ES

Elasticsearch就是一种倒排索引的实现，它使用倒排索引来快速地搜索和查询文档

在ES中，每个文档都被存储为一个JSON格式的文档，每个文档都有一个唯一的ID。ES使用倒排索引来存储每个词项出现的文档ID，以及每个文档中每个词项的出现位置等信息。这使得ES能够高效的搜索和查询文档

具体的例子如下
Hello world,this is a sample document.
可以转化成如下的正排索引

[code] document_id | position | term ------------|----------|------- 1 | 1 | Hello 1 | 2 | world 1 | 3 | this 1 | 4 | is 1 | 5 | a 1 | 6 | sample 1 | 7 | document [/code]

可以看到，这个正排索引存储了文档ID、单词位置和单词本身。如果我们要查找包含单词document的文档，我们可以根据这个索引快速找到该单词所在的位置，并获取对应的文档ID

相比之下，倒排索引存储了每个单词出现在哪些文档中，即存储了单词->文档ID的键值对，举个例子
Document 1: Hello world, this is a sample document.
Document 2: The quick brown fox jumps over the lazy dog.
Document 3: The sky is blue, the grass is green.
可以转化成如下的倒排索引

[code] term | document_ids ---------|------------- Hello | 1 world | 1 this | 1 is | 1 a | 1 sample | 1 document | 1 The | 2, 3 quick | 2 brown | 2 fox | 2 jumps | 2 over | 2 the | 2, 3 lazy | 2 dog | 2 sky | 3 is | 3 blue | 3 grass | 3 green | 3 [/code]

可以看到，这个倒排索引存储了每个单词出现的文档ID，如果我们要查找包含单词document的文档，可以快速找到包含该单词的文档ID

结语

本文粗略的介绍了正排与倒排索引的区别，并举了倒排索引的实现ES为例子。

创作不易，如果有收获欢迎点赞、评论、收藏 ，您的支持就是我最大的动力。