Lucene倒排索引简述 细说倒排索引构建

文章目录

一、数据结构

1. ByteBlockPool

1.1 Buffer结构

1.2 Slice链表

2. BytesRefHash

3. PostingsArrays

二、构建索引过程

在《Lucene倒排索引简述 之索引表》和《Lucene倒排索引简述 之倒排表》两篇文章中介绍了Lucene如何将倒排索引结构写入索引文件，如何为实现高效搜索过程奠定了基础。

Lucene需要收集每个Term在整个Segment的所有信息（DocID/TermFreq/Position/Offset/Payload），从而实现下图所示倒排索引结构构建且存储。所以问题的关键在于Lucene采用了些数据结构和手段实现高效的收集任务，完成索引时性能要求的呢？

前面的文章中介绍过Lucene的倒排索引有两种格式，一种是用于搜索的Postings，在源码中由FreqProxTermsWriterPerField负责；另一种是TermsVectors，由TermsVectorsWriterPerField实现。这两种索引的收集过程基本相同，只是写文件时有各自的编排方式上有所差异。更多的内容请阅读《Lucene倒排索引简述 番外篇》。这里我们以第一种方式为例，来探索Lucene索引的高效之道。

假设直接利用文件系统来完成这种任务，那么就是每个Term都有一个独立的文件，文件名就是TermID，用一个List来存储文件句柄。这种做法也是可以的完成我们的需求，但这种方式存在非常大的问题。因为它会带大量的磁盘的随机写，磁盘本身的性能比较差，所以它可能还会加剧系统的IO问题。

Lucene利用这种思想在内存上设计一系列的结构以实现高性能，能够避免大量对象的频繁创建与销毁带来的性能开销和可能引发GC问题的实现方案。本文将从这个角度开始来探究倒排索引构建过程中使用的各个数据结构。

一、数据结构

设计合适的数据结构对影响提升至关，在特定的场景使用的合适的结构是成功的基石，进而考虑算法问题。算法通常是特定结构下讨论的话题，Lucene采用哪些数据结构奠定了构建索引的性能呢？

1. ByteBlockPool

ByteBlockPool是Lucene实现高效的可变长的基本类型数组，但实际上数组一旦初始化之后是长度是固定的，因为数组申请的内存必须是连续分配的，以致能够提供随机访问的能力。那么ByteBlockPool采用什么手段来解决这样的问题？

1.1 Buffer结构

在所有JDK中以数组为底层存储的数据结构，如ArrayList/HashMap，实现可增长时都需要花一定代价的。数组增长的过程分两步，首先申请更大数组，然后将原数组复制到新数组上。即使JVM已经对数组拷贝做了很多优化，如今拷贝的性能开销已经很小了。但是在大量的索引时使得存储在数组上的数据不断增长，拷贝的性能开销会慢慢突显出现，同时数组频繁创建也都会带来JVM的GC问题。

ByteBlockPool是一个增长的数据结构，它实现可增长的秘密是利用二维数据的特性，二维数组是在一维数组上引用另一维数组，即是数组中的数组。 如果把它看成是List<byte[]>的形式，在List中每个元素存储放的是int[]的引用，将它可视化之后如下图：

当在我们声明二维数组的时候，如果只指定第一维组的长度时，这方式申请的二维数组，两维数组在Heap上不会连续分配。

如此说来，我们将的二维数组的每一行称为Buffer，列叫为Buffer索引。放回到List<byte[]>理解这个结构，List存储的是byte[]引用，那相当于是byte[]的索引。这里我们称byte[]为Buffer，List即是Buffer的索引。Buffer的长度是固定，当Buffer被写满了之后，需要仅继续申请一个Buffer，省去常规的数组增长之后数据拷贝的过程。

1.2 Slice链表

到这里Lucene仅仅完成了存储大量数据的问题，索引构建过程还需要为每个Term都需要一块相对独立的空间来存储Posting信息。但在收集过程，Term会出现在几个文档中，每个文档出现次数和位置都无法确定，所以Lucene无法预Term需要多大的数组来存储Posting信息。

为此Lucene在ByteBlockPool之上设计了可变长的逻辑结构，这结构就是Slice链表。它是由Slice为节点的链表，Lucene将Slice分成十级别，逐层递增，十层之后长度恒定。Slice的最后一个位置用于存储下个节点Offset，当最后一个Slice时存储下个Slice的层级数。

Slice节点可以跨越多Buffer，Slice链表为我们提供了一个逻辑上连续的内存块（byte[]）。它就是类似于文件系统上文件，每个Slice即是文件的数据块，不过文件系统的数据块的大小是固定的，而Slice的长度是分层级的。

这种设计方案好处是，Buffer会是相对比较紧凑的结构，能够更充分利用的Buffer内存。按Zipf定律可知一个单词出现的次数与它在频率表里的排名成反比，也就说可能会很多Term的频率是很小的，同样也有小部分Term的频率非常大，Slice的设计也是考虑这一特点。

Slice链接初始化时在Buffer上分配一个比较小的Slice节点，可以看得出来Buffer上的Slice非常紧凑的数据结构，属于ByteBlockPool的Buffer内部结构，Slice的链表相当于是一个文件，是一个连续且统一的结构。

ByteBlockPool与IntBlockPool设计思想完全一样，IntBlockPool只能存储int，ByteBlockPool存储byte，这里我们不再复述。Lucene仅实现这两种数据类型，其它的类型可以通过编码之后用ByteBlockPool存储。

2. BytesRefHash

Lucene在构建Postings的时候，采用一种类似HashMap结构，这个类HashMap的结构便是BytesRefHash,它是BytesRefHash是一个非通用的Map实现。 它的非通用性表现在BytesRefHash存储的键值对分别是Term和TermID，其次它并没有实现Map接口，也没有实现Map的相关操作。

