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

前言

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

正排索引与倒排索引

正排索引指的是文档id到文档内容的映射，也就是将每个文档的内容存储在一个文档ID对应的数据结构中，便于快速地根据文档ID获取文档内容。例如，在关系型数据库中存储的数据，可以看做是一种正排索引的实现

文档1: {"搜索引擎": [1], "是": [2], "强大": [3], "的": [4], "工具": [5]}
文档2: {"信息检索": [1], "对于": [2], "学术研究": [3], "非常": [4], "重要": [5]}
文档3: {"搜索引擎": [1], "和": [3], "信息检索": [5], "密切": [7], "相关": [9]}

倒排索引指的是词项到文档ID的映射，也就是将每个词项出现的文档ID存储在一个词项对应的数据结构中，便于快速地根据词项获取包含该词项的文档ID列表。例如在搜索引擎中使用的索引，就是一种倒排索引的实现

"搜索引擎": [1, 3]
"是": [1]
"强大": [1]
"的": [1]
"工具": [1]
"信息检索": [2, 3]
"对于": [2]
"学术研究": [2]
"非常": [2]
"重要": [2]
"和": [3]
"密切": [3]
"相关": [3]

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

ES

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

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

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

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

可以看到，这个正排索引存储了文档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. 可以转化成如下的倒排索引

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

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

结语

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

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