IndexedDISI(一)(Lucene 8.4.0)
Lu Xugang Lv6

  IndexedDISI工具类在Lucene中用来存储Norm/DovValues对应的文档号,其实现原理借鉴了roaring bitmaps(见文章RoaringDocIdSet),本文先通过介绍在Lucene7.5.0中的实现来理解其原理,接着会介绍在Lucene8.4.0中的优化实现。

IndexedDISI写入文档号

Block

  使用IndexDISI存储的数据结构如下所示:

图1:

  图1中,每个block用来描述最多2^16个文档号信息,例如第一个block中描述的文档号集合为[0, 2^16 - 1],在处理某个文档号时,根据下面的公式来找到存储该文档号对应的block:

1
int block = docId >>> 16

  如果当前处理的文档号为 3,那么根据上面的公式 block = 3 >>> 16 = 0,那么文档号3将被存储在第一个block中,如果当前处理的文档号为 65538,根据上面的公式 block = 65538 >>> 16 = 1,那么文档号65538将被存储在第二个block中。

稠密度(density)

  在一个block中,根据block中存储的文档号数量划分为三种稠密度:

  • ALL:block中存储的文档号数量为2^16个
  • DENSE:block中存储的文档号数量范围为 [4096, 2^16 - 1],使用FixedBitSet存储文档号
  • SPARSE:block中存储的文档号数量范围为 [1, 4095],使用short类型数组存储文档号

  存储文档号使用的数据结构根据稠密度各不相同,我们只介绍介绍DENSE跟SPARSE,至于为什么不介绍稠密度ALL,我们将在系列文章索引文件的生成(十五)之dvm&&dvd中作出解释。

DENSE

  该稠密度对应的block的数据结构如下所示:

图2:

BlockId

  BlockId为block的编号,例如图1中,第一个block的编号为0,第二个block的编号为2。

图3:

  上文中我们说到,每个block中描述了216个文档号,另外通过图3可知,blockId最大值为65535,可见IndexDISI最多描述232个文档号。

  BlockId的作用

  blockId用于计算baseId,计算公式为:

1
baseId = (blockId * 65536)

  在使用了baseId后,在每个block中只要存储块内文档号就行了,意味着,在一个block中存储的文档号的取值范围为 0 ~ 65535,在读取阶段, 通过blockId跟块内文档号就可以获得原始文档号。

docIdNumber

  docIdNumber为文档数量,它描述了当前block中存储的文档号数量。

word

  word是一个long类型的值,long类型的数值占用64个bit,每一个bit用来描述一个文档号,另外上文中说到block中最多描述2^16个文档号,那么图2中word的数量就是固定的 65536/64,即1024个。

  对于blockId为0的block中的第一个word,该word描述的文档号范围为 0 ~ 63,第二个word描述的文档号范围为 64 ~ 127,看下面的例子:

图4:

  图4中,block的编号为0的第一个word中存储了3个文档号{3, 57, 60},如果没看懂,建议先阅读文章工具类之FixedBitSet

SPARSE

  该稠密度对应的block的数据结构如下所示:

图5:

  稠密度为SPARSE时,文档号直接用short类型数组存储即可,在上文中说到,块内文档号的取值范围为0 ~ 65535,那么文档号的最大值需要16bit才能表示,而short类型的值占用2个字节,故采用short类型的数组存储。

IndexedDISI读取文档号

  我们接着介绍IndexedDISI读取文档号的过程,在介绍了其读取过程后就可以明白为什么从Lucene8.0.0版本开始,对IndexedDISI的写入进行了优化。

  在Lucene最常用的应用中,我们在Collector中会对满足查询条件的文档号进行排序,排序规则通常使用DocValues来实现,而包含DocValues信息的文档的文档号就使用IndexedDISI存储,故在排序过程中,先判断这个满足查询的文档号是否包含了DocValues信息,该过程即在IndexedDISI中读取文档号,判断是否存在这个文档号。

  判断一个文档号是否在IndexedDISI中可以简单的划分为两个步骤:

  • 步骤一:找到所属block
  • 步骤二:判断block是否包含此文档号

步骤一:找到所属block

  通过下面的公式先找到文档号属于哪一个block:

1
int block = docId >>> 16

  该过程也就是计算出上文中提到的block编号blockId,通过逐个比较block中的BlockId字段找到所属block,可见找到所属block的时间复杂度为O(n),如下所示:

图6:

步骤二:判断block是否包含此文档号

  当找到所属block之后,我们继续在块内寻找,根据不同的稠密度,查找方式也各不相同。

DENSE

  这种稠密度使用了word来存储文档号,我们通过下面的公式可以计算出查询的文档号应该在第n个word中:

1
docId >>> 6

  注意的是此时docId是块内文档号,最后通过与操作就可以判断是否包含此文档号(看不懂?说明你没有看文章工具类之FixedBitSet )。

  在计算应该在第n个word的过程中,我们需要做一件事情,那就是必须知道当前查询的文档号它是IndexedDISI存储的第几个文档号(可能不包含当前查询的文档号),我们称之为 段内编号,基于上文中的存储方式,我们只能通过累加前n -1 个block中的文档数量来获得,意味着我们必须依次处理每一个block(通过累加读取block中的DocIdNumber字段的值段内编号),故时间复杂度为O(n)。

  为什么要获得当前查询的文档号在block中的段内编号

  因为如果block中有这个当前查询的文档号,那么我们还要取出DocValues的值,才能在Collector中进行排序比较,并且需要通过段内编号才能找到当前查询文档号对应的DocValues的值,这块内容的介绍将在系列文章索引文件的生成(十五)之dvm&&dvd中作出解释。

SPARSE

  这种稠密度就是简单的遍历short[ ]数组来判断,不赘述。

结语

  通过上述的介绍,可以发现两个步骤的时间复杂度均为O(n),在Lucene8.0.0之后,会通过查找表(lookup table)提高查询性能,基于篇幅将在下一篇文章中展开。

点击下载附件

 BUY ME A COFFEE
 Comments
Comment plugin failed to load
Loading comment plugin