番外篇：Lucene 索引流程与倒排索引实现

前两篇文章主要围绕 Lucene 的底层索引文件结构方面介绍了倒排索引原理：
Lucene 倒排索引原理探秘 (1)
Lucene 倒排索引原理探秘 (2)

在 Lucene 中，写数据的基本单元称之为 Document，本文将介绍一个 Document 写入 Lucene 后的索引全流程。

基础概念

如下几个概念，Lucene 的 Document 中给出了明确的定义，在这里先强调一下：

1. Document(文档) 由 Field(字段) 构成。

2. Field 是 Term 的集合。

3. Segment 是最小的独立索引单元，由多个 Documents 构成。

在每一个 Segment 范畴内，每一个 Document 都被分配了一个唯一的数字 ID，称之为 DocID，同时根据每个 Field 的名字定一个唯一的 FieldNaming，对于索引字段进到 Postings 之前也会被分配一个唯一的 TermID。Field 除了 FieldNaming 之外也有一个 FieldNumber，与 DocID 和 TermID 一样都是一个自增的数值。

整体流程

一个 Document 写到 Lucene 中，大致涉及如下六大处理过程：

1. 处理需要存储的 Fields

2. 构建正向索引

3. 对 Field 进行分词，构建倒排索引和 TermVectors

4. 处理 Points 类型字段 (6.0 以后的版本)

5. 保存分词字段的 Norms 信息

6. Flush 生成 Segment，完成数据持久化存储

这并不是意味着每一个 Document 必然会经历这六大过程，有一些过程是互斥的，如步骤 2 与 3、3 与 4、4 与 5 都只能二选其一，同时，每一个步骤也都可以通过配置跳过。

下面将详细展开每一个处理所关联的细节。

Field 存储

Field 数据的存储与否，是可选的。Lucene 关于 Field 存储的文件格式，与 MySQL 的 frm 文件格式类似。关于 Field 的处理，主要是由StoredFieldsConsumer完成。

Lucene 为了保证写入的性能，文档一旦提交后便不可改写，这点跟 MySQL 的_frm文件是不一样的。字段存储是唯一一个按文档存储的文件，此外都是打破文档的边界按字段存储的。_

另外，因为 Lucene 作为搜索引擎，它读取文档的操作往往是以随机访问的方式。为此 Lucene 将文档数据写到.fdt 文件的同时，还需要为 DocID 对应的文档所在.tdt 文件上位置构建索引，并将索引存储到.fdx 文件中，以提供快速随机访问的能力。

DocID 是 Lucene 的内部 ID，它被用来快速获取 Document，但使用者并不能直接获取。需要注意区分 DocID 与用户定义的有业务意义的文档 ID，它们并不是一回事。

索引构建及存储

在 Lucene 中，索引可以分成两类，正向索引 和倒排索引 。在索引过程中，通常需要指定在哪个 Field 中进行检索的，也就是 TermID 在所有具有相同 FieldName 的 Field 中是唯一的。

Lucene 通常为所有相同 FieldName 的字段分配一个PerField对象，由 PerField 实现所有字段级别所有操作。相同 FieldName 的所有 Field 在处理逻辑是可以认为是连续的，在这个过程中，DocID 仅作为 Term 的属性存在。Field 是 Terms 的集合，因此可以认为索引阶段 Field 就是所有同名 Field 的所有 Terms 的集合。

正向索引

正向索引 记录了 DocId 到 FieldValue 的映射关系，提供了通过 DocID 就能直接获取字段值的能力。DocValuesWriter将 DocIdSet 与 FieldValue 分别存储在类似数组的结构中，他们的存储顺序的是一致的。然后，DocValuesConsumer 将 FieldValues 和 DocIdSet 一并写到.dvd 文件中。每个需要存储 DocValues 的 Field 都有一对这样的结构，且 DocValues 是按字段连续存储在.dvd 文件中。每个 Field 的 DocIdSet 和 FieldValues 在 dvd 文件中的索引信息 (起始位置)，被存储在.dvm 文件中。

这实现上是一种列式存储的结构。这种列式存储结构，给 Lucene 带来很多二次计算的可能，比如 Hive On Solr/ElasticSearch，Solr 的高级特性 Streaming Expression 等。Streaming Expression 是 Solr 提供基于 Lucene 索引实现的计算框架，以及在 Streaming Expression 上实现 SQL 的能力。

_ 存储 DocID 的内存是用 DocsWithFieldSet（底层实际上是 BitSet），在磁盘上的组织则要复杂一些。在 Lucene7.0 之后，Lucene 针对 BitSet 的稠稀性，采用不同的存储方式：当 BitSet 比较稀疏时，直接存储 DocID；当 BitSet 稠密时，则直接存储 BitSet 的 Bits 数据。根据数据的分布情况不同，采用适当的结构不仅可以提高空间的利用率，还能提高遍历的效率。唯一的缺点估计就是实现起来比较复杂。_当前版本 DocValues 还不支持分词。

_
_

