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

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

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

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

• gcd（greatest common divisor）
• minMax和blockMinMax
• uniqueValues
• numDocsWithValue

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

gcd（greatest common divisor）

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

  为什么要计算gcd：

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

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

{150、140、135}

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

xxxxxxxxxx

(v - min) / gcd

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

xxxxxxxxxx

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

  图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

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

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

uniqueValues

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

xxxxxxxxxx

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

numDocsWithValue

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

写入文档号信息

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

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

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

0 < numDocsWithValue < maxDoc

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

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

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

numDocsWithValue == 0

  如果numDocsWithValue == 0，那么将固定的信息写入到索引文件.dvm中，固定信息在索引文件.dvm中的位置如下所示：

  图8中，offset跟length被置为固定信息，在读取阶段，当读取到offset的值为-2时，就知道numDocsWithValue == 0，下面给出Lucene 8.4.0的索引文件.dvm，由于numDocsWithValue == 0，文档号的值信息不用写入到索引文件.dvd中：

  同样的查找表的信息用固定信息填充。

numDocsWithValue == maxDoc

  如果numDocsWithValue == maxDoc，说明正在执行flush的段中的每篇文档都包含当前域的信息，意味着我们也不用存储文档号的值信息，因为在读取阶段，文档号的值就是 [0, maxDoc]区间内的所有值，故同样只要将固定的信息写入到索引文件.dvm中：

  在读取阶段，当读取到offset的值为-1时，就知道numDocsWithValue == maxDoc，同样地给出Lucene 8.4.0的数据结构：

  在写入了文档号信息之后，将域值数量写入到索引文件.dvm中，域值数量在上文中的minMax中numValues获得，如下所示：

  基于篇幅，剩余的内容将在下一篇文章中展开。

点击下载附件