摘自：http://forfuture1978.iteye.com/blog/546841
4.2.2. 文档号及词频(frq)信息
文档号及词频文件里面保存的是倒排表，是以跳跃表形式存在的。
- 此文件包含TermCount个项，每一个词都有一项，因为每一个词都有自己的倒排表。
- 对于每一个词的倒排表都包括两部分，一部分是倒排表本身，也即一个数组的文档号及词频，另一部分是跳跃表，为了更快的访问和定位倒排表中文档号及词频的位置。
- 对于文档号和词频的存储应用的是差值规则和或然跟随规则，Lucene的文档本身有以下几句话，比较难以理解，在此解释一下：
For example, the TermFreqs for a term which occurs once in document seven and three times in document eleven, with omitTf false, would be the following sequence of VInts: 15, 8, 3 If omitTf were true it would be this sequence of VInts instead: 7,4 首先我们看omitTf=false的情况，也即我们在索引中会存储一个文档中term出现的次数。 例子中说了，表示在文档7中出现1次，并且又在文档11中出现3次的文档用以下序列表示：15，8，3. 那这三个数字是怎么计算出来的呢？ 首先，根据定义TermFreq --> DocDelta[, Freq?]，一个TermFreq结构是由一个DocDelta后面或许跟着Freq组成，也即上面我们说的A+B？结构。 DocDelta自然是想存储包含此Term的文档的ID号了，Freq是在此文档中出现的次数。 所以根据例子，应该存储的完整信息为[DocID = 7, Freq = 1] [DocID = 11, Freq = 3](见全文检索的基本原理章节)。 然而为了节省空间，Lucene对编号此类的数据都是用差值来表示的，也即上面说的规则2，Delta规则，于是文档ID就不能按完整信息存了，就应该存放如下： [DocIDDelta = 7, Freq = 1][DocIDDelta = 4 (11-7), Freq = 3] 然而Lucene对于A+B?这种或然跟随的结果，有其特殊的存储方式，见规则3，即A+B?规则，如果DocDelta后面跟随的Freq为1，则用DocDelta最后一位置1表示。 如果DocDelta后面跟随的Freq大于1，则DocDelta得最后一位置0，然后后面跟随真正的值，从而对于第一个Term，由于Freq为1，于是放在DocDelta的最后一位表示，DocIDDelta = 7的二进制是000 0111，必须要左移一位，且最后一位置一，000 1111 = 15，对于第二个Term，由于Freq大于一，于是放在DocDelta的最后一位置零，DocIDDelta = 4的二进制是0000 0100，必须要左移一位，且最后一位置零，0000 1000 = 8，然后后面跟随真正的Freq = 3。 于是得到序列：[DocDleta = 15][DocDelta = 8, Freq = 3]，也即序列，15，8，3。 如果omitTf=true，也即我们不在索引中存储一个文档中Term出现的次数，则只存DocID就可以了，因而不存在A+B?规则的应用。 [DocID = 7][DocID = 11]，然后应用规则2，Delta规则，于是得到序列[DocDelta = 7][DocDelta = 4 (11 - 7)]，也即序列，7，4. |
- 对于跳跃表的存储有以下几点需要解释一下：
- 跳跃表可根据倒排表本身的长度(DocFreq)和跳跃的幅度(SkipInterval)而分不同的层次，层次数为NumSkipLevels = Min(MaxSkipLevels, floor(log(DocFreq/log(SkipInterval)))).
- 第Level层的节点数为DocFreq/(SkipInterval^(Level + 1))，level从零计数。
- 除了最高层之外，其他层都有SkipLevelLength来表示此层的二进制长度(而非节点的个数)，方便读取某一层的跳跃表到缓存里面。
- 低层在前，高层在后，当读完所有的低层后，剩下的就是最后一层，因而最后一层不需要SkipLevelLength。这也是为什么Lucene文档中的格式描述为 NumSkipLevels-1, SkipLevel，也即低NumSKipLevels-1层有SkipLevelLength，最后一层只有SkipLevel，没有SkipLevelLength。
- 除最低层以外，其他层都有SkipChildLevelPointer来指向下一层相应的节点。
- 每一个跳跃节点包含以下信息：文档号，payload的长度，文档号对应的倒排表中的节点在frq中的偏移量，文档号对应的倒排表中的节点在prx中的偏移量。
- 虽然Lucene的文档中有以下的描述，然而实验的结果却不是完全准确的：
Example: SkipInterval = 4, MaxSkipLevels = 2, DocFreq = 35. Then skip level 0 has 8 SkipData entries, containing the 3rd, 7th, 11th, 15th, 19th, 23rd, 27th, and 31st document numbers in TermFreqs. Skip level 1 has 2 SkipData entries, containing the 15th and 31st document numbers in TermFreqs. 按照描述，当SkipInterval为4，且有35篇文档的时候，Skip level = 0应该包括第3，第7，第11，第15，第19，第23，第27，第31篇文档，Skip level = 1应该包括第15，第31篇文档。 然而真正的实现中，跳跃表节点的时候，却向前偏移了，偏移的原因在于下面的代码：
从代码中，我们可以看出，当SkipInterval为4的时候，当docID = 0时，++df为1，1%4不为0，不是跳跃节点，当docID = 3时，++df=4，4%4为0，为跳跃节点，然而skipData里面保存的却是lastDocID为2。 所以真正的倒排表和跳跃表中保存一下的信息： |