Lucene 源码系列——索引文件的生成(五)之 tim&&tip

在前面的四篇文章中,我们介绍了生成索引文件.tim、.tip.doc.pos、.pay 中.doc、.pos、.pay 这三个索引文件的内容,接着我们继续图 1 中剩余的内容,即流程点 生成索引文件.tim、.tip

生成索引文件。tim、.tip、.doc、.pos、.pay 的流程图

图 1:

1.png

  对于图 1 的流程图的介绍,可以看文章索引文件的生成(一)之 doc&&pay&&pos,我们同样以流程图的方法来介绍生成索引文件。tim、.tip 的逻辑。

生成索引文件。tim、.tip 的流程图

图 2:

2.png

  图 2 的流程描述的是一个域生成索引文件。tim、.tip 的流程图。

准备数据

图 3:

3.png

  将包含当前 term 的文档号 docId,以及在这些文档内的出现频率 frequency,位置信息 position、payload 信息、偏移信息 offset 写入到索引文件.doc、.pay、.pos 之后,会生成 IntBlockTermState 对象,该对象包含了以下的信息作为处理索引文件。tim、.tip 的准备数据:

  • singletonDocID:该值如果不为-1,说明只有一篇文档包含当前 term,那么 singletonDocID 的值为对应的文档号,singletonDocID 的存在会影响索引文件的数据结构,在 生成InnerNode 流程点会介绍该值的影响
  • lastPosBlockOffset:如果该值为-1,说明 term 在所有文档中的词频没有达到 128,即没有生成一个 block(见文章索引文件的生成(二)),如果至少存在一个 block,那么该值描述的是 VIntBlocks 在索引文件.pos 中的起始位置,见图 4
  • docStartFP:当前 term 的文档号 docId、词频信息 frequency 在索引文件.doc 的起始位置
  • posStartFP:当前 term 的位置信息 position 在索引文件。pos 的起始位置
  • payStartFP:当前 term 的偏移位置 offset,payload 在索引文件。pay 的起始位置
  • skipOffset:当前 term 的跳表信息在索引文件.doc 的起始位置

  上述值在索引文件中的位置如下所示:

图 4:

4.png

  索引文件。tim 又称为 Term Dictionary,所以在读取阶段,我们是先通过读取索引文件。tim 来得到在索引文件.doc、.pos、pay 的信息。

  • docFreq:包含当前 term 的文档数量
  • totalTermFreq:当前 term 在所有文档中出现的词频和值

  上述的两个信息是在生成索引文件.doc、.pay、.pos 的过程中记录的,其记录的时机点如下所示:

图 5:

5.png

生成 NodeBlock

图 6:

6.png

  每当处理一个新的 term 之前,我们先要 统计term栈中的prefixTopSize

term 栈跟 prefixTopSize 是什么

  term 栈即存放 term 的栈,prefixTopSize 是跟栈顶 term 有相同前缀的 term 数量,例如待处理的 term 集合如下所示:



    term集合 = {"abc", "acc", "acd", "acea", "aceb", "acee", "acef"}

图 7:

7.png

  从图 7 可以看出跟栈顶元素有最长相同前缀的 term 数量为 4,前缀值为"ace",那么此时 prefixTopSize 的值为 4,如果 prefixTopSize 超过 minItemsInBlock,那么就生成一个 NodeBlock。

minItemsInBlock 是什么

  minItemsInBlock 是一个 Lucene 中的默认建议值(Suggested default value),默认值为 25,它描述了至少有 minItemsInBlock 个有相同前缀的 term 才能生成一个 NodeBlock。

  如果 minItemsInBlock 的值为 5,在图 7 中,由于 prefixTopSize 的值为 4,所以不能生成一个 NodeBlock,那么就执行 更新term栈中的prefixTopSize 的流程点。

如何更新 term 栈中的 prefixTopSize

  根据新的 term 来更新 term 栈中的 prefixTopSize。我们用两种情况来介绍其更新过程。

  • 如果新的 term 为"aceg",那么将"aceg"添加到 term 栈以后如下图所示:

图 8:

8.png

  • 如果新的 term 为"acfg",那么将"acfg"添加到 term 栈以后如下图所示:

图 9:

9.png

为什么是生成一个或多个 NodeBlock

  前面我们说到 term 栈就是存放 term 的栈,这种说法只是为了便于介绍上文中的内容,term 栈里面实际存放了两种类型的信息,在源码中的对应的变量名如下所示,另外 term 栈在源码中对应的是 pending 链表:

  • PendingTerm:该值代表了一个 term 包含的信息
  • PendingBlock:该值代表的是具有相同前缀的 term 集合包含的信息

  我们另 minItemsInBlock 的值为 3(强调的是上文中 minItemsInBlock 的值为 5),我们以图 7 为例,如果我们插入一个新的 term,例如“ba”,由于此时 prefixTopSize 的值为 4,那么就可以将"acea", "aceb", "acee", "acef"这四个 term 的信息生成一个 NodeBlock,生成 NodeBlock 的过程将在下一篇文章介绍,在这里我们只需要知道在生成 NodeBlock 之后,它就会生成一个以"ace"为前缀的 PendingBlock,并且会添加到 term 栈中,如下所示:

图 10:

10.png

  由图 10 可,在生成以"ace"为前缀的 NodeBlock 之后,还可以生成以"ac"为前缀的 NodeBlock,如下所示:

图 11:

11.png

  图 10、图 11 生成 NodeBlock 的条件的判断逻辑是这样的:

  • 计算当前栈顶 term 的长度 i
  • 计算出新 term 跟当前栈顶 term 的相同前缀个数 pos
  • 如果栈顶 term 的相同前缀为 n 的 prefixTopSize 不小于 minItemsInBlock,那么就生成一个 NodeBlock,其中 n 的取值范围是(pos, i)

  图 10 的例子中,栈顶 term(”acef“)的长度 i = 4,新 term 为"ba",跟栈顶 term 没有相同前缀,所以 pos = 0,栈顶元素 term 的相同前缀 n 的取值范围为(0, 4),当 n=3(前缀为"ace")时,此时的 prefixTopSize 为 4,那么就可以生成一个 block,即图 10 的内容;当 n=2(前缀为"ac")时,prefixTopSize 为 3,那么就可以生成一个 block,即图 11 的内容;当 n=1(前缀为"a")时,prefixTopSize 为 2,由于小于 minItemsInBlock,故不能生成一个 PendingBlock。

结语

  图 6 的流程图对应的是源码 https://github.com/LuXugang/Lucene-7.5.0/blob/master/solr-7.5.0/lucene/core/src/java/org/apache/lucene/codecs/blocktree/BlockTreeTermsWriter.java 中的 pushTerm()方法,感兴趣的同学可以结合源码理解。


本文地址:https://www.6aiq.com/article/1586659744715
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出