4、字典树：Trie（Prefix Tree）原理

一直以来，数据结构的“小”而“快”是每个追求更好性能的developer孜孜不倦追求的目标，所谓“快”即检索速度快，“小”即通用最小化算法。上一节我们介绍了倒排表的数据压缩原理和过程，自本节开始，我们分几部分详细介绍一下Lucene中对倒排索引Term DIctionary以及Term Index的数据压缩和优化算法。

我们已经了解到，Term Dictionary是字典序非重复的 K-V 结构的，而通常搜索引擎级别的倒排索引，Term Dictionary 动辄以“亿”起步，这势必要求我们在做数据存储时对其数据结构有极其高的要求。以图4-1为例，假设途中英汉词典片段就是我们要存储的词项字典，为了遵循“通用最小化算法”对其进行数据压缩，我们就必须要考虑如何以最小的代价换区最高的效率。通过观察不难发现，无论任何一个Term，无外乎由26个英文字母组成，这也就意味越多的词项就会造成的越多的数据“重复”。这里所说的重复指的是词项之间会有很多个公共部分，如“abandon”和“abandonment”就共享了公共前缀“abandonment”。我们是否可以像Java开发过程中对代码的封装那样，重复利用这一部分公共内容呢？答案是肯定的！Lucene在存储这种有重复字符的数据的时候，只会存储一次，也就是哪怕有一亿个以abandon为前缀的词项，“abandom”这个前缀也只会存储一次。这里就用到了一种我们经常用到的一种数据结构：Trie即字典树，也叫前缀树（Prefix Tree）。下面我们以Term Dictionary：（msb、msbtech、msn、wltech）为例，演示一下Trie是如何存储Term Dictionary的。

如上图4-2所示，我们按照每个Term一步来演示Trie是如何存储Term Dictionary的。图中我们以圆形标识节点，箭头代表节点的出度，出度存储了当前节点对应的字符。当输入词项“msb”的时候，如果图中第一步所示，图中以加粗的圆圈标识当前节点是一个终止节点。当输入第二个词项“msbtech”的时候，复用了“msb”，当输入“msn”的时候，节点2添加了第二个出度，至此我们已经实现了对重复关键字的复用。但是问题也就随之而来了，当最后一个Term输入的时候，节点0产生了第二个出度。

5、FST的构建原理

细心的你应该已经发现了，在使用字典树存储Term Dictionary的案例中，字符“tech”也属于重复部分，但是未被合理复用，导致了空间浪费。为了解决这个问题，Lucene采用了另一种数据结构：FST（Finite State Transducer），即“有限状态转换机”。FST是本章内容难点，也是倒排索引的核心数据结构。

通常我们在计算机的语言中标示一件事物，都会通过某种数学模型来描述。假如现在我们要描述一件事：张三一天的所有活动。这里我们采用了一种叫做FSM（Finite State Machine）的抽象模型，如图5-1所示，这种模型使用原型的节点标示某个“状态”，状态之间可以互相转换，但是转换过程是无向的。比如睡觉醒了可以去工作，工作累了可以去玩手机；或者工作中想去上厕所等等。在这个模型中，标示状态的节点是有限多个的，但状态的转换的情况是无限多的，同一时刻只能处于某一个状态，并且状态的转换是无序切循环的。

显然这种模型并不适用于描述Term Dictionary这样的数据结构，但是我们之所以提他，是为了方便读者理解这种具化事务抽象化描述的方式。虽然FSM并不适合，但是在他的基础上演化出了FSA（Finite State Acceptor）,我们仍然以图 4-2 中的Term Dictionary数据为例，演示一下FSA是如何在Trie的基础上进行优化的。

如上图5-2所示，相较于FSM，FSA增加了Entry和Final的概念，也就是由状态转换的不确定性变为了确定，由闭环变为了单向有序，这一点和Trie是类似的，但是不同的是，FSA的Final节点是唯一的，也是因为这个原因，FSA在录入和Trie相同的Term Dictionary数据的时候，从第三步开始才表现出了区别，即尾部复用。如果在第三步的时候还不太明显，那第四步中就可以清楚的看到FSA在后缀的处理上更加高效。

至此，FSA已经满足了对Term Dictionary数据高效存储的基本要求，但是仍然不满足的一个问题就是，FSA无法存储key-value的数据类型，所以FST在此基础上为每一个出度添加了一个output属性，用来表示每个term的value值。下面以Term Dictionary：（msb/10、msbtech/5、msn/2、wltech/8、wth/16）为例，演示一下FST的构建原理，斜线后面的数字代表每个term的输出值。

