财务平台亿级数据量毫秒级查询优化之elasticsearch原理解析

财务平台进行分录分表以后，随着数据量的日渐递增，业务人员对账务数据的实时分析响应时间越来越长，体验性慢慢下降，之前我们基于mysql的性能优化做了一遍，可以说基于mysql该做的优化已经基本上都做了，本次是基于elasticsearch对其做进一步的性能优化

正文
1mysql索引原理

基于mysql最常用也最直接有效的性能优化也就是添加索引。

mysql索引是怎么实现的呢？数据库最基本的查询算法是顺序查找，时间复杂度为O（n），显然在数据量很大的时候很低，优化的查询算法有二分查找，二叉树查找，虽然查找效率提高了，但是各自对检索的数据都有要求，二分查找检索被要求数据是有序的，而二叉树查找只能用于二叉树上，但是数据本身的组织结构不可能完全满足各种数据结构，例如，理论上不可能同时将两列都按顺序进行组织，所以在数据之外，数据库系统还维护者满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。

索引是什么？索引是存储引擎用于快速找到记录的一种数据结构，这是索引的基本功能，主要基于hash，b+tree。

我们开发当中一般用到都是mysql innoDB引擎，采用的是b+tree。

b+tree的优势主要体现在查询性能上，在单元素查询时，b+tree会自顶层向下逐层查找节点，最终找到我们需要的叶子节点，范围查询时，b+tree找到叶子节点的起始位置，通过叶子节点链表依次查询数据，直到范围结束为止。

参考上面的示意图

总结：基于b+tree的mysql索引，当这个树的形状瘦低的时候查询效率就会很快，因为查找磁盘的io次数很少，但是如果这个树的形状胖高的时候，查询磁盘的次数就会比较多，那么查询效率就会越来越慢，所以基于mysql索引的性能优化，索引是有限制的，适量的添加索引会对查询效率有明显提升，但是索引过量就适得其反，不但查询效率会降低，也会影响其他操作的效率，因为其他操作的时候也是需要维护索引的。

1elasticsearch索引原理

elasticsearch底层的索引原理是倒排索引，使用场景一般是OLAP，支持rest风格json数据格式交互的全文检索引擎，开源，面向文档设计，实时检索，索引可以无限扩展，只要你的服务器的磁盘、内存足够大。

我们先看一个列子

一个字段有一个自己的倒排索引。18,20这些叫做term，而[1,3]就是postinglist。Posting list就是一个int的数组，存储了所有符合某个term的文档id。

term Dictionary
term排序后的集合，方便二分查找，有了term Dictionary之后就可以在磁盘上查找到具体的document，磁盘的读操作非常昂贵，一次大概需要10ms时间，不同存储方式的磁盘性能不一样，所以为了减少磁盘的读取次数就必要把一些数据缓存到内存中，但是term Dictionary会有很多，不能完整的放到内存中，于是就有了termindex
term index
可以理解为就是英文词典的目录，它是一棵树的结构

示意图

这棵树不会包含所有的term，它只包含term的一些前缀，通过term index可以快速地定位到term dictionary的某个offset，然后从这个位置再往后顺序查找，大大减少了磁盘访问次数

示意图

所以term index不需要存下所有的term，而仅仅是他们的一些前缀与Term Dictionary的block之间的映射关系，再结合FST(Finite StateTransducers)的压缩技术，可以使term index缓存到内存中
为什么elasticsearch比mysql快
mysql只有 termdictionary这一层，是以树的方式存储在磁盘上的。检索一个term需要若干次的磁盘访问操作，而elasticsearch，在term dictionary的基础上添加了term index来加速检索，term index以树的形式缓存在内存中。从term index查到对应的term dictionary的block位置之后，再去磁盘上找term，大大减少了磁盘的访问次数。
term index在内存中是以FST的形式保存的，其特点是非常节省内存。Term dictionary在磁盘上是以分block的方式保存的，一个block内部利用公共前缀压缩，比如都是Ab开头的单词就可以把Ab省去。这样term dictionary可以更节约磁盘空间。
压缩技术
用FST压缩term index之外，对posting list也有压缩。

联合索引查询
以上都是单field索引，如果多个field索引的联合查询，比如查询age=18 AND gender=女，倒排索引如何满足快速查询的要求呢？大致过程如下：根据过滤条件 age=18 的先从term index找到18在term dictionary的大概位置，然后再从term dictionary里精确地找到18这个term，然后得到一个posting list或者一个指向posting list位置的指针。然后再查询gender=女的过程也是类似的。最后得出age=18 AND gender=女，就是把两个 posting list做一个“与”的合并
1、skip list
2、bitset 二进制，直接按位与
总结
elasticsearch就是尽量将磁盘里的东西搬进内存，减少磁盘随机读取次数(同时也利用磁盘顺序读特性)，结合各种压缩算法，高效使用内存，从而达到快速搜索的目的。

1mysql索引与elasticsearch索引对比

mysql
如果数据量不是特别大，在千万级别，适当的管理好索引，查询效率还是可以的，但是对索引命中率有要求，就是必须要保证索引的命中率，还有就是索引的数量限制好，但是查询条件比较多、需要添加很多索引的时候mysql索引就有瓶颈了。

elasticsearch
使用了OLAP场景，海量数据实时查询，亿级以上数据量，因为底层采用的是倒排索引机制，只要你的服务器资源足够好，理论上随着数据量的增加、索引的增量，实时查询效率是线性的。

倒排索引
倒排索引应用场景：搜索引擎、实时排名，如百度搜索，搜狗搜索
索引分为正向索引和反向索引（倒排索引）
正向索引：通过Key找Value
正向索引的结构如下：

[AppleScript] 纯文本查看 复制代码

   “文档1”的ID > 单词1：出现次数，出现位置列表；单词2：出现次数，出现位置列表；…………。

[p=26, null, left]“文档2”的ID > 此文档出现的关键词列表。

倒排索引的结构如下：

[AppleScript] 纯文本查看 复制代码

 “关键词1”：“文档1”的ID，“文档2”的ID，…………。

   “关键词2”：带有此关键词的文档ID列表。

对应的倒排列表为：{(3;1;<4>)，(5;1;<4>)},其含义为在文档3和文档5出现过这个单词，单词频率都为1，单词“拉斯”在两个文档中的出现位置都是4，即文档中第四个单词是“拉斯”。
倒排索引可以统计文档ID，出现次数，出现位置。

转载自：https://mp.weixin.qq.com/s/IfjwPEP5RjkfDt-VKSE2gg