Lucene 定义多种 DocValues 类型，每种类型的存储方式有区别，但有一点是相同的：DocIDSet 和 DocValues 均为分开存储的。关于 DocValues 部分其实是一个大话题，这里不再过多展开。

倒排索引

与 Field 存储相较而言，倒排索引的构建则要复杂很多，因为涉及到整个 Segment 级别的信息处理，比如 Term 在哪些文档出现了，在每个文档分别出现几次，每次出现在什么位置等等，这些信息都是需要站到 Segment 这个视角上才能够收集。

Lucene 中的倒排索引实现分成两类：一种是传统的，按 Segment 构建的 Postings，这是我们通常理解的倒排索引结构；另一种方式是在每个上文档构建的 TermVectors，又叫词向量或者文档向量。

Postings

Posting 是大家所熟悉的结构：左边是 Terms 列表，记录 Field 中出现的所有的 Terms，也是叫 TermsDictionary；右边是 Postings，记录 Term 所对应的所出现哪些文档的文档号，出现次数，位置信息等。示意图如下：

在构建 Posting 过程中需要考虑如何收集 Terms 的位置信息和统计信息，还要考虑在大规模的数据量级下如何去重和排序。这些都是实现倒排索引需要考虑的关键问题，一些不合理的细节所导致的额外性能开销，就会直接影响全局索引性能。

现在我们来看一下 Lucene 构建 Posting 的过程： 在实时索引时，Postings 先在内存中临时构建。Field 被分词后变成一系列 Terms 的集合，而后遍历这个 Terms 的集合，为每个 Term 分配一个 ID，叫 TermID。Lucene 用一个类 HashMap 的数据结构来存储 Term 与 TermID 的映射关系，同时实现去重的目的。分配完 TermID 之后，后续就可以使用 TermID 来表示 Term。

在 Postings 构建过程中，会在 PostingsArrays 存储上个文档的 DocID 和 TermFreq，还有 Term 上次出现的位置和位移信息。PostingsArrays 由几个 int[] 组成，其下标即为 TermID(TermID 是连续分配的整型数，所以 PostingsArrays 是紧凑的)，对应的值便是记录 TermID 上一次出现的相关信息。就是说，Lucene 用多个 int[] 存储 Term 的各种信息，一个 int[] 存放 TermID 的一种信息。

Lucene 为了能够直接使用基本数据类型（基本类型有两大好处：减少内存开销和提升性能），所以才有了 PostingsArrays 结构。为了便于理解，PostingsArrays 可以表示为 Postings[]，每个 Postings 对象含有 docFreq,intStart,lastPos 等属性。

_
_

PostingsArrays 这个结构只保留每个 TermID 最后出现的情况，对于 TermID 每次出现的具体信息则需要存在其它的结构之中。它们就是IntBlockPool&ByteBlockPool，它能有效的避免 Java 堆中由于分配小对象而引发内存碎片化从而导致 Full GC 的问题，同时还解决数组长度增长所需要的数据拷贝问题，最后是不再需要申请超大且连续的内存。

限于篇幅，关于这两个结构的细节设计将在下一篇文章中分享。这里我们暂且将其看成两个连续的 int[] 和 byte[]，Postings 的数据实际只存储在 BytesBlockPool(byte[]) 一个地方，IntBlockPool(int[]) 中存储的是索引。

需要注意的是，Postings 是在 byte[] 存储的结构是一个表尾增加的链表结构，在构建索引的时候用 IntBlockPool 来记录 Term 下一次要写的位置。也就是说，PostingsArrays 的 intStarts[] 是 Term 的 byte[] 的表尾，而表头是记录在 PostingsArrays 的 byteStart 上，这也是一个 int 数组，记录每个 Term 的在 BytesBlockPool 的起始位置。有了表头和表尾之后，我们就可以 ByteBlockPool 里拿到整个链表了。

_
_

为什么不能直接写磁盘？这是因为在构建过程中无法知道 Postings 有多长，不能确定要预留多少空间；另外构建过程中 Term 是随机出现的而非有序的；最后是 Term 难以再排序，只能按 TermID 的顺序处理。

为什么需要 postingsArrays？因为写到 byte[] 的只是增量，那么就需要找到上次的 Term 出现情况才能计算。如果总是在 byte[] 上查找则显得过重，因为 Postings 存储在 byte[] 时，它的结构是一个单向链表。有了 PostingsArrays 中记录的上条信息，则便于计算增量。

这里多提一点，Lucene 在 Segment 提交之前，实现上不是在写 Buffer，而是先在内存上构建了。当 Segment 提交之后，将内存上的索引重新编码之后再刷磁盘。也就是说，索引在构建时写在内存的数据结构和编码与最终写在磁盘上的结构完全不一样。基于以上，且不仅限以上原因，需要先收集 posting 的信息。知道这点之后，至于它叫什么，是缓冲，预构建，还是收集都是一样的。

_
_

收集完，也就是已经把整个 Segment 的文档全部遍历了，此时触发 Flush 的操作。然后，将 Term 排序之后编排成 TermEnum 格式，此处进入索引写磁盘的步骤了。

关于倒排索引更多信息，在前两篇文章中已经详细披露了。

