ElasticSearch检索的核心-倒排索引解读

前言

ElasticSearch为什么适合做检索服务器？

因为快啊，大佬！

为什么快啊？

因为倒排索引啊！

什么是倒排索引？

这个，就要细细分析一下了，这篇文章可能写的不是那么全，但是我也会尽量总结所有重点！希望能帮到大家，爱你们！

索引是什么？

首先，从基础玩起来，倒排索引，分为倒排+索引

索引这个词汇，在数据库的出镜率非常高，我基础比较差，所以，我在这里会从头进行学习解读，希望大家理解，如果对索引非常了解的兄弟，请直接跳过这一段

首先，什么是索引。

索引是一种特殊的数据库数据结构

首先，一般我们认为的查找，就是从头检索到尾，也就是从开头遍历到结尾，这样的时间复杂度是O(n)

索引，就是将数据库表中的某一列或几列以特定的数据结构存起来，比如B-Tree，Hash等，这样我们去查找的时候，复杂度就会下降到O(log)或者O(1)

把索引想成目录，把数据库想成书的内容。所以索引的核心作用就是加快数据的检索和查询速度。

上面那句话我感觉就是说了和没说一样。。你用目录来找内容肯定比一页页遍历翻书快多了，下面咱们就该走一下索引的原理了，睁大眼睛，我们走起。

索引的原理

首先，上面说了，索引是一种数据结构，这种结构很可能是B-Tree，Hash等等

一般的数据库索引数据结构基本都是Tree，Tree这个东西，涉及一种叫做平衡多叉树的数据结构

也有一些数据库索引使用hash桶做数据结构，但大部分都是Tree

平衡多叉树就是b-tree，b+ tree的核心，这玩意儿就是搞查询用的

平衡多叉树的基本原理

1. 这不是二叉结构，有一种树叫做平衡二叉树，多叉和二叉是不同的玩意。
2. B树和B+树的核心都是平衡多叉树
3. 所有节点关键字是按递增次序排列，并遵循左小右大原则
4. 树中每个节点最多含有m个节点（m>=2）

这样似乎有点抽象。。。不过这个只是理论

后面我单独开贴来说一下B树,B+树系列吧

常规的索引数据结构如下

这篇文章不是讲B树，hash的，所以我就直接进入正题了，直接讲ElasticSearch。

ElasticSearch的倒排索引是什么？

上面说了，索引相当于是目录，是查询内容的指向标一类的东西

那么，倒排索引又是什么？和一般的索引有什么不一样的嘛？

现在我来和大家一起复习一下。

首先索引的机制我已经简单的介绍了，是一种数据库中使用的数据结构。

一般是B树，hash之类的。

但是ElasticSearch用的既不是B树也不是hash，用的是倒排索引

ElasticSearch的核心就是搜索，所做的一切都是为了提高搜索的效率

ElasticSearch是一个非关系型的数据库，和Mysql之类的关系型数据库有本质区别。

所以用的索引技术也不相同

倒排索引，就是为了方便检索的一种数据结构

倒排索引检索 VS 传统检索

如果我们在关系型数据库中，例如Mysql中进行查找，我们只能用like来实现模糊检索

例如，我们现在要检索一篇含有 “Ak47” 的文章，需要编写如下sql语句

select * from article where content like '%Ak47%';

这样的查找，我们是没法使用索引的，因为我们需要进行全扫描，你不可能将整个文章内容都作为索引

这样检索效率很差，也没法完成复杂性检索。

更别提复杂的全文检索了，所以，mysql不适合用来做检索引擎。

更多情况下，很多数据库是以一个主键，作为每个文档的唯一标识

例如传统索引下

文档ID	content
1	Ak47突击步枪
2	Ak74u突击步枪
3	Ak74s突击步枪
4	Akm突击步枪

倒排索引就不一样了，他是以单词作为索引，然后将对应的文档id和索引进行关联，类似链表，然后生成倒排索引结构

word	文档ID
Ak	1,2,3,4
Ak47	1
Ak74	2,3
Akm	4
突击	1,2,3,4
步枪	1,2,3,4
突击步枪	1,2,3,4

所以，检索的时候只要去通过词汇，直接就能找到匹配的文档

相当于，假设你要搜索 “Ak47”，直接根据word去找匹配的词汇，然后取到文档ID就行了。

这个不就很快？所以倒排索引的好处就体现出来了。

所以倒排 Vs 传统，倒排完胜。

词汇的形成是通过分词进行切分的，分词的核心在这里就不做讨论了，如果想看，可以看下我以前的一篇blog

中文分词的算法分析

倒排索引的数据结构

ElasticSearch的核心首先是 Apache Lucene，而倒排索引也是出自Lucene的特殊的数据结构

首先我们看上一节，倒排索引其实可以用一个字典逻辑来表达

{
    "Ak":[1,2,3,4],
    "AK47":[1],
    "Ak74":[2,3]
}

