2.2 生成索引文件

詞表是類似這樣的數據結構：SortedMap<Term, Postings>。如果詞表很小，內存能夠放下，則可以使用折半查找算法來查詢一個詞對應的文檔序列。如果內存不能完全放下倒排索引中的詞表，如何利用索引文件查找？理論上，可以采用B樹存儲詞表。為了簡化實現，Lucene 3以前的版本使用了跳表。跳表把詞組織成固定大小的塊，例如每32個詞放入一個新的塊，然后在塊上建立一個索引。記住每個塊的開始詞在文件中的位置。

但是，更好的分塊方式是根據詞共享了哪些前綴。按前綴組織詞產生的詞塊大小是變化的。把相同前綴的詞放到一起比按順序放更好，這樣在每個區(qū)塊內，可最大化共享前綴的詞，并且減少了產生的詞索引。

這樣做也可以加速詞密集的查詢。因為詞索引成為了前綴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索引

根據有限狀態(tài)轉換找到詞塊在文件中存放的位置，如圖2-4所示。

圖2-4 有限狀態(tài)轉換

BlockTreeTermsReader類用于讀索引。BlockTreeTermsWriter類用于寫索引。

對于主鍵列來說，可以把所有的詞和postings一起存到一個FST中。把FST保存到硬盤。

可以利用BlockTree的結構加快排序的速度。