ES系列十之深入理解倒排索引

话不多说，今天开始深入理解一下es中所谓的“倒排索引”。其实在索引中包括正排索引也就是根据id去直接检索数据，其实mysql中数据底层存储的主键索引就是正排索引，这个后续会讲到的，感兴趣可以关注一下哟；还有一种索引就是我们今天要讲的倒排索引，所谓的倒排索引呢，就是倒排索引它记录的是词，和词所存在的文档id的所有列表。通过这种索引结构的存储方式，其查询速率可想而知。其数据格式为

<DocID、TF、Term position…>

在实现倒排索引时lucene将关键词，文档id，及关键词在文档中出现的位置分为了3个文件，分别是

1、词典文件：每个关键词以及指向频率文件和位置文件的指针和filed（用于表达信息位置，每个关键词都有一个或多个field）信息。

2、频率文件：关键词在每个文件中出现频率的文件。其中文档id就存在此文件中。

3、位置文件：关键词所在文章中的位置文件，也就是关键词在文档的偏移量一些信息。

具体看下下图就可以明白，一句话被拆分为多个关键词存储。这样就可以和mysql对比出为什么，es及solr这种检索工具效率会更高了。

当然聪明的小伙伴们会发现，其实这么设计还是有个弊端的，比较es中的数据全部都是落在磁盘的，那么当索引中数据过大的时候，这种存储格式在检索的时候会产生大量的io吧？

当然了，es的大佬们也是考虑到了这种情况，es是java开源组件，首先es在处理数据时，会根据索引检索出相应的数据到jvm里，以此来减少io消耗，还有个优化点就是，压缩索引。由于倒排索引文件往往占用巨大的磁盘空间，我们自然想到对数据进行压缩。同时，引进压缩算法后，使得磁盘占用减少，操作系统在query processing过程中磁盘读取效率也能提升。另外，压缩算法不仅要考虑压缩效果，还要照顾到query processing过程的解压缩效率。

总的来说，好的索引压缩算法需要最大化两个方面：

1、减少磁盘资源占用

2、加快用户查询响应速度

其中，加快响应速度比减少磁盘占用更为重要。

对于每个DocID，其保存在硬盘中的大小取决于文件集最大文档编号的大小。这样造成编号较小的DocID分配了和编号较大的DocID（上百万）一样的存储空间，浪费了资源。由于每个posting是根据DocID顺序存储，所以不需要保存DocID，只需要保存前后两个DocID的差值，这样可以大大减小DocID储存空间，这种方式称为Delta Encoding，具体可以看下图。

对于tf值，根据Zipf（齐普夫）定律，tf值较小的term占大多数，我们可以对这类tf值少分配一些空间保存。而tf大的term占少数，对这些tf分配多空间储存。基于上述排列特性，往往将docID和tf及其他数据分开放置，方便数据压缩。最终，整体的存储结构如下图所示：

为了方便分布式存储倒排索引文件，Data Block是硬盘中的基础存储单元。由于建立过程需要，每个term 的postinglist被拆分为多个部分保存在多个block中（如图不同颜色的block代表存储不同term的postinglist）。也就是说，每个block内部可能包含多个term的postinglist片段。

Data block的基本组成单元是数据块（chunk），每个chunk一般包含固定数量的posting，图中所示一个chunk包含128个posting，这些posting都属于同一个term。其中将DocID、tf和position分开排放，方便压缩。

这样以block为单元，以chunk为基础元素的索引存储的方式，一方面可以支持使用caching的方法缓存最常用term的postinglist，提高query响应速度。另一方面，所有压缩解压缩过程都以chunk为单位，都在chunk内部进行。当需要查找某一term的postinglist时，不需要对所有文件进行解压缩。对于不相关的chunk直接忽略，只需要对少部分block中的目标chunk进行处理，这样又从另一个方面大大缩短了query响应时间。这也是chunk机制设置的初衷。

目前来说有三种算法，PForDelta算法，最早由Heman在2005年提出（Heman et al ICDE 2006），在PForDelta算法基础上，Hao Yan、Shuai Ding、Torsten Suel这三位大佬发表过一篇论文提出了NewPFD算法及 OptPFD算法。具体算法就不讲解了哈，主题还是实现上面的压缩及解压缩。