这个字典里面的key值是分词后的单词，对应的value是文档的ID

根据Lucene的概念，这个key值被称为 Term

如果要进行检索，我们通过term去找对应的值

一般如果文档数量很大，那么对应的term表也一样很大，全都放到内存会出事的，所以，Lucene定义了一个索引，叫做 Term Index，汉语词典索引

一般我们不能把所有的Term表都放到内存里，所以这个是指向第二层索引表指路牌

第二层，全称 Term Dictionary，汉语叫做索引表

根据lucene的概念，这个value值被称为 Postings List，汉语被称为倒排表。

记录表不仅仅只是一个文档ID的list，不要被我的简写搞混淆了，记录表里面包含了大概如下信息

字段	字段功能
文档ID	包含单词的所有文档唯一id
词频（TF）	记录 Term 在每篇文档中出现的次数，用于评分
位置（Position）	记录 Term 在每篇文档中的分词位置（多个），用于做词语搜索
偏移（Offset)	记录 Term 在每篇文档的开始和结束位置，用于高亮显示

看个图

这是他们三者之间的关系

这就是倒排索引的大概数据结构。

Term Index解析

Trem Index, 走检索的时候，这个相当于是入口，也就是目录。

通过Terms Index能够快速地在Terms Dictionary中找到你的想要的Term。

存储模式

Terms Dictionary 存储 Term 的索引文件叫做 Terms Index，存储的格式是 .tip

数据结构

Term Index是由多个FST组成的，FST这个东西展开说太多了，咱们这篇文章不太够，所以我这里就简单描述下，后面再开团讲这个。

Trem Index里面主要包含

字段	字段功能
header	header头
IndexStartFP	当前的FSTIndex信息的起始位置
FSIndex	起始位置索引，FST算法存储

它的数据结构如下：

Trem Index的结构是Burst-Trie实现的，这里面主要包含了Term的一些前缀

它的结构类似

这里简单的画了个图，您就凑合看吧

当然也有复杂的，类似这样

当然这里不可能是包含所有的term，这里和mysql之类的索引是不一样的，这里存的只是term的前缀。

所以，当我们搜索”Ak47”的时候，这里面大概率会存储着”A”的前缀，找到A之后再去匹配Term Dictionary

Term Dictionary解析

Term Dictionary 存储了所有的Term值

如果用精准一点的描述，Term Dictionary存储了Term和对应的Postings List指针。

存储模式

Terms Dictionary 的文件存储格式为 .tim，存储了Term和对应的Postings List指针。

数据结构

先看个图

tim主要包含了如下字段

这里面，Nodeblock是核心，先看这张图，Nodeblock其实类似一个树

Terms Dictionary 通过 .tim 后缀文件存储，

其内部采用 NodeBlock 对 Term 进行压缩前缀存储，

处理过程会将相同前缀的的 Term 压缩为一个 NodeBlock，

NodeBlock 会存储公共前缀，然后将每个 Term 的后缀以及对应 Term 的 Posting 关联信息处理为一个 Entry 保存到 Block

Entry是一个关联的信息，一般记作元数据

Block可以互相包含，因为前缀很可能相同

具体流程类似：

Postings List解析

Postings List就是前面我们说的，包含文档ID，文档位置，词频等信息，这些数据相互独立，并且在Postings List中也有这样的表现

存储模式

Postings List 被拆成三个文件存储：

1. .doc后缀文件：记录 Postings 的 docId 信息和 Term 的词频
2. .pay后缀文件：记录 Payload 信息和偏移量信息
3. .pos后缀文件：记录位置信息

数据结构

这三个文件是做查询使用的，所以用的最多的应该.doc文件

我这里举一个.doc的数据结构的例子，进行分析

.doc文件里存储了Term的文档对应的ID，.doc的数据结构如下

1. TermFreqs 存储文档号和对应的词频
2. SkipData是搜索的时候判断对应的文档ID在不在一个交集当中，进行跳表的

倒排索引的查询逻辑

首先接着上面那个数据结构，我们把数据结构连接起来，看一下下面的图。

1. 通过Term index，这里面记录着前缀
2. 通过前缀快速定位到Term dictionary的offset
3. 通过offset定位到Postings List

这就是大概的倒排索引查询逻辑，这里面较为抽象，但是将基本的查询步骤都刻画出来了。

结尾

这篇文章，我感觉写的不好，我预计，我后序还是会修修补补，大家看到了，如果我有错误，马上指出来！

最近学习进入了一个新的阶段，希望我自己能打通任督二脉，希望我可以做到吧。

太多的感谢说不出口

我知道是你们在我的背后

不断鞭策

信念不会随时间陈旧

停不下执笔的手

踌躇茫然也只是短暂停留

最后感谢一些文章的作者，你们帮了我很多

tim&&tip文件
Lucene 倒排索引原理
Elasticsearch索引原理