Lucene 源码系列——倒排表
原文：https://www.amazingkoala.com.cn/Lucene/Index/2019/0222/36.html
本篇文章介绍如何生成倒排表，通过一个简单的例子来讲解倒排表的底层存储结构。文章中不会给出详细的源码介绍，只有一些必要的对象，感兴趣的朋友可以看我的 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)，它会额外的生成倒排表，虽然写入的逻辑是类似的，但最终的倒排表的数据结构还是有区别，在后面的文章中会详细介绍。
public void invert(IndexableField field, boolean first) throws IOException {...}
例子
图 1：
上图说明：
- 代码第 42 行表示倒排表中会存放 文档号、词频、位置、偏移信息
type.setIndexOptions(IndexOptions.DOCS_AND_FREQS_AND_POSITIONS_AND_OFFSETS);
- 代码第 46 行表示我们为域名为"content"的域值分词后"book"添加一个值为"hi"的 payload 值，而域名为"title"的中的"book"以及其他 term 都没有 payload 信息，
- 通过自定义分词器来实现 payload，当前例子中的分词器代码可以看 PayloadAnalyzer
我们也可以为不同的term提供不同的payload。
三个关键类
构建倒排表的过程中，主要用到下面三个类：
ByteBlockPool 类
此类中用一个二维数组用来存放 term 的倒排表数据。
public byte[][] buffers;
IntBlockPool 类
此类中同样用一个二维数组来存储索引信息，由于所有 term 的倒排表数据都紧凑的存放在 ByteBlockPool 对象的 buffers[][]二维数组中，并且一个 term 的倒排表数据并非存储在一块连续的空间中，所以我们需要 IntBlockPool 对象中的一个二维数组来存储映射到 ByteBlockPool 对象的索引。
public byte[][] buffers;
ParallelPostingsArray 类
在这个类中我们只要关心下面几个重要的数组。该类的对象用来处理同一种域名的数据，有几种域名就有对应数量的 ParallelPostingsArray 对象，也就是说下面的数组对于不同文档的相同的域是共用的，这点很重要。
下面所有的数组的下标值都是 termID，termID 用来区分不同 term 的唯一标识，它是一个从 0 开始递增的值，每个 term 按照处理的先后顺序获得一个 termID。
int[] termFreqs；
记录每一个 term 在一篇文档中的词频 frequencies。
int[] lastDocIDs；
记录每一个 term 上次出现是在哪一个文档中。
对于同一个term来说，在某一篇文档中，只有所有该term都被处理结束才会写到倒排表中去，否则的话，term在当前文档中的词频frequencies无法正确统计。所以每次处理同一个term时，根据它目前所属的文档跟它上一次所属的文档来判断当前的操作是统计词频还是将它写入到倒排表。
另外包含某个term的所有文档号是用差值存储，该数组用来计算差值。
int[] lastDocCodes；
记录每一个 term 上一次出现是在哪一个文档中。跟 lastDocIDs[]数组不同的是，数组元素是一个组合值，相同的是当 term 在新的文档中出现后，才将它上一次的文档号写入到倒排表中。
基于压缩存储，如果一个term在一篇文档中的词频只有1，那么文档号跟词频的信息组合存储，否则文档号跟词频分开存储。
例子：
文档号5中某个term的词频为1，那么组合存储，将文档号左移一位，然后跟1执行或操作
(5 << 1) | 1 == 11。
图 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，所以上图中下标值 1427 的部分为新的分片。13 这四个字节作为一个索引值，在读取阶段，通过读取该索引值就可以知道下一个分片在 ByteBlockPool 对象的 buffers [ ] [ ]二维数组中的偏移位置。
并且旧分片中下标值 10
写入过程
处理文档 0
处理域名“content”
例子中使用的是自定义分词器 PayloadAnalyzer,所以对于域名“content”来说，我们需要处理 “book”、“is”、"book"共三个 term。
处理 “book”
图 8：
ByteBlockPool 对象的 buffers 数组
- 下标值 0~4：文档 0 中第一个"book"的长度以及对应的 ASCII
- 下标值 10：第一个"book"在文档 0 中的位置，即 0，由于有 payload 信息，组合存储后，位置值为（0 << 1 | 1）,即 1
- 下标值 11~14：索引值
- 下标值 15~17：payload 的长度以及对应的 ASCII
- 下标值 18~19：文档 0 中第一个"book"在文档 0 中的偏移位置以及 term 的长度
IntBlockPool 对象的 buffers 数组
- 下标值 0：包含"book"的文档号、词频信息在 ByteBlockPool 对象的 buffers 数组写入的起始位置
- 下标值 1：下一次遇到"book"时，它的 position、payload、offset 信息在 ByteBlockPool 对象的 buffers 数组写入的起始位置
lastPositions[]数组
- lastPositions[]数组下标值为"book"的 termId(0)的数组元素更新为 0。
termFreq[]数组
- termFreq[]数组下标值为"book"的 termId(0)的数组元素更新为 2。
注意点
- 由于文档 0 中的所有 term 没有都处理结束，所以我们还不知道"book"在文档 0 中的词频，所以上图中并没有记录 文档号、词频信息（组合存储）。
处理“book”
图 9：
ByteBlockPool 对象的 buffers 数组
- 下标值 20：第二个"book"在文档 0 中的位置，根据图 8 中，上一个"book"的位置是 0，所以差值存储就是 (1 - 0) = 1，带有 payload，位置信息即为 (1 << 1 | 1)，即 3，并且 lastPositions[]数组下标值为当前 term 的 termId(0)的数组元素更新为 1。
- 下标值 21~23：payload 的长度以及对应的 ASCII
- 下标值 24~25：第二个"book"在文档 0 中的偏移位置以及 term 的长度
IntBlockPool 对象的 buffers 数组
- 下标值值 1：下一次遇到"book"时，它的 position、payload、offset 信息在 ByteBlockPool 对象的 buffers 数组写入的起始位置**(下文不赘述这个数组的更新)**
lastPositions[]数组
- lastPositions[]数组下标值为"book"的 termId(0)的数组元素更新为 1 (下文不赘述这个数组的更新)
termFreq[]数组
- termFreq[]数组下标值为"book"的 termId(0)的数组元素更新为 2 (下文不赘述这个数组的更新)
处理“is”
图 10：
ByteBlockPool 对象的 buffers 数组
- 下标值 29~31：文档 0 中的"is"的长度以及对应的 ASCII
- 下标值 37："is"在文档中的位置，即 2，由于没有 payload，位置信息即为 (2 << 1 | 0)，即 4
- 下标值 38~39："is"在文档 0 中的偏移位置以及 term 的长度
处理域名“author”
处理“book”
图 11：
ByteBlockPool 对象的 buffers 数组
- 下标值 42~46：文档 0 中的域名"title 的"book"的长度以及对应的 ASCII
- 下标值 52："book"在文档中的位置，即 0，由于没有 payload，位置信息即为 (0 << 1 | 0)，即 4
- 下标值 53~54：域名"title 的"book"在文档 0 中的偏移位置以及 term 的长度
注意点
由于是文档 0 中的另一个域"title"，所以即使在"content"中我们处理过"book"，在"title"域中属于一个新的 term。即域之间的倒排表是独立的，尽管数据都存放在同一个 ByteBlockPool 对象的 buffers 数组中
处理文档 1
处理域名“content”
处理“book”
图 12：
ByteBlockPool 对象的 buffers 数组
- 下标值 5~6：由于文档 0 已经处理结束，所以"book"在文档 0 中的词频也确定了，故可以将"book"在文档 0 中的文档号跟词频 freq 写入到倒排表中，由于词频值为 2，故不需要组合存储，用两个字节分别存储文档号跟词频。
- 下标值 25
28：从图 11 中我们可以看出只剩下下标值 26、27 两个字节，无法存储"tem"在当前文档 1 中的 position、payload、offset 的信息，故需要扩容，获得的新的分片的范围为下标值 5776 的区间，故下标值 25~28 的 4 个字节成为一个索引(index)，并且索引值为 57。由于在图 11 中下标值 25 记录了一个 length 的值，所以需要把这个值放到新的分片中，即下标值 57 的位置。 - 下标值 58："book"在文档 1 中的位置，即 0，由于有 payload 信息，组合存储后，位置值为（0 << 1 | 1）,即 1
- 下标值 59~61：payload 的长度以及对应的 ASCII
- 下标值 62~63："book"在文档 1 中的偏移位置以及 term 的长度
termFreq[]数组
- termFreq[]数组下标值为"book"的 termId(0)的数组元素由图 11 中的 2 更新为 1，因为这里开始存储"book"在文档 1 中的词频值了。
注意点
- 从图 12 中，文档 0 中"is"跟"title"域中的"book"的文档号跟词频信息还没有写入到倒排表中，那是因为还没有在新的文档中遇到"is"跟"title"中的"book"。
文档处理结束
从图 12 中，文档 0 中"is"跟"title"域中的"book"的文档号跟词频信息还没有写入到倒排表中，那是因为还没有在新的文档中遇到"is"跟"title"中的"book"。但是这些信息都保存在 ParallelPostingsArray 类数组中，所以不用写入到倒排表中。
结语
本篇文章介绍了如何构建倒排表，逻辑简单易懂，尽管我们只添加了两篇文档，但是倒排表的所有逻辑都已经涉及了。
