Es之正排索引与倒排索引

概要

很早就研究了Es倒排索引的具体实现，但对倒排索引和正派索引的定义不是那么清晰，本文就是简述本人对二者的理解。
正排索引和倒排索引的概念来源于

正排索引是文档(ID)到关键词的映射（已知文档找关键词），倒排索引是关键词到文档(ID)的映射（已知关键词找文档）。
注意这里的文档是指文档ID,而非文档本身，但通过文档ID可以找到文档的数据实体，
这里的文档ID并非必须是MySQL中的主键，Es中的Doc Id，MongoDB的ObjectId，而是任何可以定位到文档的唯一特定词。

ps:明确我们这里讨论的文档是文档包含多个字段，字段对应具体值的结构，比如MySQL、Es、MongoDb等都是这种层级结构，很多博文说文档映射关键词，就是本文中字段的具体值到所包含关键词的映射过程。

一、正排索引

正排索引（forward index），也叫attribute or profile index，是通过对doc某特定字段（正排字段）的具体值建立索引，在将具体值分词后，得到不少于1个的关键词，索引中记录了这些关键词内容、位置、次数等信息。常用来进行过滤，统计，排序或算分使用。

正排索引中“正"指的是从doc field—>doc field keys的映射过程 ，其优点是结构简单、建立方便，适用于文档量较小的情况。对于大规模的文档集，正排索引的检索效率较低，因为需要扫描所有文档以找到包含特定关键字的文档。

假设有一系列文档，文档中有若干字段，其中以name字段建立正排索引形式如下：

name字段值	关键词信息	文档(ID)
my is tom,hello tom	my,is, tom, hello	1
you are tom	you,are,tom	2
my is bob,he is john	my,is,bob,he,john	3

当然了组织索引的具体数据结构暂不讨论，可以B+Tree、HashMap、SkipList等等。
但是我们可以通过正排索引快速的定位某个文档是否包含特定关键词,以及关键词次数、位置等信息。

显而易见，正排索引更符合人类整理信息的习惯，构建简单，但查找效率低下，一般数据检索采用倒排索引，除非在特定情况下，否则正排索引实用性价值不大。

二、倒排索引

倒排索引（inverted index）是通过对doc某特定字段的具体值进行分词后，得到不少于1个的关键词，根据这些关键词建立索引，索引中记录了关键词所对应文档的ID、位置、次数等信息。

倒排索引中的"倒"指的是从doc field keys->doc id的映射过程。由于每个关键词对应的文档在动态变化，所以倒排索引的建立和维护都较为复杂，但是在查询的时候由于可以一次得到查询关键字对应的所有文档，所以效率很高。在全文检索中，检索的快速响应是一个最为关键的性能，而索引建立由于在后台进行，尽管效率相对低一些（比如Es文档插入后默认1s后才能搜到），但不会影响整个搜索引擎的效率。

关键词信息	文档(ID)
my	1,3
is	1,2,3
tom	1,2
hello	1
you	2
are	2
bob	3
he	3
john	3

在实际应用中，通常会将正排索引和倒排索引结合起来使用。首先使用倒排排索引对文档集进行初筛，找到包含查询关键字的文档；然后使用正排索引对文档进行排序等操作。

三、Q&A

1. MySQL的 B+Tree索引是正排索引还是倒排索引？

首先声明本人观点，MySQL的 B+Tree索引既不符合正排索引定义也不符合倒排索引定义,没必要非要将其关联起来，不管是正排，倒排，还是B+Tree，都是提高查询效率的方法。非要关联的话，B+Tree索引具有正排和倒排的某些特性，聚簇索引偏向正排索引，非聚簇索引偏向倒排索引，聚簇索引通过主键组织文档数据，非聚簇索引是辅助提升查询效率的手段。主键类似文档ID,非聚簇索引字段值类似关键词。

2. 正排索引有应用吗？

在Es中就有正排索引，被称为Doc Values，其将文档中每个字段的值采用列式结构存储，通常存储在磁盘中，查询是会被加载到内存中。主要用于存储和检索字段原始值，以便进行快速的聚合、排序和脚本操作，特别适用于数值、日期、布尔和不分词字符串的字段。

四、参考

1]：Lucene 正排索引、倒排索引
2]：ES倒排索引、正排索引
3]：Difference between Inverted Index and Forward Index
4]：Forward index
5]：Indexing for Beginners
6]：elasticsearch实战-doc values列式存储算法
7]：Es doc values正排索引