最近接触了公司一个内部后台的产品设计需求，其中有部分数据存储在Elastic search数据库中（下文简称ES库），这种Nosql的数据库，以往只是进行简单的增删改查，没深入了解过，接触最多的还是关系型数据库比如MSSQL Server、Mysql之类的。接触ES库给我最大的感觉就是一个字『快』，特别是多条件联合查询，在数据量过10亿的情况下，可明显感知搜索速度的差异。本次正好借本文介绍一下ES库的基本原理。

  介绍

    ES库是一个分布式可扩展的数据库，主要用于大并发的大数据量的实时数据检索。快速的检索是有代价的，代价就是不支持类似事务管理，不支持回滚，删除数据可就真删除了。任何事情都有代价的，要想速度快就要减少一切非必要的操作。ES的这种特点决定了它不适合做OLTP类型的数据存储，因为不支持事务这一条就pass掉了。

  基本概念

    对于一个数据库产品，按照惯例，首先要了解一下这个数据库的组成，比如表结构、表字段啥的，ES库比较特殊，他是Nosql数据库，是非结构化存储的，它是面向文档型的数据库，一条数据就是一个文档。下图为关系型数据库与es库的结构对比。

可以看到，ES库在层次上和关系型数据库类似，不过在物理存储结构上就不同了，ES的数据通过Json格式存储。与ES交互，通过HTTP的Restful API方式，比如我想往ES中插入一条数据，可以通过：PUT  /project/contract/129001，来实现，PUT后边的路径分别表示的是：索引名，类型名，文档ID

{

    "ID" :    7892,

    "city_name" :      "beijing",

    "project_name" :      "KMlop",

    "create_date": "2019-08-25",

    "detail" :    "this is fist pj"

}

对于ES的增删改操作，本次不去详细描述，本文主要是分享ES的快速搜索的原理，下面我们开始了解ES快速搜索数据的原理。

索引

让我们回想一下，对于关系型数据库，如何加快速度访问的呢？第一反应就是：上索引。不管上的是聚集索引还是非聚集索引，总之，我给需要检索的列上了索引，搜索速度就上去了，那么同理，ES想要快速访问数据，也要有索引，不过ES的索引的原理和关系型的不同了，原因是上文我们提到，ES是非结构化存储，数据以JSon存储，关系型数据库的B+tree索引没办法用在这种的数据结构上，ES用的索引是倒排索引。

那什么是倒排索引呢？

倒排索引的思路是不去索引列值而是索引关键字。比如对于一个存储网站内容的列，如果索引的是这个列的内容，那么如果检索一个关键字，就需要索引全扫描，索引量如果很大或者多个关键字联合搜索就会很慢，如果索引的是关键字，那么对于这种关键字类型的查询速度就就会非常快，因为索引存的是关键字对应的记录ID。倒排索引，建立索引之前需要对内容先进行切词。

举个例子，比如有以下三条记录：

ID    name              age

1      micah latin      23

2      Jones              23

3      pink                56

4      robotic            63

假设切词直接按照单个字切分，那么nane列的切分结果为：

ID        name

1      micah/ latin

2    Jones

3    pink 

4    robotic

age列切分结果：

ID        age

1       23

2       23

3       56

4       63

其中的ID是文档ID，斜杠表示的是切分位置。  切分后就可以组织倒排索引了，

对于name列，倒排索引结果为：

Term Dictionary    Posting List

Jones                    [2]

latin                        [1]

micah                      [1]

pink                        [3]

robotic                    [4]

对于age列，倒排索引结果：

Term Dictionary    Posting List

23                            [1，2]

56                            [3]

63                            [4] 

其中，Term Dictionary是切分后的结果，可简单理解为关键字，Posting List为包该含关键字的文档ID。建立倒排索引之后，检索包含关键字的记录就非常容易了，比如检索age=23的记录，就可以很快得出是记录ID为1和2的。我们从例子上看，Term Dictionary 是有序的，因为如果不排序，那么检索索引的时间复杂度就是O(n)，如果是有序的，就可以通过二分法查找，复杂度就变成LogN了，检索效率进一步提升。ES是面相大数据量检索的，如果Term Dictionary 非常大，几十亿，如果索引放不进内存，查找效率又会减下来，有没有办法呢？想一下，这时候的数据结构是不是就可以通过B+tree索引再索引一次？这就组成了二级索引，B+tree索引用来索引Term Dictionary ，而Term Dictionary 索引posting list。

压缩算法

  考虑这样一种情况，索引列是性别，那么假设性别就两种，那么每一个性别下索引的记录ID会非常多，这时候就需要对索引进行压缩。因为记录ID是整形的，就可以想到存储的时候只需要第一个记录的完整ID，其余的记录只需要记录与前一个记录的差值就可以，这样就实现了对记录ID的压缩存储，而用这种方式存储数据，就需要存储的数据结构是变化的，因为很明显，存储数字100000，和存储10不能用一个数据结构，这样会造成空间的浪费。那么怎么实现变长的数据存储呢？把需要存储的posting list进行分组，每组用一段bit存储。每段bit开头给出这段bit中用几个bit存储一个数字。

压缩的步骤为：

1、通过delta编码算法，把posting list中的整数进行增量编码。编码的步骤为：

1）用Elisa Gamma Code的方式编码x的长度：Cr (floor(log(x)) + 1);

2）求出x的二进制表示，并且用Cr做前缀

3）去掉x二进制表示中的第一个1

2、将第一步得到的增量编码进行分块（一块128个数据，上图为了解释原理，3个数字一个块）。

3、对每个分块统计其中最大的数需要多少个bit，把这个数放到数据块头部，读取数据时用于判断多少位表示一个数据。

总结

ES为了极致的查询速度，舍弃了一切不必要的操作（事务管理）。通过倒排全文索引配合使用二级索引，进一步提高检索效率，对于索引数据进行增量压缩，以便索引可以放入内存，这是CPU时间换内存空间的策略。根据压缩策略算法可知，如果记录ID是随机的，那么压缩效率就会很低，所以记录的ID最好是连续的，这样压缩效率最好。