索引文件的读取(十一)(Lucene 8.4.0)

  在上一篇文章索引文件的读取(十)之tim&&tip中我们遗留了一个问题:

  为什么要根据是否达到阈值使用不同的处理方式:

  这个问题可以分解为两个小问题:

处理方式

  这两种处理方式的不同之处就在于如何根据每个term对应的文档号集合,并从这些集合中获取满足查询条件的文档号集合。

未达到阈值

  未达到阈值的情况下,会根据每个term从索引文件.doc中获取包含这个term的文档号集合,并且用一个long类型的数组docBuffer[ ]来存储文档号集合。注意的是,数组docBuffer[ ]实际上只会存储一个block(见文章索引文件之doc)中的文档号集合,当这个block中的文档号信息读取结束后,会载入下一个block的文档号信息,并写入到数组docBuffer[ ]中,这里为了便于描述,我们假设数组docBuffer[ ]中存储了所有的文档号

  接着使用一个优先级队列DisiPriorityQueue来存储每个term对应的正在被读取的文档号,该队列的排序规则为比较文档号的大小,在执行了排序后,堆顶元素的文档号是最小的,通过排序,更新term对应正在被读取的文档号,直到所有term对应的正在被读取的文档号为Integer.MAX_VALUE,最终文档号按照从小到大的顺序都被取出,我们这里通过一个例子简单介绍下该原理。

图1:

  根据图1中74行的查询条件肉眼可知,域值bcd、ga、gc、gch满足查询条件,这几个term对应的文档号集合,如下所示:

图2:

  获取过程:

图3:

  在最开始,四个docBuffer[ ]数组的第一个数组元素作为每个term正在被读取的文档号存储到优先级队列中,调整堆后如上所示,此时堆顶元素1为满足查询的文档号,它是域值"gc"对应docBuffer[ ]的第一个元素(这里由于域值"bcd"对应的文档号数量多,在源码中用cost来描述,当元素相同时,cost越小,排序位置就越靠前,故尽管它对应的docBuff[ ]的第一个元素也是1,但是堆顶元素选择了域值"gc"对应docBuffer[ ]的第一个元素),随后域值"gc"对应的正在被读取的文档号更新为dcoBuff[ ]数组的下一个数组元素,即文档号3,替换当前的堆顶元素,如下所示:

图4:

  由于栈顶元素被更新了,故需要执行调整堆的操作,调整后的堆如下所示:

图5:

  调整堆之后,堆顶元素为文档号1,由于在图3中,我们已经收集了该文档号,故不需要重复收集。接着域值"bcd"对应的正在被读取的文档号更新为dcoBuff[ ]数组的下一个数组元素,即文档号3,替换当前的堆顶元素1,如图6所示,由于栈顶元素被更新了,故需要执行调整堆的操作,如图7所示:

图6:

图7:

  调整堆以后,堆顶元素为文档号2,并且该文档号还没有被处理过,故它为满足查询的文档号。

  至此相信大家已经理解了其原理,下面直接给出下一次执行了调整堆操作以后的状态:

图8:

  图8中,堆顶元素文档号3为满足查询的文档号,接着更新、调整堆的操作,如下所示:

图9:

  按照上文描述的处理逻辑,下一步应该更新域值"gc"对应的正在被读取的文档号,由于它对应的文档号都已经取出,故在源码中通过另下一个正在被读取的文档号为Integer.MAX_VALUE,在排序之后如下所示:

图10:

  接着我们直接给出剩下的更新、堆排序后的状态:

图11:

图12:

图13:

图14:

  在图14中,直到所有term对应的正在被读取的文档号的值为Integer.MAX_VALUE,那么获取满足查询条件的文档号集合的过程就完成了。

  上文中的逻辑可以简单的用更新堆顶元素、调整堆两个步骤来归纳,源码中的核心实现位于DisjunctionDISIApproximation类中的nextDoc()方法,如下所示:

图15:

达到阈值

  达到阈值的情况下,在文章索引文件的读取(十)之tim&&tip中我们说到,所有term对应的文档号总是优先使用数组存储(数组中可能会有重复的文档号),当达到某个阈值后,会使用FixedBitSet存储,如果最终使用数组存储,那么在收集结束后对数组进行排序、去重操作后就能获取满足查询条件的文档号集合即可,我们详细的介绍下使用FixedBitSet存储时,如何收集以及读取文档号。

  为了便于描述我们还是以图1的例子为例,每个term对应的文档号集合如下所示:

图16:

构造FixedBitSet对象

  我们首先了解下FixedBitSet是如何存储文档号的,这块内容在文章工具类之FixedBitSet已经介绍过了,我们这里再简单的说明下:该对象中包含一个long类型的数组bits[ ],其中每一个数组元素,即一个long类型的值,使用该值的每个bit用来代表一篇文档号,那么一个long类型的值可以用来描述64篇文档号,故bits[ ]数组的第一个数组元素描述的是文档号0~63,第二个数组元素描述的是文档号64~127,以此类推。

  例如我们有以下的文档号,用bits[ ]数组存储后如下所示:

图17:

  图17中,bit为1描述了存储了对应的文档号,文档号跟bit的映射关系通过下面的公式来描述:

  由上述的操作可以知道,bits[ ]数组的大小取决于文档号集合中最大的文档号。所以由于不知道满足查询的最大文档号是多少,构造FixedBitSet对象时候只能根据段中的文档总数来确定bits[ ]数组的大小。

FixedBitSet存储文档号

  存储文档号的总流程可以用一句话概括:依次处理每一个term,将每一个term对应的文档号写入到FixedBitSet中,对于图16的例子,term的处理顺序为:"bcd" ---> "ga" ---> "gc" ---> "gch"。

图18:

  bits[ ]数组的最大长度为 ((maxDoc - 1) >> 6) + 1。

FixedBitSet读取文档号

  获取某个文档号的值,需要上一个文档号的值target才能获取,target的初始值为0,由于代码比较简单,我们直接给出:

  从上述代码可以看出,获取一个文档号的性能取决于相邻的文档号的数值大小,相邻的文档号差值越大,查找速度越慢。

  为什么未达到阈值使用BooleanQuery的方式做文档号的收集

  为什么达到阈值后不使用BooleanQuery的方式做文档号的收集

  在执行TermRangeQuery时,获取满足查询的文档号的时机点是不同的,取决于满足查询的term数量是否达到阈值,时机点如下图所示,该流程图的介绍见系列文章查询原理(一)

图19:

结语

  

点击下载附件