TermVectors

上面已经用了比较长的篇幅来介绍 Posting。接下来简单介绍第二种结构，需要存储的数据跟第一种实际上一样的，都是 Term 和 Term 的统计信息、位置信息。只不过，TermVectors 在 Postings 的基础又将 Terms 按文档做了重新排序。同一个文档中，如果一个 Field 中出现了一个同名的 Term 出现了两次，则会被分开记录两次。

回顾一下 Postings 中记录的几种信息：

TermFreq：在一个文档中出现的次数，通过与 DocID 成对出现。

Position：Term 出现的位置，相当于 DocID。

Offset：在文档内的位移，与 Position 一起才能确定一个位置。

Payload：附加信息，如词性等，可用于自定义评分等。

这些信息也是 TermVectors 需要记录的。显然这些信息实际上与是否在文档内并无影响，所以 TermVectors 记录信息实际上 Postings 并无太大差别。只不过对于 TermVectors 是已经知道 DocID 的，所以并不会在所有 Term 上记录 DocID。当然，Freq、Position 和 Offset 也不会记录在其它 Documnet 出现的情况了。此外还有一点需要注意的，TermVectors 把 Term 所有信息都记录在同一个文件上（.tvd），这与 Postings 的记录方式是一样的。Postings 将它们拆分成三个文件分别存储 DocID 和 TermFreq、Position 和 Offset、Payload。

Lucene 在存储 TermVectors 的时候，默认将 4096 个文档打包成一个 chunk 来存储。在一个 chuck 的结构如上图，这里想强调的是，TermFreq/Position/Offset/Payload 的存储格式基本一样，这里以 TermFreq 为例。

假设有个Term="Solr"出现这三个文档的 FieldA、FieldB 和 FieldC 三个字段中，它们 TermID 不一定相同，只要这三文档不是一样，它们极可能是不同的。因为每个文档的每个字段都有自己的 Term 和 TermID 的映射表，这就是跟 Postings 最大的差异。

为什么没有 DocFreq、TotalTermFreq 呢？如果已经读过《Lucene 倒排索引原理探秘 (1)》，应该知道这些字段级别的统计信息，它们会被存放在 TermDictionary 的 FieldMetaData 里。也就是说，Postings 和 TermVectors 都不会记录部分信息的。

TermVectors 在 Solr 中有挺多应该场景的，比如 Highlight，MoreLikeThis，分类聚类等 NLP 任务等。

默认 TermVectors 是开启的，虽然在搜索时，只要不用它就不会去读这部分信息。但是在索引时，还是会带来性能开销的。不仅如此 Segment Flush 之后还可能会出现多次 Merge，也都会带来一定的开销。如果在搜索时，不需要用 TermVectors 的情况下，可以将其省略掉。

PointValues

PointValues 原本用于地理位置信息的索引和查询，但它在多维数值或者多维数值区间索引和搜索上的表现也都非常出色。因此，PointValues 已成为数值字段的默认实现。原先的数值字段 (IntField/FloatField/LongField/DoubleField) 已被标记为废弃接口(@Deprecated)，且加了 Legacy 前缀。

Solr 在Solr7.0开始支持 PointValues，并成为数值字段的推荐使用类型。同时 BackPort 到Solr6.5版本。

PointValues 采用新存储结构: BKD-Tree(KD-Tree 的变种) 。KD-Tree 主要应用于多维空间，范围搜索和最近邻搜索。BKD-Tree 是基于 KD-Tree 实现的数据结构，它有高效的 IO 性能、更高磁盘利用率等优点。基于 BKD-Tree 实现的 IntPoint（含 LongPoint，FloatPoint，DoublePoint）不管是索引的性能，还是在搜索的性能都比原先的 TrieField 的性能更加高，索引文件也更小，尤其是搜索时占用 Heap 内存要小很多。

PointValues 是一个非常有价值 **** 的特性 ，它并不只是适用于多维的空间搜索，在一维的各个场景下的性能指标也都非常不错，强烈推荐大家关注并且使用该特性。

Norms

Norms，Normalization Factors，存储的是每个文档中每个字段的归一化因子和 Boost（索引时的 Boost 已经被弃用了，交由 Payload 接管）。这两个数值都会直接影响搜索时最终文档评分。

在 TFIDFSimailary 模型下，归一化因子的计算可以简单理解为 log2(1/numTerms)。

Norms 是所有索引文件中最简单的，所以它在我脑海中的存在感极弱。Norms 可以通过配置FieldType.setOmitNorms(true)，表示不存储 norms，但默认是会存储的。这个配置是字段级别的，也就是在一个多字段的文档中，可以选择部分字段存储，部分不存储。由上公式就可以知道，Norms 的计算需要知道字段中去重后有多少个 Terms，所以它跟 Postings 也算是有一点关系的，也是放在 Postings 之后处理的。

总结

这篇文章讲解了 Lucene 为一个 Document 构建索引的处理流程，重点讲解了两种倒排索引结构，Posting 与 TermVectors，希望能够结合前面的两篇文章来加深大家关于 Lucene 倒排索引结构的理解。