倒排表（上）

本篇文章介绍如何生成倒排表，通过一个简单的例子来讲解倒排表的底层存储结构。文章中不会给出详细的源码介绍，只有一些必要的对象，感兴趣的朋友可以看我的GitHub，对构建倒排表的源码给出了详细的注释：https://github.com/luxugang/Lucene-7.5.0/blob/master/solr-7.5.0/lucene/core/src/java/org/apache/lucene/index/DefaultIndexingChain.java ，此类中的该方法是开始构建倒排表的入口。 另外如果某些域使用了词向量(TermVector)，它会额外的生成倒排表，虽然写入的逻辑是类似的，但最终的倒排表的数据结构还是有区别，在后面的文章中会详细介绍。

例子

图1： 上图说明：

三个关键类

构建倒排表的过程中，主要用到下面三个类：

ByteBlockPool类

此类中用一个二维数组用来存放term的倒排表数据。

IntBlockPool类

此类中同样用一个二维数组来存储索引信息，由于所有term的倒排表数据都紧凑的存放在ByteBlockPool对象的buffers[][]二维数组中，并且一个term的倒排表数据并非存储在一块连续的空间中，所以我们需要IntBlockPool对象中的一个二维数组来存储映射到ByteBlockPool对象的索引。

ParallelPostingsArray类

在这个类中我们只要关心下面几个重要的数组。该类的对象用来处理同一种域名的数据，有几种域名就有对应数量的ParallelPostingsArray对象，也就是说下面的数组对于不同文档的相同的域是共用的，这点很重要。 下面所有的数组的下标值都是termID，termID用来区分不同term的唯一标识，它是一个从0开始递增的值，每个term按照处理的先后顺序获得一个termID。

int[] termFreqs；

记录每一个term在一篇文档中的词频frequencies。

int[] lastDocIDs；

记录每一个term上次出现是在哪一个文档中。

int[] lastDocCodes；

记录每一个term上一次出现是在哪一个文档中。跟lastDocIDs[]数组不同的是，数组元素是一个组合值，相同的是当term在新的文档中出现后，才将它上一次的文档号写入到倒排表中。

例子：

图2： 

文档号5中某个term的词频为6，将文档号左移一位，5 << 1 = 10, 然后分开存储。

图3：

int[] lastPositions；

记录每一个term在当前文档中上一次出现的位置。

基于压缩存储，倒排表中的位置(position)信息是一个差值，这个值指的是在同一篇文档中，当前term的位置和上一次出现的位置的差值。
每次获得一个term的位置信息，就马上写入到倒排表中。
注意的是，实际存储到倒排表时，跟存储文档号一样是一个组合值，不过这个编码值是用来描述当前位置的term是否有payload信息。

例子

没有payload信息, 将位置的值左移1位：8 << 1, 在读取倒排表时，如果position的二进制值最低位为0，说明没有payload的信息。

图4： 

带有payload信息, 将位置的值左移1位,并与1执行或操作：(8 << 1)| 1, 在读取倒排表时，如果position的二进制值最低位为1，说明带有payload的信息。

图5：

int[] textStarts；

每一个term在ByteBlockPool对象的buffers [ ] [ ]二维数组中的起始位置。

int[] intStarts；

数组元素为每一个term在IntBlockPool对象的buffers[ ] [ ] 二维数组中的位置。

写倒排表时候，IntBlockPool对象的buffers[][] 二维数组中的数据描述了对于某一个term我们应该往ByteBlockPool对象的buffers[][] 二维数组中的哪个位置写，而intStarts[]则是描述我们如何通过termID找到在IntBlockPool对象的buffers[][] 二维数组中的数据。

在这里还需要重复的时候， 我们在当前文档第一次处理某个term时，才会将这个term上次出现的文档号跟词频写入到倒排表中， 而这个term的位置跟payload，则是马上写入。

存储空间的分配和扩容

每次处理一个term，需要考虑分配跟扩容问题。

分配

该term第一次处理，那么需要新分配一个连续的固定大小的存储空间，分配规则如下：

总是预分配两块大小都为5个字节的分片，其中第一块分片存放term的文档号、词频信息，第二块分片存放term的位置、payload、offset信息。
// 分片层级
public final static int[] NEXT_LEVEL_ARRAY = {1, 2, 3, 4, 5, 6, 7, 8, 9, 9};
// 分片大小
public final static int[] LEVEL_SIZE_ARRAY = {5, 14, 20, 30, 40, 40, 80, 80, 120, 200};

例子

图6：

扩容

在图6中，对于存储position、payload、offset信息的分片，如果前4个字节都被记录了，那么此时就会遇到哨兵值16，表示我们需要扩容了。 图7： 根据分片规则，扩容后获得的新分片大小为14，所以上图中下标值14~27的部分为新的分片。 并且旧分片中下标值10~13这四个字节作为一个索引值，在读取阶段，通过读取该索引值就可以知道下一个分片在ByteBlockPool对象的buffers [ ] [ ]二维数组中的偏移位置。

写入过程

处理文档0

处理域名“content”

例子使用的是自定义分词器PayloadAnalyzer,所以对于域名“content”来说，我们需要处理 “book”、“is”、"book"共三个term。

处理 “book”

图8：

ByteBlockPool对象的buffers数组
IntBlockPool对象的buffers数组
lastPositions[]数组
termFreq[]数组
注意点
处理“book”

图9：

ByteBlockPool对象的buffers数组
IntBlockPool对象的buffers数组
lastPositions[]数组
termFreq[]数组
处理“is”

图10：

ByteBlockPool对象的buffers数组

处理域名“author”

处理“book”

图11：

ByteBlockPool对象的buffers数组
注意点

由于是文档0中的另一个域"title"，所以即使在"content"中我们处理过"book"，在"title"域中属于一个新的term。即域之间的倒排表是独立的，尽管数据都存放在同一个ByteBlockPool对象的buffers数组中

处理文档1

处理域名“content”

处理“book”

图12：

ByteBlockPool对象的buffers数组
termFreq[]数组
注意点

文档处理结束

从图12中，文档0中"is"跟"title"域中的"book"的文档号跟词频信息还没有写入到倒排表中，那是因为还没有在新的文档中遇到"is"跟"title"中的"book"。但是这些信息都保存在ParallelPostingsArray类数组中，所以不用写入到倒排表中。

结语

本篇文章介绍了如何构建倒排表，逻辑简单易懂，尽管我们只添加了两篇文档，但是倒排表的所有逻辑都已经涉及了。

点击下载Markdown文件