正排索引与倒排索引

博客:cbb777.fun

全平台账号:安妮的心动录

github: https://github.com/anneheartrecord

下文中我说的可能对，也可能不对，鉴于笔者水平有限，请君自辨。有问题欢迎大家找我讨论 正排索引和倒排索引是搜索引擎中常见的概念 正排索引指的是文档id到文档内容的映射，也就是将每个文档的内容存储在一个文档ID对应的数据结构中，便于快速地根据文档ID获取文档内容。例如，在数据库中存储的数据，可以看做是一种正排索引的实现

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

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

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

在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