用了Elasticsearch后，查询起飞了( 二 ) 最近接触的几个项目都使用到

文章图片
相关的名词都是ES官方文档给的描述，后面参考材料中都可以找到出处。
②索引内部结构
上面所描述的倒排索引，仅仅是一个很粗糙的模型。真的要在实际生产中使用，当然还差的很远。
在实际生产场景中，比如ES最常用的日志分析，日志内容进行分词之后，可以得到多少的term?
那么如何快速的在海量term中查询到对应的term呢?遍历一遍显然是不现实的。
termdictionary：于是乎就有了termdictionary ， ES为了能快速查找到term ，将所有的term排了一个序，二分法查找。
是不是感觉有点眼熟，这不就是MySQL的索引方式的，直接用B+树建立索引词典指向被索引的数据。
termindex：但是问题又来了，你觉得TermDictionary应该放在哪里?肯定是放在内存里面吧?磁盘io那么慢。就像MySQL索引就是存在内存里面了。
但是如果把整个termdictionary放在内存里面会有什么后果呢?内存爆了...
别忘了， ES默认可是会对全部text字段进行索引，必然会消耗巨大的内存，为此ES针对索引进行了深度的优化。
在保证执行效率的同时，尽量缩减内存空间的占用。于是乎就有了termindex 。
Termindex：从数据结构上分类算是一个“Trie树” ，也就是我们常说的字典树。
这是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。
这棵树不会包含所有的term ，它包含的是term的一些前缀(这也是字典树的使用场景，公共前缀) 。
通过termindex可以快速地定位到termdictionary的某个offset ，然后从这个位置再往后顺序查找。就想右边这个图所表示的。
怎么样，像不像我们查英文字典，我们定位S开头的第一个单词，或者定位到Sh开头的第一个单词，然后再往后顺序查询?
lucene在这里还做了两点优化，一是termdictionary在磁盘上面是分block保存的，一个block内部利用公共前缀压缩，比如都是Ab开头的单词就可以把Ab省去。
二是termindex在内存中是以FST(finitestatetransducers)的数据结构保存的。
FST有两个优点：
空间占用小：通过对词典中单词前缀和后缀的重复利用，压缩了存储空间。查询速度快：O(len(str))的查询时间复杂度。FST的理论比较复杂，本文不细讲，延伸阅读：
https://www.shenyanchao.cn/blog/2018/12/04/lucene-fst/OK ，现在我们能得到lucene倒排索引大致是个什么样子的了。

文章图片
关于postingslist的一些巧技
在实际使用中， postingslist还需要解决几个痛点：
postingslist如果不进行压缩，会非常占用磁盘空间。联合查询下，如何快速求交并集(intersectionsandunions) 。对于如何压缩，可能会有人觉得没有必要， ”postinglist不是已经只存储文档id了吗?还需要压缩?” ，但是如果在postinglist有百万个docid的情况，压缩就显得很有必要了。
比如按照朝代查询古诗，至于为啥需要求交并集， ES是专门用来搜索的，肯定会有很多联合查询的需求吧(AND、OR) 。按照上面的思路，我们先将如何压缩。
①压缩
FrameofReference：在lucene中，要求postingslists都要是有序的整形数组。
这样就带来了一个很好的好处，可以通过增量编码(delta-encode)这种方式进行压缩。
比如现在有id列表[73,300,302,332,343,372] ，转化成每一个id相对于前一个id的增量值(第一个id的前一个id默认是0 ，增量就是它自己)列表是[73,227,2,30,11,29] 。
在这个新的列表里面，所有的id都是小于255的，所以每个id只需要一个字节存储。