ES倒排索引
倒排索引存储结构
倒排索引的存储结构
posting List倒排索引
索引文件中分别存储了不同的数据
其中倒排表包含某个词项的所有id的数据存储在了.doc中
词项字典term Dictonary
词项字典包含了index field的所有经过normalization token filters处理之后的词项数据，最终存储在.tim文件中
所谓nomalization其实是一个如去重，时态统一，大小写统一，近义词处理等操作，词项索引就是为了加速词项字典检索的一种数据结构，落地文件为tip，.tip文件和.tim文件结构数据如下
词项索引（Term Index）
lucene中通过FST Index信息来读取当前域在索引文件.tim的具体信息，同一个索引所有的FSTIndex都被连续的写入在同一个.tip文件中，所以就需要indexStartFP来索引FSTIndex
FSTIndex底层是一个字节数组，存储了每个Block在.tim中的起始位置，block f和block g对应的Block分别被保存在了.tim文件的Block 0 和Block 1的位置
每个Block内部又保存了Block Header、Suffix和Stats信息以及Metadatas信息，其中Block Header中存储了当前Block中的Pending Block和Pending Term的总计数，也就是EntryCount，Sufix则是保存了当前Block后缀的个数以及分别是什么，如block b的SufixLength=2，为f、g。Stats则保存了当前Term的词频和文档频率，参见：org.apache.lucene.index.TermsEnum.TermStats。
其中docFreq为包含当前Term的doc数量，totalTermFreq为当前term在所有文档中的当前字段中出现的总次数，但实际保存的是和docFreq的差值，这也是遵循通用最小化算法的法则表现。需要注意的是，两者均是指在同一个域内的计数。Metadatas这里不着重介绍。
关于倒排表的文件结构，我们进需知道内部存储包含Term的id数组，词频，postion，payload，offset等信息，需要重点注意的是ES内部采用的压缩算法
压缩算法
既然全文检索经常备用在大数据检索领域，搜索引擎级别的数据量通常在亿级，百亿级以上，那么也就是说我们对其建立倒排索引，每个字段被拆分成了若干Term，结果就有可能倒排索引的数据量甚至超过了source data，即便我们对倒排索引的检索不必要全表扫描，但是太多的数据不管是存储成本还是查询性能都不是我们想要的，解决办法就是采用高效的压缩算法和快速的编码解码算法
FOR（Frame Of Reference）
以第一节中的场景为例，假设我们的商品有10亿个，某个Term如“小米”，包含当前词项的docs假如有100万条，每个docid为int类型，占用4个Bytes，也就是32个bit，换算成MB，就是400万字节总占用大小为3200万个bit≈3.8MB。粗略的看，也许你并不觉得3.8MB有多大，但是需要注意的是，倒排索引的数量级很有可能也是亿级甚至更多，这样算来，数据的压缩就是我们不得不考虑的事情。
我们还是以小米这个Term为例，加入其对应的倒排表中的id为[1,2,3...100W]，我这里有字幕W代表万。通常一个数值列席占用的bit数取决于其值的大小，这是数值存储的计算方式决定的，一个bit能存储的数子个数是2^1，能存储的最大值就是2^1-1，就是[21-1]也就是[0,1]，同理2个bit的取值范围就是[0,22)或[0,22-1]，其计算公式为n个bit能存储值的区间为[0,2n)比如int使用32个bit存储，最大值就是2^31-1。这里之所以是31次方是因为int是有符号整数，其中一个bit用来存储符号位了，但是docid只有正整形，因此在倒排索引的场景里不必考虑负数的情况。
那么当前数组中最大值只有100w，我们既可以用更少的bit来存储，而不是32个bit，那么具体用多少个呢，原则上是2n只要大于100w，n取最小值既可以了，此时n=20。但次数数组中每个数值都需要使用20个bit来存储，这显然是极大的浪费，因为数组前段的数值都非常小，仅用很少的bit就可以了，这是我们就考虑是否可以用差值存储dealta list，即不存储原本的数值，而是存储每个数值之前的一个数字，这时原本的数字组就变成了[1,1,1,1,]数组中包含100w个1，如果存储数子1那么用1个bit就够了，也就是我们存储一百万个数字，只需要用100万个bit，虽然看上去还是很多，但是原本存储这些数据需要使用3200W个bit，现在数据压缩了32倍，这也是采用差值存储的理论最该的压缩倍率。
此时或许你已经有了疑惑，实际场景中不可能有这么巧合的情况。没错，那我们以图3-1中的数组[73，300，302，332，343，372]为例，此数组占用的空间大小为4Bytes*6=24Bytes,计算差值列表，结果为[73,227,2,30,11,29]取差值的目的就是压缩整个数组的取值范围，经过计算，差值最大为227，使用8个bit位来存储。但是细心思考可以发现，除了227意外，其他数字都很小，如果都是用8个bit来存储显然浪费了不少存储空间。于是我们尝试将数组进行拆分，将原本拆分成[73,227]和[2,30,11,29]这俩个数组，这样做的好处就是第二个数组的数值区间进一步减小了。最大值有227变为了30，这时只需要5个bit就可以存储任意一个数字。而第一个数组还是用8个bit存储每一位数字。
然而问题又来了，为什么我们不对每一个数字单独使用其最合适的bit数来存储，这样岂不是更节省空间么？这就要再次提到关于数据存储的法则“快速的编码和解码”，我们不仅需要把数据尽可能的压缩使其占用更小的空间，还需要对齐进行解码，因为我们最终需要的还是source data
我们对detais list进行拆封的目的是对每个数组使用不同的bit进行合理的空间分配，在这个过程中我们需要对每个数组元素使用bit数进行记录，比如[73，227]这个数组每个数字使用8个bit来存储，这个数字“8”是需要一段空间来记录的，笔者暂且把这块记录空间叫Record Space，这块空间的大小是1个Byte，如果我们把每个数字单独拆分出来，那么就是要对每个数字单独开辟这一个byte的空间，得不偿失，所以在计算数组的拆封长度的时候，就要权衡得失，尽量把数组保留的足够长，数组越长，Record Space 所占用的空间越可以忽略不计，但同时数组越扁平越好，取值空间越小越好。比如这个数组：[22, 43, 21, 34, 55, 64, 4322, 345]，就可以吧4322和345拆分出来，因为4322加大了每个数字的bit占用，造成了空间浪费。
最后我们来计算一下经过压缩后的磁盘占用。数组经过拆分，分为了两个数组，第一个数组每个数字占用1个Byte，共两个数字，总占用为2Bytes，记录数组单位大小的Record Space大小为1Byte，第二个数组每个数字占用5个bit，一共四个数字，共计20bit，但是计算空间的最小单位是Byte，所以实际占用的大小为3Bytes，第二个数组的Record Space大小也是1Byte，因此压缩后的数据总大小为1B+2x1B+3B+1B=7Bytes，相比压缩之前，大小不到原先的三分之一。
RBM(RoaringBitmap)
如果你足够细心，你也许会发现其实上述例子中的数组仍然具有一定的特殊性。没错，他是一个稠密数组，可以理解为是一个取值区间波动不大的数组。如果倒排表中出现这样的情况：[1000W, 2001W, 3003W, 5248W, 9548W, 10212W, … , 21Y]，情况将会特别糟糕，因为我们如果还按照FOR的压缩算法对这个数组进行压缩，我们对其计算dealta list，可以发现其每个项与前一个数字的差值仍然是一个很大的数值，也就意味着dealta list的每个元素仍然是需要很多bit来存储的。于是Lucene对于这种稀疏数组采用了另一种压缩算法：RBM（Roaring Bitmaps）
我们以图3-2中的数组 [1000，62101，131385，132052，191173，196658] 为例，这是一个典型的稀疏型数组。在进行数据压缩的时候，其实不管何种方法，我们的最终目的都是把原来的数字转换成足够小的数字以便于我们存储，同时又必须保证压缩后的数据是可以快速解码的。
减法不好用，这次我们尝试使用除法，由于无符号int类型的最大值不超过232，因此RBM的策略就是把一个int型拆封成俩个shhort类型的乘积，具体的做法是把数组中的每个元素对216取模，因为被除数是232除数是216，因此商和余数均小于216，其实这种想法是国内开发者强行转化的逻辑吗。
RBM算法本身的设计思路是将原数字的32个bot分为了高16为和低16位。以原数组中196658这个id为例，将其转化为二进制结果为 110000000000110010，我们看到其实结果是不足32bits的，但因为每个int型都是有32个bit组成的，不足32bit会在其前面补0，实际其占用的空间大小仍然为32bits，如果这一点不理解，打个比方，公交车有32个座位，无论是否坐满，都是使用了32个座位。最终196658转换成二进制就是0000 0000 0000 0011 0000 0000 0011 0010，前16位就是高16位，转换成十进制就是3，后16位也就是低16位，转换成十进制就是50，3和50分别正好是196658除以63326（216）的得数和余数，换句话说，int类型的高16位和低16位分别就是其本身对216的商和模。
对数组中每个数字进行相同的操作，会得到以下结果：（0,1000）（0,62101）（2,313）（2,980）（2,60101）（3,50），其含义就是每个数字都由一个很大的数字变为了两个很小的数字，并且这个数字都不超过65536，更重要的是，当前结果是非常适合压缩的，因为不难看出，出现了很多重复数字，比如钱俩个数字的得数都是0，以及第2,3,4个数字的树都是2,。RBM使用了非常适合存储当前结果的数据。这种数据结构是一种类似于哈希的数据机构，不过key值是一个short有序不重复数组，用于保存每个商值，value是一个容器，保存了当前key值对应的所有模，这些模式不重复的，因为同一个商的余数是不会重复的。这里的容器官方称之为Container，如图
RBM中包含三种Container，分别是ArrayContainer、BitmapContainer和RunContainer，下面我将对这三种Container展开来逐一讲解。
首先是ArrayContainer，顾名思义，Container中实际就是一个short类型的数组，其空间占用的曲线如图3-4中的红色线段，注意这里是线段，因为docs的数量最大不会超过65536，其函数为 y（空间占用）=x（docs 长度） x 2Bytes，当长度达到65536极限值的时候，其占用的大小就是16bit * 65536 / 8 /1024 = 128KB，乘以65536是总bit数，除以8是换算成Byte，除以1024是换算成KB。
第二种是BitmapContainer，理解BitmapContainer之前首先要了解什么是bitmap。以往最常见的数据存储方式都是二进制进位存储，比如我们使用8个bit存储数字，如果存十进制0，那二进制就是 0 0 0 0 0 0 0 0，如果存十进制1，那就是 0 0 0 0 0 0 0 1，如果存十进制2，那就是 0 0 0 0 0 0 1 1，用到了第二个bit。这种做法在当前场景下存储效率显然不高，如果我们现在不用bit来存储数据，而是用来作为“标记”，即标记当前bit位置商是否存储了数字，出的数字值就是bit的下标，如下图3-5所示，就表示存储了2、3、5、7四个数字，第一行数字的bit仅代表当前index位置上是否存储了数字，如果存储了就记作1，否则记为0，存储的数字值就是其index，并且存储这四个数字只使用了一个字节。
不过这种存储方式的问题就是，存储的数字不能包含重复数字，并且Bitmap的大小是固定的，不管是否存储了数值，不管存储了几个值，占用的空间都是恒定的，只和bit的长度有关系。但是我们刚才已经说过，同一个Container中的数字是不会重复的，因此这种数据类型正好适合用这种数据结构作为载体，而因为我们Container的最大容量是65536，因此Bitmap的长度固定为65536，也就是65536个bit，换算成千字节就是8KB，如图3-4中的蓝色线段所示，即Lucene的RBM中BitmapContainer固定占用8KB大小的空间，通过对比可以发现，当doc的数量小于4096的时候，使用ArrayContainer更加节省空间，当doc数量大于4096的时候，使用BitmapContainer更加节省空间。
第三种Container叫RunContainer，这种类型是Lucene 5之后新增的类型，主要应用在连续数字的存储商，比如倒排表中存储的数组为 [1,2,3…100W] 这样的连续数组，如果使用RunContainer，只需存储开头和结尾两个数字：1和100W，即占用8个字节。这种存储方式的优缺点都很明显，它严重收到数字连续性的影响，连续的数字越多，它存储的效率就越高。
Trie（Prefix Tree）原理
一直以来，数据结构的“小”而“快”是每个追求更好性能的developer孜孜不倦追求的目标，所谓“快”即检索速度快，“小”即通用最小化算法。上一节我们介绍了倒排表的数据压缩原理和过程，自本节开始，我们分几部分详细介绍一下Lucene中对倒排索引Term DIctionary以及Term Index的数据压缩和优化算法。
我们按照每个Term一步来演示Trie是如何存储Term Dictionary的。图中我们以圆形标识节点，箭头代表节点的出度，出度存储了当前节点对应的字符。当输入词项“msb”的时候，如果图中第一步所示，图中以加粗的圆圈标识当前节点是一个终止节点。当输入第二个词项“msbtech”的时候，复用了“msb”，当输入“msn”的时候，节点2添加了第二个出度，至此我们已经实现了对重复关键字的复用。但是问题也就随之而来了，当最后一个Term输入的时候，节点0产生了第二个出度。
FST的构建原理
细心的你应该已经发现了，在使用字典树存储Term Dictionary的案例中，字符“tech”也属于重复部分，但是未被合理复用，导致了空间浪费。为了解决这个问题，Lucene采用了另一种数据结构：FST（Finite State Transducer），即“有限状态转换机”。FST是本章内容难点，也是倒排索引的核心数据结构。
通常我们在计算机语言中表示一件事物，没问呢会通过某种数学模型来描述。加入我们要描述一件事：张三一天的所有活动。这里我们采用了一种叫做FSM（Finite State Machine）的抽象模型，这种模型使用模型使用原型的节点表示某个状态，状态之间可以互相转换，但是转换过程是无相的。比如睡觉醒了可以去工作，工作累了可以去玩手机；或者工作中想去上厕所等等。在这个模型中，表示状态的节点是有多个的，但状态的转换是无限多的，同一时刻只能处于某一个状态，并且状态的转换是无需切循环的
显然这种模型并不适用于描述Term Dictionary这样的数据结构，但是我们之所以提他，是为了方便读者理解这种具化事务抽象化描述的方式。虽然FSM并不适合，但是在他的基础上演化出了FSA（Finite State Acceptor）,我们仍然以图 4-2 中的Term Dictionary数据为例，演示一下FSA是如何在Trie的基础上进行优化的。
相较于FSM，FSA增加了Entry和Final的概念，也就是由状态转换的不确定性变为了确定，由闭环变为了单向有序，这一点和Trie是类似的，但是不同的是，FSA的Final节点是唯一的，也是因为这个原因，FSA在录入和Trie相同的Term Dictionary数据的时候，从第三步开始才表现出了区别，即尾部复用。如果在第三步的时候还不太明显，那第四步中就可以清楚的看到FSA在后缀的处理上更加高效。
至此，FSA已经满足了对Term Dictionary数据高效存储的基本要求，但是仍然不满足的一个问题就是，FSA无法存储key-value的数据类型，所以FST在此基础上为每一个出度添加了一个output属性，用来表示每个term的value值。下面以Term Dictionary：（msb/10、msbtech/5、msn/2、wltech/8、wth/16）为例，演示一下FST的构建原理，斜线后面的数字代表每个term的输出值。
通用最小化算法的应用面非常广泛，这里其实也是遵循了这样的规则。可复用的不仅仅Term的字符，输出值之所以被存储了最靠前的位置上，目的也是为了让更多的Term复用，如果输出值产生了冲突，再去处理冲突问题，最终生成最小化FST。
如上图5-3所示，当第一个term:msb被写入FST中，其输出值被保存在了其第一个节点的出度上，在数据从FST中读取的时候， 计算其每个节点对应的出度的输出值以及终止节点的final output值的累加和，从而得出输出值，此时msb的输出值就是10+0+0+0=10，但是这里我用0来标识没有输出值，但实际情况没有输出值就是空而不是0，这里写0只是为了方便你去理解，这一点是需要注意的。
当第二个term:msbteach被写入的时候，其输出值5与msb的输出值10发生了冲突，这时，通用最小化算法法则再次发挥了功效。数字虽然不能像字符那样以前缀作为复用手段，但是数字是可以累加的，10可以拆成两个数字5，这样10和5就产生了公共部分，即5，所以这个时候m的输出值就需要改成5，那另一个5就需要找一个合适的位置，然而把它存放在任何一个节点的出度上似乎都会影响msbtech的计算结果，为了避免这个问题，可以把这个多出来的属于msb的输出值存入msb的final节点的final output中，节点的final output只会在当前出度是输入值的最后一个字符并且出度的target指向的是final节点的时候，才会参与计算。因此此时的msb和msbtech就各自把输出值存入了合适的位置，互不影响而且做到了“通用最小化”原则。
输入第三个term:msn，节点2产生了第二个出度：n，2 < 5，根据"通用最小化"法则，2和5有公共部分：2，5倍拆分成了2和3，此时公共前缀为“ms”，前面以“ms”为前缀的所有term都讲重新计算出度output，此时3需要满足：不能存放在公共前缀“ms”上，并且也不能在第二条出度“n”上，因此只能存放在出度b上，因为b在当前节点2第一条出度的链路上是最靠前的位置。这里FST和Trie最大的区别就是FST不仅使用了公共前缀，而且还计算了公共后缀，“msn”的最终节点会指向节点7，和节点6的出度h共享终止节点。
其实到这里还不能很好的提现“公共后缀”，但是输入wltech的时候，此时就产生了公共后缀“tech”，节点2的出度b和节点8的出度t共同指向了节点3。
输入最后一个term:wth，公共前缀为w，公共后缀为h，最终生成的FST如上图所示。
FST的压缩效率非常高，相比HashMap，FST的性能相差并不多，但是可以大大节省空间。搜索引擎级别的词项动辄几亿甚至几十亿的数量级，如果使用FST对其进行存储，其高效的数据存储使得数据被压缩的很小，使其完全缓存在内存内成为可能。FST在Luncene中应用非常广泛，比如同义词处理，模糊查询Suggest等都有应用。