在Lucene倒排索引原理探秘(1)和Lucene倒排索引原理探秘(2)两篇文章中详细介绍了Lucene的倒排索引文件组织结构，这为高效的搜索过程奠定了良好的基础。

我们已经知道，Lucene的倒排索引有两种格式：一种是用于搜索的Postings；另一种是TermsVectors。这两种索引的构建过程基本相同，只是写文件时在编排方式上有所差异，在《番外篇：Lucene索引流程与倒排索引实现》一文中已经做了详细介绍。

在构建倒排索引的过程中，Lucene需要收集每个Term在整个Segment中的相关信息(DocID、TermFreq、Position、Offset、Payload），并且将这些信息存储下来，如下图所示。因此，在索引阶段，如何高效的收集这些信息，显得至关重要，本文将以Postings索引格式为例，详细探讨Lucene索引过程中所采用的数据结构与技术手段。

数据结构

Lucene设计了一系列内存高效的数据结构，通过对象复用和内存分页的思想，来优化Java GC问题。这部分内容将围绕ByteBlockPool、ByteRefHash、PostingsArray三个结构展开。

ByteBlockPool

ByteBlockPool是Lucene实现高效的可变长的基本类型数组，但实际上数组一旦初始化之后长度是固定的，因为数组申请的内存必须是连续分配的，以致能够提供快速随机访问的能力。那么ByteBlockPool是如何实现的？

Buffer结构

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

ByteBlockPool是一个可动态增长的结构，如下图所示：

ByteBlockPool是一个由多个Buffer构成的数组，如上图右侧所示，左侧的数字则代表了每一个Buffer在这个二维数组中的Index位置。Buffer的长度是固定的，当一个Buffer被写满以后，需要申请一个新的Buffer，如果这个Buffer数组要扩展，仅仅是将已有Buffer的引用拷贝了一次，而不需要拷贝数据本身。Buffer本质上是一个byte[]，因此，ByteBlockPool其实是一个byte的二维数组，用Buffer数组来表达则更易理解。

Slice链表

索引构建过程需要为每个Term分配一块相对独立的空间来存储Posting信息。一个Term可能会出现在几个文档中，而且在每个文档出现的次数和位置都无法确定，所以Lucene无法预知Term需要多大的数组来存储Posting信息。

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

Slice节点可以跨越多个Buffer，Slice链表为我们提供了一个逻辑上连续的内存块。如果将Slice链表理解成类分布式文件系统上的文件，每个Slice则是文件的数据块，不过文件系统的数据块的大小是固定的，而Slice的长度则是分层级的。

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

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

BytesRefHash

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

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

BytesRefHash用来存储Term和TermID之间的映射关系，如果Term已经存在，返回对应TermID；否则将Term存储并且生成TermID后返回。Term在存储过程BytesRefHash将BytesRef的有效数据拷贝在ByteBlockPool上，从而实现紧凑的key值存储。TermID是从0开始自增长的连续数值，存储在int[]上。BytesRefHash非散列哈希表，从而TermID的存储也是紧凑的。

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

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

PostingsArrays

从PostingsArrays名字上容易被误以为是存储Postings数据的结构，实则不然。在Postings构建过程中，Lucene将各项信息写到ByteBlockPool的Slice链表上。链表是单向链表，它的表头和表尾存储到PostingsArrays，从而能够快速写入，并且可以从头开始遍历。这个结构曾在《番外篇：Lucene索引流程与倒排索引实现》一文中介绍过。

PostingsArrays除了记录了Slice链表的索引之外，它还存储上个文档的DocID和TermFreq，还有Term上次出现的位置和偏移信息。PostingsArrays由几个int[]组成，其下标都是TermID（TermID是连续分配的整数），对应的值便是记录TermID上一次出现的各种信息。

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

索引构建过程

在索引构过程中，Term由TextField经过TokenStream处理之后产生，它由一个可复用对象BytesRef表示。在建构索引的链路上，Lucene更多是用TermID来表示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链表上，同时会记录增量信息，为了节省内存空间，Position/Offset第二次及以后都用VInt来记录这个增量值。

这就是PostingsArrays需要记录lastPosition/lastOffset的原因，而lastDocID和lastTermFreq不仅可用计算增量，还可以用来计算Term每次出现后TermFreq的累加值。需要说明的一点：每个信息在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完成索引文件的输出。至此，已经完成了一轮构建索引的流程。

本文转载自微信公众号【Nosql漫谈】。

原文链接：https://mp.weixin.qq.com/s/_k-toltGmSBIl8zPq93jPQ