注意，本專題內容參見《 http://lucene.apache.org/java/3_0_1/fileformats.html 》

?

深入了解Lucene的磁盤索引文件，可以使我們對IR系統底層數據存儲結構有一個深刻的認識。在《索引文件格式》這一專題中，我們將詳細探討 Lucene 3.0索引數據在磁盤上的存儲格式，并通過一個實例進一步理解這些格式。但首先，我們必須準備點Lucene 索引文件格式的基礎知識。

?

?

?

?

★ Lucene 自定義的基本數據類型

?

【Byte】? 由8 bits組成的基本數據類型。所有其他的數據類型都是一個byte 串。因此，Lucene的索引文件都可以看成是有序的byte 串

【UInt32】 由4 byte 組成的32位無符號整 型 ，高位優先。UInt32 --> <Byte> ⁴

【UInt64】 由8 byte 組成的64位無符號整型，高位優先。 UInt64 --> <Byte> ⁸

【VInt】 可變長整型，為正整數定義的可變長格式。其特殊之處在于： 每字節的最高位表明后面還有一個字節，每字節的低七位表明整數的值，高位優先。 因此 單個字節能表示的整數范圍為0-127，而128到16383必須存儲在兩個字節中。比如下表：

? Value ? ?	First byte?	Second byte	Third byte ?
0	00000000	?	?
1	00000001	?	?
2	00000010	?	?
...	...	...	...
127	01111111	?	?
128	10000000	00000001	?
129	10000001	00000001	?
130	10000010	00000001	?
...	...	...	...
16,383	11111111	01111111	?
16,384	10000000	10000000	00000001
16,385	10000001	10000000	00000001

【Chars】 采用UTF-8編碼的Unicode字符序列

【String】 由VInt 和 Chars組成的字符串類型，其中VInt表示了Chars的長度，Chars表示了String的值。比如：

字符串"name"在Lucene的存儲結構中表示為：4,110,97,109,101。其中4為字符的長度，后面4bytes分別表示四個字 符。

?

?

?

?

?

?

?

★ 空間復雜度的優化 —— Lucene壓縮技術

??? 信息檢索領域中一個非常重要的研究課題就是如何將海量的信息存儲起來。Lucene建立倒排索引結構，需要將詞語、文檔號、詞頻、位置信息寫入磁盤文件。需要檢索的文本越多，信息量就越大。因此Lucene使用了一些數據壓縮技術來盡量減少數據存儲所需要的空間。

?

(1) 前綴規則 Prefix

????? 所謂前綴規則，即當前詞和前一個詞有共同的前綴的時候，當前詞僅僅保存前綴之后的子串。 比如“term terminal”這兩個詞的存儲如下所示， 注意：前綴規則只適用于兩個相鄰的詞。

???????????????????????????????????????????? ? ? t e r m 4? i n a l

????? 我們來看看壓縮的效率：假設有term，termagancy，termagant，termina四個詞。每個字母需要1byte的空間。常規存儲一共需要35byte。而壓縮存儲之后為："term4agancy8t4inal"。一共需要22byte.

?????? Lucene倒排索引文件的Dictionary主要就采用了這種壓縮技術。其效果非常理想，原因就在于Dictionary中的詞語都按照字典序進行排序，兩個相鄰的詞語之間的具有很長的相同前綴。

?

?

( 2) 差值規則(Delta)

????? 所謂差值規則，就是兩個連續存儲的數據，后一個數據存儲的是與前一個數據的差值。 比如"1500000 1500001"這兩個數據的存儲如下所示， 注意：差值規則也必須在兩個連續的存儲數據之間發生。

??????????????????????????????????????????????????? 1500000? 1

????? 很顯然，如果要存儲一個比較大的數據，很有可能需要多個字節的存儲空間。如果存儲與前一個數據的差值，那么很有可能將數據控制在1byte之內。

???? ? Lucene倒排索引文件中frequence、docID、position都采用了這種壓縮技術。其原因就在于這三種信息具有一個相似的特性，就是信息的后一個數據基本上都是前一個數據增1。因此差值總是可以將很大的數用1來存儲。

?

?

(3) 或然跟隨規則

?????? 或然跟隨規則可以在某種特定的情況下將本需要2個空間存儲的數據放在壓縮成1個空間存儲。 比如說某個數據A=1，其后緊跟的一個數據B=1。則可以采用(A<<1) | B 來存儲，過程如下：

?? ??? A=00000001? B=00000001? --->?? (A<<1) | B =00000010 | 00000001=00000011=3

?????? 很顯然，本需要2byte存儲的A和B，現在只需要1byte就可以全部存儲完畢了。

????? ? 但要注意，如果后面跟隨的B>1怎么辦？那么當然不可能將A的最后一個bit來存放B，只能放棄這種規則。但是如何區別使用或然規則壓縮的數據和普通數據呢。只能將A進行左移1位而不與B或運算。

?

????? Lucene中有很多情況符合這種具有一定條件約束的壓縮技術。比如：.frq文件中的DocDelta[, Freq?]、prx文件中的PositionDelta,Payload?等。這些在后面的具體討論中會詳細講到。

?

?

?

?

?

?

?

?

★ 時間復雜度的優化 —— Lucene 的跳表查詢結構(Skip list)

?

??? 對于搜索引擎而言，查找時最主要的操作。為了提高查找的性能，Lucene在很多地方采取的跳躍表的數據結構。

?

??? 跳躍表(Skip List)是如圖的一種數據結構，有以下幾個基本特征：

• 元素是按順序排列的，在Lucene中，或是按字典順序排列，或是按從小到大順序排列。
• 跳躍是有間隔的(Interval)，也即每次跳躍的元素數，間隔是事先配置好的，如圖跳躍表的間隔為3。
• 跳躍表是由層次的(level)，每一層的每隔指定間隔的元素構成上一層，如圖跳躍表共有2層。

?

需要注意一點的是，在很多數據結構或算法書中都會有跳躍表的描述，原理都是大致相同的，但是定義稍有差別：

• 對間隔(Interval)的定義： 如圖中，有的認為間隔為2，即兩個上層元素之間的元素數，不包括兩個上層元素；有的認為是3，即兩個上層元素之間的差，包括后面上層元素，不包括前面的上 層元素；有的認為是4，即除兩個上層元素之間的元素外，既包括前面，也包括后面的上層元素。Lucene是采取的第二種定義。
• 對層次(Level)的定義：如圖中，有的認為應該包括原鏈表層，并從1開始計數，則總層次為3，為1，2，3層；有的認為應該包括原鏈表層，并 從0計數，為0，1，2層；有的認為不應該包括原鏈表層，且從1開始計數，則為1，2層；有的認為不應該包括鏈表層，且從0開始計數，則為0，1層。 Lucene采取的是最后一種定義。

跳躍表比順序查找，大大提高了查找速度，如查找元素72，原來要訪問2，3，7，12，23，37，39，44，50，72總共10個元素，應用跳 躍表后，只要首先訪問第1層的50，發現72大于50，而第1層無下一個節點，然后訪問第2層的94，發現94大于72，然后訪問原鏈表的72，找到元 素，共需要訪問3個元素即可。

【Lucene3.0 初窺】索引文件格式(1)：預備知識