深入理解ES的倒排索引

数据写入过程

词项字典 term dictionary

倒排表 posting list

FOR算法

RBM算法

ArrayContainer

BitMapContainer

词项索引 term index

在Elasticsearch中，倒排索引的设计无疑是惊为天人的，下面看下倒排索引的结构。

倒排索引分为词项索引【term index】、词项字典【term dictionary】、倒排表【posting list】

先看一个原始数据录入的过程，原始数据录入的过程包含切词、规范化、去重、字典化等这么几个步骤，

I am going to bejing这句话，

切词就是将这段英文按照空格进行字段切分，这个就是所谓的分词器的功能，中文也有自己的分词器，当然还可以自定义分词器

分完词以后就是规范化，规范化的过程就是去掉一些语气词，过去分词、现在分词转换成同义词，比如将going转换成go

去重很简单，就是去掉一些重复的词项

字典化就是将这个数据保存起来，用一个id做出对应的映射

就是将一段话进行分词以后得到的结果，比如上面的话就会得到go 、bejing等基础信息，可以看到词项字典的数量是原始数据的很多倍

词项字典的数据结构是FST

在介绍FST之前，先介绍下prefix Tree，前缀树的优点是能充分的利用数据空间，比如abc，和abcd这两个词，底层可以共用abc，这样就能大大的节省数据存储占用的空间

但是前缀树有一个缺点就是比如fbcd，这个词的bcd和abcd的后四位是相同的，但是因为前缀树的特点，后四位不能充分利用

而FST是在前缀树的基础上做了改进，能够充分的利用相同的字符来存储，大大提升存储的效率。

倒排表的数据结构是一个有序的数组，数组中记录的是当前词项对应原始数据的id，比如bejing这个词项有很多原始数据对应，id有1,3,5,7

倒排表有两种常见的压缩算法

FOR算法的全称是frame of reference，这个算法的流程大致如下

原始数据比如是[1,3,6,7]这样，可能很长，在java中一个int是占用4个字节，可能通过切分词以后，倒排表的数据占用空间比原始数据还要大
这个时候，因为数组是有序的，可以将数组的每一项都减去前一项来代替当前的值，比如[1,2,3,1]
可以看到，通过这个简单的变形，倒排表的数组中的数据都减小了
然后就可以通过更小的bit来表示一个int的数，比如我可以用3个bit来表示上面的每一个数，这样的数据占用空间就会小很多，极限的情况下数组是连续的，可以使用一个bit来表示一个int数，可以减少到原来的1/32
当然实际情况下，数组不一定是连续的，这个时候可能就会使用分组了，比如3,5,7我使用4个bit来表示，6787，35465，,44656使用14bit来表示，这样想比使用32bit可以节省不少空间

从网上找到一张图，可以很好的说明这个算法