索引文件的生成（十六）（Lucene 8.4.0）

在文章索引文件的生成（十五）之dvm&&dvd中，我们介绍了在索引（index）阶段收集文档的NumericDocValues信息的内容，随后在flush阶段，会根据收集到的信息生成索引文件.dvd&&.dvm。如果已经阅读了文章NumericDocValues，那么能快的理解本文的内容，注意的是那篇文章中，是基于Lucene 7.5.0，下文中的内容基于Lucene 8.4.0，不一致（优化）的地方会特别说明。

生成索引文件.dvd、.dvm之NumericDocValues的流程图

图1：

准备工作

图2：

根据在索引阶段收集的文档的NumericDocValuses信息（见文章索引文件的生成（十五）之dvm&&dvd），在当前流程点需要执行一些准备工作，即计算出下面的信息：

gcd（greatest common divisor）
minMax和blockMinMax
uniqueValues
numDocsWithValue

在流程点准备工作中，通过遍历每一个包含NumericDocValues信息的文档来完成上述信息的计算。

gcd（greatest common divisor）

gcd即最大公约数，获得所有NumericDocValues的域值的最大公约数，根据数学知识可知，最大公约数的最小为1。

为什么要计算gcd：

在文章NumericDocValues中已经作出了解释，本文中再详细的介绍一次，其实目的很简单：降低存储开销。

例如我们有以下的域值集合：


1
{150、140、135}

上述三个域值的最大公约数为5，即gcd的值为5，按照下面的公式我们计算出编码后的域值：


xxxxxxxxxx
1
1
(v - min) / gcd

上述公式中，v为编码前的域值，min为域值集合中的最小值，在本例子中，min的值为135，编码后的域值集合如下所示：


xxxxxxxxxx
1
1
{3, 1, 0}

可见编码后的域值集合中，最大值为3，当使用固定位数按位存储（见文章PackedInts（一））时，只需要6个bit存储即可，在读取阶段，根据min、gcd的值就可以获得编码前的域值集合。

minMax、blockMinMax

minMax跟blockMinMax在源码中都是类MinMaxTracker的对象，都是用来收集下面的信息：

min：域值集合中的最小值
max：域值集合中的最大值
numValues：域值集合中的元素数量
spaceInBits：存储域值占用的bit数量
- spaceInBits的计算方式：(bitCount(max - min)) * num，其中num指的是域值的数量，bitCount( )方法描述的是域值占用的有效bit数量，例如bitCount(3) = 2，数值3的二进制为0b00000011，有效的bit数量为2个

两个信息的区别在于，minMax收集的是域值集合中全量数据下的min、max、spaceInBits，而blockMinMax则是将域值集合分为N个block，每处理4096个域值就作为一个block，每个block单独收集min、max、spaceInBits。

为什么要计算minMax、blockMinMax

为了判断出使用单个block和多个block存储域值时，哪一种方式有更低的存储开销。

例如我们有以下域值集合，为了便于描述，计算blockMinMax时，每处理3个域值就作为一个block。

图3：

图3中，对于minMax，域值集合的全量数据下的min、max分别为1、18，并且有9个，那么spaceInBits = (bitCount(18 - 1)) * 9，数值17的二进制为0b00010001，有效的bit数量为5个，故spaceInBits的值为5*9 = 45。

图4：

图4中，对于blockMinMax，域值集合被分为3个block，每个block的spaceInBits的和值作为blockMinMax的spaceInBits，故spaceInBits = (bitCount(2 -1)) * 3 + (bitCount(18 -16)) * 3 + (bitCount(8 -5)) * 3 = 3 + 6 + 9 = 18。

源码中，如果blockMinMax和minMax的spaceInBits满足下面的条件，那么就使用多个block存储域值：


xxxxxxxxxx
1
1
(double) blockMinMax.spaceInBits / minMax.spaceInBits <= 0.9

显而易见，上述的例子将会使用多个block存储域值。当然了，当前的流程点是准备工作，仅仅判断出存储域值的方式，其具体的存储域值逻辑将在后面的流程中执行。

uniqueValues

uniqueValues是一个Set<Long>对象，用来统计域值的种类，uniqueValues将在后续的流程点是否使用域值映射存储作为判断的依据，在本文中不展开介绍，我们只需要知道收集域值种类的时机点即可，例如图3中的域值集合，在执行完流程点准备工作后，uniqueValues中的内容如下所示：


xxxxxxxxxx
1
1
{1, 2, 3, 5, 8, 16, 17, 18}

numDocsWithValue

numDocsWithValue用来描述包含当前域名的文档数量，在后面的流程中它将作为一个判断条件，用于选择使用哪种数据结构来存储包含当前域的文档号集合。

写入文档号信息

图5：

文档号信息包含两个信息：

文档号的值信息：文档号的值将被写入到索引文件dvd中
文档号的索引信息：文档号索引信息将被写入到索引文件.dvm中，在读取阶段根据文档号的索引信息来读取在索引文件.dvd中的文档号的值区间，下文中会详细说明

另外根据在流程点准备工作中计算出的numDocsWithValue，对应有三种数据结构存储文档号索引信息。

0 < numDocsWithValue < maxDoc

maxDoc的值为段中的文档数量，在下文中会介绍该值，如果numDocsWithValue的值在区间(0, maxDoc)，文档索引信息将会被存储到索引文件.dvm中的DocIdIndex字段，文档号的值信息将被存储到索引文件.dvd中的DocIdData字段：

图6：

图6中，文档号的索引信息包含offset跟length，它们描述了文档号的值信息在索引文件.dvd中的值区间，其他字段的解释见文章NumericDocValues，我们再看Lucene 8.4.0中的数据结构：

图7：

在Lucene 8.4.0版本中，DocIdIndex字段中多了jumpTableEntryCount跟denseRankPower两个信息，在读取阶段，通过这两个信息能获得查找表（lookup table）的信息，jumpTableEntryCount跟denseRankPower以及查找表的概念在系列文章IndexedDISI已经介绍，这里不赘述。