通用最小化算法的应用面非常广泛，这里其实也是遵循了这样的规则。可复用的不仅仅Term的字符，输出值之所以被存储了最靠前的位置上，目的也是为了让更多的Term复用，如果输出值产生了冲突，再去处理冲突问题，最终生成最小化FST。

如上图5-3所示，当第一个term:msb被写入FST中，其输出值被保存在了其第一个节点的出度上，在数据从FST中读取的时候， 计算其每个节点对应的出度的输出值以及终止节点的final output值的累加和，从而得出输出值，此时msb的输出值就是10+0+0+0=10，但是这里我用0来标识没有输出值，但实际情况没有输出值就是空而不是0，这里写0只是为了方便你去理解，这一点是需要注意的。

当第二个term:msbteach被写入的时候，其输出值5与msb的输出值10发生了冲突，这时，通用最小化算法法则再次发挥了功效。数字虽然不能像字符那样以前缀作为复用手段，但是数字是可以累加的，10可以拆成两个数字5，这样10和5就产生了公共部分，即5，所以这个时候m的输出值就需要改成5，那另一个5就需要找一个合适的位置，然而把它存放在任何一个节点的出度上似乎都会影响msbtech的计算结果，为了避免这个问题，可以把这个多出来的属于msb的输出值存入msb的final节点的final output中，节点的final output只会在当前出度是输入值的最后一个字符并且出度的target指向的是final节点的时候，才会参与计算。因此此时的msb和msbtech就各自把输出值存入了合适的位置，互不影响而且做到了“通用最小化”原则。

输入第三个term:msn，节点2产生了第二个出度：n，2 < 5，根据"通用最小化"法则，2和5有公共部分：2，5倍拆分成了2和3，此时公共前缀为“ms”，前面以“ms”为前缀的所有term都讲重新计算出度output，此时3需要满足：不能存放在公共前缀“ms”上，并且也不能在第二条出度“n”上，因此只能存放在出度b上，因为b在当前节点2第一条出度的链路上是最靠前的位置。这里FST和Trie最大的区别就是FST不仅使用了公共前缀，而且还计算了公共后缀，“msn”的最终节点会指向节点7，和节点6的出度h共享终止节点。

其实到这里还不能很好的提现“公共后缀”，但是输入wltech的时候，此时就产生了公共后缀“tech”，节点2的出度b和节点8的出度t共同指向了节点3。

输入最后一个term:wth，公共前缀为w，公共后缀为h，最终生成的FST如上图5-4所示。

6、Lucene中FST的构建过程

FST的压缩率非常高，相比HashMap，FST的性能相差的并不多，但是可以大大的节省空间占用。“搜索引擎”级别的词项字典动辄几亿甚至几十亿的数量级，如果使用FST对其进行存储，其高效的数据存储使得数据被压缩的很小，使其完全缓存在内存中成为了可能。FST在Lucene中的应用非常广泛，比如同义词处理、模糊查询、Suggest等都有应用。

我之前提到过，在计算机编程语言的世界里，描述一件事情通常使用某种数据模型，如FSM。在Lucene中使用了一个了个泛型来描述FST的数据结构：org.apache.lucene.util.fst.FST，在FST对象的构建过程中，又使用了一个Node的类型的对象来描述FST模型中的“节点”，使用Arc来表示节点Node的出度。Lucene把Node分成了两种，分别是UnCompiledNode和CompiledNode，他们的区别就是是否“Compiled”，暂时可以理解为是否经过了某种处理，处理之后就是CompiledNode，否则就是UnCompiledNode，这里所说的“处理”指的就是构建FST对象中的一个过程。未处理过的Node也就是所有UnCompiledNode被放在了一个UnCompiledNode类型的数组中：UnCompiledNode[]