Term在Lucene中通常会被表示BytesRef，而BytesRef的内部是一个byte[]，这是一个可以复用对象。当通过TermID在BytesRefHash获取词元的时候，便是词元在存储ByteBlockPool的byte[]拷贝到BytesRef的byte[]，同时指指定有效长度。整个BytesRefHash生存周期中仅持有一个BytsRef，所以该BytesRef的byte[]长度是最词元的长度。

BytesRefHash是为Postings构建过程生成并存储Term和TermID之间的而设计的结构，如果Term已经存在，返回对应TermID；否则将Term存储，同时生成TermID并返回。Term在存储过程BytesRefHash将BytesRef的有效数据拷贝在ByteBlockPool上，从而实现紧凑的key的存储。TermID是从0开始自增长的连续数值，存储在int[]上。BytesRefHash非散列哈希表，从而TermID的存储也是紧凑的。

因为BytesRefHash为了尽可能避免用到对象类型，所以直接采用int[]存储TermID，实际上也就很难直接采用散列表的数据结构来解决HashCode冲突的问题。

Lucene构建倒排索引的过程分了两步操作，构建Postings和TermVectors。它们俩过程共享一个ByteBlookPool，也就是在每个DocumentsWriter共用同一个ByteRefHash（因为BytesRefHash以ByteBlockPool都不是线程安全的，因此它们都是线程级别）。它为Postings收集过程提供去重和Term与TermID对应关系的存储及检索。

3. PostingsArrays

从PostingsArrays的名字上容易被误以为是就Postings收集的存储结构，实则并不是。在Postings构建过程中，Lucene是将各项信息写到ByteBlockPool的Slice链表上。链表是单向链表，它的表头和表尾存储到PostingsArrays，从而快速写入和从开头开始遍历。这个结构曾在《Lucene倒排索引简述 番外篇》介绍过，可以配合起来读。

PostingsArrays除了记录了Slice链表的索引之外，它还存储上个文档的DocID和TermFreq，还有Term上次出现的位置和位移的情况。即是PostingsArrays由几个int[]组成，其下标都是TermID（TermID是连续分配的整型数，所以PostingsArrays是能被紧凑的存储的），对应的值便是记录TermID上一次出现的各种信息了。就是说Lucene用多个int[]存储Term的各种信息，一个int[]仅存TermID的一种信息中的一个数据。

Lucene为了能够直接使用基本类型数据，才有PostingsArrays结构的。方便理解你可以理解成是Postings[]，每个Postings对象含有DocId,TermFreq,intStarts,lastPosition等属性。

二、构建索引过程

在索引构过程中，Term由TextField经过TokenStream之后产生，它由一个可复用对象BytesRef表示。但在建构索引的链路上，Lucene更多的是用TermID来表示Term，因为TermID是连续分配的数值，也是为了适用PostingsArrays的结构特点。这是PostingsArrays工作原理的第一前提，可以用数组来存储Term对的信息。

当Term第一次出现时，Lucene尝试在BytesRefHash取到TermID失败，此时Lucene将它的状态标记新人。新出现的Term作为新生婴儿，需要在BytesRefHash上为它分配一个身份证号（TermID）。然后在PostingsArrays登记户籍信息了，它记录了它的名字（BytesRef的byte[]）在哪个位置（前面提过，BytesRefHash直接把Term存储在ByteBlockPool的，所以需要位置记下来）；然后为建立一个履历档案（第一Slice链表），记录它将来在每个年级（DocID）的考试次数（TermFreq）。

如果地区比较有心，还会另一份为Term建那个一档案（第二Slice链表）用于记录，每个次考试的情况，如果班级（Position），座位号（Offset），以及成绩（Payload）。这些数据是Term成长过程的产生的，经历一次记一次。关于每次考试的情况，第一次考试Lucene直接把它写入ByteBlockPool的Slice链表上，同时会记一会在PostingsArrays用于下次记录计算增量。为了节省内存空间，Position/Offset第二次及以后都用VInt来记录它的增量。

这就是为什么PostingsArrays需要记录lastPosition/lastOffset的原因，关于lastDocID和lastTermFreq除了因为需要算增量之外，还因为Term每次出现都累加，所以先在PostingsArrays记录。此外则是每个信息在Slice中是没有索引，不方便回溯和修改。

构建索引的过程，实际上就是ByteBlockPool(IntBlockPool)、BytesRefHash和PostingsArrays三者之间的协作。当它们同框之后，结构的美感体验淋漓尽致。

这里为了简化流程，图中将IntBlockPool简化成为int[]，也就是说它也是Slice的方式实现连续的链表。

PostingsArrays的byteStarts[TermID]记录Term的俩个链表的表头在ByteBlockPool的绝对位置，intStarts[TermID]记录下次要写的位置，则textStarts[TermID]则是记录BytesRefHash把Term存储在ByteBlockPool的哪个位置上。

为什么byteStart和intStart需要先指向IntBlockPool呢？ 主要是因为TermID对应可能会有两条Slice链表，以TermID为索引的数组不方便存储。通过IntBlockPool可以方便处理，仅需要IntBlockPool连续两个位置，下一个位置用于存储第两个Slice链表。当然IntBlockPool的引入让这个过程变得更复杂了，也体现Lucene的设计之精湛和巧妙。

将表尾是为了方便写入数据，表头将是了方便遍历了。在索引提交的时候，Lucene将这两个Slice链表的数据通过PostingsEnum遍历出来，交由BlockTreeTermsWriter完成索引文件的产出。构建索引过程也就走向终点，同时新一轮的索引构建开始。