2.2 生成索引文件

词表是类似这样的数据结构：SortedMap<Term, Postings>。如果词表很小，内存能够放下，则可以使用折半查找算法来查询一个词对应的文档序列。如果内存不能完全放下倒排索引中的词表，如何利用索引文件查找？理论上，可以采用B树存储词表。为了简化实现，Lucene 3以前的版本使用了跳表。跳表把词组织成固定大小的块，例如每32个词放入一个新的块，然后在块上建立一个索引。记住每个块的开始词在文件中的位置。

但是，更好的分块方式是根据词共享了哪些前缀。按前缀组织词产生的词块大小是变化的。把相同前缀的词放到一起比按顺序放更好，这样在每个区块内，可最大化共享前缀的词，并且减少了产生的词索引。

这样做也可以加速词密集的查询。因为词索引成为了前缀Trie树。如果词典中不包含这个词，可以快速报告：“没有找到。”不需要在查找某一个词块之后才能确定没有。

这种方法叫作BlockTree。例如，词表中包含如下一些词。

        able
        above
        apple
        perfect
        preface
        prefecture
        prefix
        previous
        profit
        programmer
        project
        zoo

把a开头的3个词组织成一个词块：{able, above, apple}。p开头的词有8个，超过4个。把pre开头的4个词组织成一个词块：{ preface, prefecture, prefix , previous }。把pro开头的3个词组织成一个词块：{ profit, programmer, project }。因为以z开头的词只有1个，所以zoo单独组成一个词块。BlockTree索引如图2-3所示。

图2-3 BlockTree索引

根据有限状态转换找到词块在文件中存放的位置，如图2-4所示。

图2-4 有限状态转换

BlockTreeTermsReader类用于读索引。BlockTreeTermsWriter类用于写索引。

对于主键列来说，可以把所有的词和postings一起存到一个FST中。把FST保存到硬盘。

可以利用BlockTree的结构加快排序的速度。