倒排表(上)

本篇文章介绍如何生成倒排表,通过一个简单的例子来讲解倒排表的底层存储结构。文章中不会给出详细的源码介绍,只有一些必要的对象,感兴趣的朋友可以看我的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文件