为什么ES的搜索效率对比数据库的正排索引更快呢？

倒排索引原理

正排索引

正排是以文档ID为关键字，表中记录文档中每个字的位置信息，查询时扫描表中每个文档中字的信息， 直到找出所有包含查询关键字的文档。

倒排索引

倒排表是以字或词作为关键字进行索引，表中关键字所对应的记录项记录了出现这个字或词的所有文档ID。

正排索引是文档ID到关键字的映射，倒排索引是从关键字到文档ID的映射

倒排索引的核心组成

1、单词词典：记录所有文档的单词，一般都比较大。还会记录单词到倒排列表的关联信息。

2、倒排列表：记录了单词对应的文档集合，由倒排索引项组成。倒排索引项包含如下信息：

文档ID，用于获取原始信息

单词频率TF，记录该单词在该文档中的出现次数，用于后续相关性算分

位置Position，记录单词在文档中分词的位置，用于语句搜索(phrase query)

偏移Offset，记录单词在文档的开始和结束位置，实现高亮显示

Trie

Lucene在4.x之前使用trie，在4.x之后就使用FST。

Trie树，即前缀树，字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

它的优点是：最大限度地减少无谓的字符串比较，缺点是后缀不共享。

FST（Finite State Tranducer）

1. 有环
2. 它有且只有一个初始状态，可以有0个或多个final状态
3. 它在同一个时间点只能在一个状态中

cat/0

deep/1

do/2

dog/3

dogs/4

december/5

november/6

红色加粗线条代表一个final状态