最近接触了公司一个内部后台的产品设计需求，其中有部分数据存储在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最好是连续的，这样压缩效率最好。
网友评论