如图6-1所示，假设次数输入第一个Term，此时当前term所有的字符都不会被处理，因为FST的构建是遵循“尾部冻结”的规则的。那么什么是尾部冻结呢？首先我们知道FST最终会被构建成一个FST对象，那这个对象最终转换成二进制对象存储在一个BytesStore对象中，，在Lucene 8.7.0中，BytesStore中封装了一个byte[]类型的数组：current，current数组就是专门存储经过处理之后的节点（CompiledNode）的，当然经过处理后的节点以及其出度的信息都会被转换成二进制存储在current数组中，BytesStore可以理解为是一个字节数组的增强版，是新版本Lucene对current数组的优化，当构建的FST对象大于1GB的时候就会使用BytesStore可以理解为是一个字节数组的增强版对象来存储，否则使用current数组。那么什么时机才是“Compiled”这个动作最好的时机呢？也就是什么时候才是我们从CompiledNode数组中摘下来节点并且计算结果存放在current中的最好时机呢？当然就是等当前节点不会再发生任何变化的时候，因为只有当节点的所有属性都不再发生改变的时候，记录它的描述才是有意义的。那什么时候才能确定它不再会发生改变了呢？以图4-1中的Term Dictionary为例，FST的构造器Builder会在输入第一个term的时候在其构造函数中创建一个长度为10的默认的frontier数组：

// NOTE: cutting this over to ArrayList instead loses ~6%
// in build performance on 9.8M Wikipedia terms; so we
// left this as an array:
// current "frontier"
private UnCompiledNode<T>[] frontier;
final UnCompiledNode<T>[] f =
    (UnCompiledNode<T>[]) new UnCompiledNode[10];
frontier = f;

当输入第一个term:abandon的时候，在frontier中“挂载”了8个UnCompiledNode和对应的7个Arc的信息，此时并没有任何Node和Arc被写入current[]，因为现在并不能确定任何节点将来是否会发生改变，换句话说，现在还无法确定后面是否有“a”、“ab”、“aba”、“aban”、“aband”、“abando”、“abandon”其中任何一个为前缀的词项，因为下一个term没有输入，它有可能是ac，如果是ac那么Arc a（这里指的是abandon的第一个字符a）对应的节点就产生了第二个出度，也就是发生了变化。注意Arc a对应的节点不是Arc a的target节点，而是a前面的节点，即Arc a是其对应节点的出度；同理，下一个Term也可能是abb，此时Arc a就未发生变化，而是Arc b产生了变化，新增了第二个出度b；当然也可能是abandonment，此时第一个term的终止节点n发生了变化，因为原本n的出度为0，但是现在为1，即Arc m，因此我们在下一个term输入之前，无法确定当前term未来将会发生何种变化。

我们仍然以图4-1中的Term Dictionary为例，当第三个term:abbreviation输入的时候，就可以确定以后不再会有以aba为前缀的term了，因为所有的词项都是按照字典序排列的，当第三个字符出现b的时候，就意味着aba前缀的完结，也就是说此时abandom中的第四个节点S-a也就是Arc a（abandon中的第三个字符）的target节点不再会发生任何改变了，这里需要注意，Arc a对应的节点目前仍不能确定在未来是否会发生改变，因为其对应的节点是S-b也就是Arc b的target节点，后面还有可能会出现以“abc”、“abd”等为前缀的term，因此当前只能冻结节点s-a也就是frontier中的第四个节点。

刚才所描述的这个确定节点不再会发生改变的过程就叫做尾部冻结（freezeTail），freezeTail的实现如下：

// minimize nodes in the last word's suffix
// 最小化最后一个单词后缀中的节点
private void freezeTail(int prefixLenPlus1) throws IOException {
  final int downTo = Math.max(1, prefixLenPlus1);
  for(int idx=lastInput.length(); idx >= downTo; idx--) {
    boolean doPrune = false;
    boolean doCompile = false;
    final UnCompiledNode<T> node = frontier[idx];
    final UnCompiledNode<T> parent = frontier[idx-1];
    if (node.inputCount < minSuffixCount1) {
      doPrune = true;
      doCompile = true;
    } else if (idx > prefixLenPlus1) {
      if (parent.inputCount < minSuffixCount2 || (minSuffixCount2 == 1 && parent.inputCount == 1 && idx > 1)) {
        doPrune = true;
      } else {
        doPrune = false;
      }
      doCompile = true;
    } else {
      doCompile = minSuffixCount2 == 0;
    }
    if (node.inputCount < minSuffixCount2 || (minSuffixCount2 == 1 && node.inputCount == 1 && idx > 1)) {
      for(int arcIdx=0;arcIdx<node.numArcs;arcIdx++) {
        @SuppressWarnings({"rawtypes","unchecked"}) final UnCompiledNode<T> target =
        (UnCompiledNode<T>) node.arcs[arcIdx].target;
        target.clear();
      }
      node.numArcs = 0;
    }
    if (doPrune) {
      node.clear();
      parent.deleteLast(lastInput.intAt(idx-1), node);
    } else {
      if (minSuffixCount2 != 0) {
        compileAllTargets(node, lastInput.length()-idx);
      }
      final T nextFinalOutput = node.output;
      final boolean isFinal = node.isFinal || node.numArcs == 0;
      if (doCompile) {
        parent.replaceLast(lastInput.intAt(idx-1),
                           compileNode(node, 1+lastInput.length()-idx),
                           nextFinalOutput,
                           isFinal);
      } else {
        parent.replaceLast(lastInput.intAt(idx-1),
                           node,
                           nextFinalOutput,
                           isFinal);
        frontier[idx] = new UnCompiledNode<>(this, idx);
      }
    }
  }
}

再回到图6-1的例子中来，假设输入的第二个term是“abe”，此时如图6-2所示。图中浅粉色节点表示S_e是新加入frontier数组的节点，蓝色加粗边框表示节点S_d是被执行了freezeTail操作，成为了一个CompiledNode。

理解FST在Lucene中的构建原理，我们还需要知道什么是PendingBlock和PendingTerm。这两个对象是Lucene在Node的基础上抽象出的两个概念，他们同时继承自PendingEntry。其代码实现如下：

private static final class PendingTerm extends PendingEntry {
    public final byte[] termBytes;
    // stats + metadata
    public final BlockTermState state;
    ...
private static final class PendingBlock extends PendingEntry {
  public final BytesRef prefix; //block前缀的长度（有leading label需要+1）
  public final long fp; //block在tim文件中的起始位置
  public FST<BytesRef> index; //第一个PendingBlock的FSTIndex的二进制对象
  public List<FST<BytesRef>> subIndices;  //ckPendingBlo中嵌套的PendingBlock集合
  public final boolean hasTerms;  //是否包含至少一个完整的的Term（即"非Block"也就是PendingTerm）
  public final boolean isFloor; //是否是floorBlock，即层级块
  public final int floorLeadByte; //即leading label 如果不是floor block生成的PendingBlock 那么返回-1
  ...

为了弄清楚这两个对象的含义，我们借助下面这张图来帮助我们辅助理解，需要注意，这张图仅仅是为了帮助我们理解几个概念，此图并非FST的原理图。

假设上图中树形结构描述的是左侧的Term Dictionary，当节点的子节点的数量不止一个的时候，它可能就是一个Block。比如我们暂时就可以把图中的a、b、f、g都可以看成是Block。关于Block的理解，可以参考本章图2-2中对Block的解释。从图中可以清楚的看到，节点a、b、f、g都包含至少2个或以上的子节点，所以暂时可以把它们看成是一个block。但是在org.apache.lucene.codecs.blocktree.BlockTreeTermsWriter中的writeBlocks方法有这么一段代码：

if (itemsInBlock >= minItemsInBlock && end-nextBlockStart > maxItemsInBlock) {
   // The count is too large for one block, so we must break it into "floor" blocks, where we record
   // the leading label of the suffix of the first term in each floor block, so at search time we can
   // jump to the right floor block.  We just use a naive greedy segmenter here: make a new floor
   // block as soon as we have at least minItemsInBlock.  This is not always best: it often produces
   // a too-small block as the final block:
   boolean isFloor = itemsInBlock < count;
   newBlocks.add(writeBlock(prefixLength, isFloor, nextFloorLeadLabel, nextBlockStart, i, hasTerms, hasSubBlocks));
   hasTerms = false;
   hasSubBlocks = false;
   nextFloorLeadLabel = suffixLeadLabel;
   nextBlockStart = i;
}

在这段代码中的英文注释，大概含义是说：如果一个Block太大，也就是子节点过多，Lucene就会把它划分成多个floor blocks（层级块），并且把每个floor block中的第一个字符记做leading label，目的是为了floor block的快速定位。并且在floor block分块的时候，使用了贪婪计数的法则，当block满足至少包含minItemsInBlock个entry信息的时候，才会生成一个block，这种规则通常会导致最后一个block中包含的entry的数量最少。

具体floor是如何划分的？BlockTreeTermsWriter类中定义了两个final类型的静态成员：DEFAULT_MIN_BLOCK_SIZE和DEFAULT_MAX_BLOCK_SIZE。

/** Suggested default value for the {@code
 *  minItemsInBlock} parameter to {@link
 *  #BlockTreeTermsWriter(SegmentWriteState,PostingsWriterBase,int,int)}. */
public final static int DEFAULT_MIN_BLOCK_SIZE = 25;
/** Suggested default value for the {@code
 *  maxItemsInBlock} parameter to {@link
 *  #BlockTreeTermsWriter(SegmentWriteState,PostingsWriterBase,int,int)}. */
public final static int DEFAULT_MAX_BLOCK_SIZE = 48;

这里min值和max值分别代表划分floor时满足条件的最小和最大的临界值，其关系是 max <= 2 * (min -1)。也就是说，当block节点的子节点count >= DEFAULT_MIN_BLOCK_SIZE的时候，才会被划分floor block，否则就是pending term，但是当floor count的节点数继续增加到DEFAULT_MAX_BLOCK_SIZE的时候就会被截断，也就是floor block节点的最大值就是DEFAULT_MAX_BLOCK_SIZE，当超过这个临界值的时候，就会被划分成多个floor block或者pending term。如果block的subIndices数量大于等于DEFAULT_MIN_BLOCK_SIZE且小于等于DEFAULT_MAX_BLOCK_SIZE的时候，Block不会被拆分，此时Block称之为Pending Block。其实现如下：

private static final class PendingTerm extends PendingEntry {
  public final byte[] termBytes;
  public final BlockTermState state;
  public PendingTerm(BytesRef term, BlockTermState state) {...}
  @Override
  public String toString() {...}
}
private static final class PendingBlock extends PendingEntry {
  public final BytesRef prefix; //block前缀的长度（有leading label需要+1）
  public final long fp; //block在tim文件中的起始位置
  public FST<BytesRef> index; //第一个PendingBlock的FSTIndex的二进制对象
  public List<FST<BytesRef>> subIndices;  //PendingBlock中嵌套的PendingBlock集合
  public final boolean hasTerms;  //是否包含至少一个完整的的Term（即"非Block"也就是PendingTerm）
  public final boolean isFloor; //是否是floorBlock，即层级块
  public final int floorLeadByte; //即leading label 如果不是floor block生成的PendingBlock 那么返回-1
  ...
}

在图6-3中，为了方便演示和读者理解，我暂且把DEFAULT_MIN_BLOCK_SIZE和DEFAULT_MAX_BLOCK_SIZE的值分别设置为3和4，即min=3，max=4。图中豆沙色矩形标注的部分即block的entry。

接下来，我们来演示一下Lucene是如何将Term Dictionary构建成为一个FST对象的。

图6-2中当term:abe输入完成之后生成的数据模型如图6-4所示

我们继续上图中的过程，并且以图中左侧的Term Dictionary为例，当第三个term:abfi输入的时候，就意味着以“abe”为前缀的所有term都已经结束，当term:abfj输入，意味着所有以“abfj”为前缀的term结束，以此类推，当输入term:abfk之后，frontier如图6-5所示

图中蓝色边框的节点代表当前节点已执行freezeTail，被冻结的节点将会从frontier中“摘”下来，此时尚无任何节点数据写入current数组，因为虽然有节点被冻结，但是被冻结的节点都没有任何出度，即 lastFrozenNode = -1，此时pending对象中保存的结构如图右侧所示。

输入term:abgl，此时以“abf”为前缀的所有term都已经结束，此时Arc f的target节点S-f就可以确定不再会发生任何变化，即包括其子节点在内都不会再产生新的出度，此时调用writeBlocks方法将S-f生产Block，因为节点S-f的出度节点数量为3，大于等于min值小于max值，因此生成pending block，如图6-6所示：

后面的几步执行过程都是相似的，这里不再赘述，当输入term:abh的时候，节点S-g确定不再发生任何改变，冻结尾部执行writeBlocks生成block。由于S-g的出度包含’l‘、’m‘、’n‘、’o‘、’p‘、’q‘、’r‘，由于所有节点冻结都是从尾部开始的，遵循floor block的规则，生成S-p和S-l两个floor block，并最终生成Block：S-g，此时pending对象中已经包含了两个pending block和三个pending term，如图6-7所示：

接下来的步骤都是相同的道理了，但是当最后一个term:ac输入之后，因为没有下一个term了，因此所有的节点都已经确认，最终生成的结果如下图6-8所示

数据会最终被全完成frontier数组中摘出来生成byte数组保存在current数组中写入磁盘。