原文:http://www.matrix.org.cn/resource/article/34.html

論壇:http://www.matrix.org.cn/topic.shtml?forumId=32
索引文件格式

本文定義了Lucene（版本1.3）用到的索引文件的格式。

Jakarta Lucene是用Java寫成的，同時有很多團體正在默默的用其他的程序語言來改寫它。如果這些新的版本想和Jakarta Lucene兼容，就需要一個與具體語言無關的Lucene索引文件格式。本文正是試圖提供一個完整的與語言無關的Jakarta Lucene 1.3索引文件格式的規格定義。

隨著Lucene不斷發展，本文也應該更新。不同語言寫成的Lucene實現版本應當盡力遵守文件格式，也必須產生本文的新版本。

本文同時提供兼容性批注，描述文件格式上與前一版本不同的地方。

定義

Lucene中最基礎的概念是索引（index），文檔（document），域（field）和項（term）。

索引包含了一個文檔的序列。

· 文檔是一些域的序列。

· 域是一些項的序列。

· 項就是一個字串。

存在于不同域中的同一個字串被認為是不同的項。因此項實際是用一對字串表示的，第一個字串是域名，第二個是域中的字串。

倒排索引

為了使得基于項的搜索更有效率，索引中項是靜態存儲的。Lucene的索引屬于索引方式中的倒排索引，因為對于一個項這種索引可以列出包含它的文檔。這剛好是文檔與項自然聯系的倒置。

域的類型

Lucene中，域的文本可能以逐字的非倒排的方式存儲在索引中。而倒排過的域稱為被索引過了。域也可能同時被存儲和被索引。

域的文本可能被分解許多項目而被索引，或者就被用作一個項目而被索引。大多數的域是被分解過的，但是有些時候某些標識符域被當做一個項目索引是很有用的。

段（Segment）

Lucene索引可能由多個子索引組成，這些子索引成為段。每一段都是完整獨立的索引，能被搜索。索引是這樣作成的：

1. 為新加入的文檔創建新段。

2. 合并已經存在的段。

搜索時需要涉及到多個段和/或者多個索引，每一個索引又可能由一些段組成。

文檔號（Document Number）

內部的來說，Lucene用一個整形（interger）的文檔號來指示文檔。第一個被加入到索引中的文檔就是0號，順序加入的文檔將得到一個由前一個號碼遞增而來的號碼。

注意文檔號是可能改變的，所以在Lucene外部存儲這些號碼時必須小心。特別的，號碼的改變的情況如下：

· 只有段內的號碼是相同的，不同段之間不同，因而在一個比段廣泛的上下文環境中使用這些號碼時，就必須改變它們。標準的技術是根據每一段號碼多少為每一段分配一個段號。將段內文檔號轉換到段外時，加上段號。將某段外的文檔號轉換到段內時，根據每段中可能的轉換后號碼范圍來判斷文檔屬于那一段，并減調這一段的段號。例如有兩個含5個文檔的段合并，那么第一段的段號就是0，第二段段號5。第二段中的第三個文檔，在段外的號碼就是8。

· 文檔刪除后，連續的號碼就出現了間斷。這可以通過合并索引來解決，段合并時刪除的文檔相應也刪掉了，新合并而成的段并沒有號碼間斷。

緒論

索引段維護著以下的信息：

· 域集合。包含了索引中用到的所有的域。

· 域值存儲表。每一個文檔都含有一個“屬性－值”對的列表，屬性即為域名。這個列表用來存儲文檔的一些附加信息，如標題，url或者訪問數據庫的一個ID。在搜索時存儲域的集合可以被返回。這個表以文檔號標識。

· 項字典。這個字典含有所有文檔的所有域中使用過的的項，同時含有使用過它的文檔的文檔號，以及指向使用頻數信息和位置信息的指針。

· 項頻數信息。對于項字典中的每個項，這些信息包含含有這個項的文檔的總數，以及每個文檔中使用的次數。

· 項位置信息。對于項字典中的每個項，都存有在每個文檔中出現的各個位置。

· Normalization factors. For each field in each document, a value is stored that is multiplied into the score for hits on that field. 標準化因子。對于文檔中的每一個域，存有一個值，用來以后乘以這個這個域的命中數（hits）。

· 被刪除的文檔信息。這是一個可選文件，用來表明那些文檔已經刪除了。

接下來的各部分部分詳細描述這些信息。

文件的命名（File Naming）

同屬于一個段的文件擁有相同的文件名，不同的擴展名。擴展名由以下討論的各種文件格式確定。

一般來說，一個索引存放一個目錄，其所有段都存放在這個目錄里，盡管我們不要求您這樣做。

基本數據類型（Primitive Types）

Byte

最基本的數據類型就是字節（byte，8位）。文件就是按字節順序訪問的。其它的一些數據類型也定義為字節的序列，文件的格式具有字節意義上的獨立性。

UInt32

32位無符號整數，由四個字節組成，高位優先。

UInt32 --> <Byte>4

Uint64

64位無符號整數，由八字節組成，高位優先。

UInt64 --> <Byte>8

VInt

可變長的正整數類型，每字節的最高位表明還剩多少字節。每字節的低七位表明整數的值。因此單字節的值從0到127，兩字節值從128到16,383，等等。

VInt 編碼示例

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

Lucene輸出UNICODE字符序列，使用標準UTF-8編碼。

String

Lucene輸出由VINT和字符串組成的字串，VINT表示字串長，字符串緊接其后。

String --> VInt, Chars

索引包含的文件（Per-Index Files）

這部分介紹每個索引包含的文件。

Segments文件

索引中活動的段存儲在Segments文件中。每個索引只能含有一個這樣的文件，名為"segments".這個文件依次列出每個段的名字和每個段的大小。

Segments --> SegCount, <SegName, SegSize>SegCount

SegCount, SegSize --> UInt32

SegName --> String

SegName表示該segment的名字，同時作為索引其他文件的前綴。

SegSize是段索引中含有的文檔數。

Lock文件

有一些文件用來表示另一個進程在使用索引。

· 如果存在"commit.lock"文件，表示有進程在寫"segments"文件和刪除無用的段索引文件，或者表示有進程在讀"segments"文件和打開某些段的文件。在一個進程在讀取"segments"文件段信息后，還沒來得及打開所有該段的文件前，這個Lock文件可以防止另一個進程刪除這些文件。

· 如果存在"index.lock"文件，表示有進程在向索引中加入文檔，或者是從索引中刪除文檔。這個文件防止很多文件同時修改一個索引。

Deleteable文件

名為"deletetable"的文件包含了索引不再使用的文件的名字，這些文件可能并沒有被實際的刪除。這種情況只存在與Win32平臺下，因為Win32下文件仍打開時并不能刪除。

Deleteable --> DelableCount, <DelableName>DelableCount

DelableCount --> UInt32

DelableName --> String

段包含的文件（Per-Segment Files）

剩下的文件是每段中包含的文件，因此由后綴來區分。

域（Field）


域集合信息（Field Info）

所有域名都存儲在這個文件的域集合信息中，這個文件以后綴.fnm結尾。

FieldInfos (.fnm) --> FieldsCount, <FieldName, FieldBits>FieldsCount

FieldsCount --> VInt

FieldName --> String

FieldBits --> Byte

目前情況下，FieldBits只有使用低位，對于已索引的域值為1，對未索引的域值為0。

文件中的域根據它們的次序編號。因此域0是文件中的第一個域，域1是接下來的，等等。這個和文檔號的編號方式相同。


域值存儲表（Stored Fields）

域值存儲表使用兩個文件表示：

1. 域索引（.fdx文件）。

如下，對于每個文檔這個文件包含指向域值的指針：

FieldIndex (.fdx) --> <FieldValuesPosition>SegSize

FieldValuesPosition --> Uint64

FieldValuesPosition指示的是某一文檔的某域的域值在域值文件中的位置。因為域值文件含有定長的數據信息，因而很容易隨機訪問。在域值文件中，文檔n的域值信息就存在n*8位置處（The position of document n's field data is the Uint64 at n*8 in this file.）。

2. 域值（.fdt文件）。

如下，每個文檔的域值信息包含：

FieldData (.fdt) --> <DocFieldData>SegSize

DocFieldData --> FieldCount, <FieldNum, Bits, Value>FieldCount

FieldCount --> VInt

FieldNum --> VInt

Bits --> Byte

Value --> String

目前情況下，Bits只有低位被使用，值為1表示域名被分解過，值為0表示未分解過。

項字典（Term Dictionary）

項字典用以下兩個文件表示：

1. 項信息（.tis文件）。

TermInfoFile (.tis)--> TermCount, TermInfos

TermCount --> UInt32

TermInfos --> <TermInfo>TermCount

TermInfo --> <Term, DocFreq, FreqDelta, ProxDelta>

Term --> <PrefixLength, Suffix, FieldNum>

Suffix --> String

PrefixLength, DocFreq, FreqDelta, ProxDelta
--> VInt

項信息按項排序。項信息排序時先按項所屬的域的文字順序排序，然后按照項的字串的文字順序排序。

項的字前綴往往是共同的，與字的后綴組成字。PrefixLength變量就是表示與前一項相同的前綴的字數。因此，如果前一個項的字是"bone"，后一個是"boy"的話，PrefixLength值為2，Suffix值為"y"。

FieldNum指明了項屬于的域號，而域名存儲在.fdt文件中。

DocFreg表示的是含有該項的文檔的數量。

FreqDelta指明了項所屬TermFreq變量在.frq文件中的位置。詳細的說，就是指相對于前一個項的數據的位置偏移量（或者是0，表示文件中第一個項）。

ProxDelta指明了項所屬的TermPosition變量在.prx文件中的位置。詳細的說，就是指相對于前一個項的數據的位置偏移量（或者是0，表示文件中第一個項）。

2. 項信息索引（.tii文件）。

每個項信息索引文件包含.tis文件中的128個條目，依照條目在.tis文件中的順序。這樣設計是為了一次將索引信息讀入內存能，然后使用它來隨機的訪問.tis文件。

這個文件的結構和.tis文件非常類似，只在每個條目記錄上增加了一個變量IndexDelta。

TermInfoIndex (.tii)--> IndexTermCount, TermIndices

IndexTermCount --> UInt32

TermIndices --> <TermInfo, IndexDelta>IndexTermCount

IndexDelta --> VInt

IndexDelta表示該項的TermInfo變量值在.tis文件中的位置。詳細的講，就是指相對于前一個條目的偏移量（或者是0，對于文件中第一個項）。

項頻數（Frequencies）

.frq文件包含每一項的文檔的列表，還有該項在對應文檔中出現的頻數。

FreqFile (.frq) --> <TermFreqs>TermCount

TermFreqs --> <TermFreq>DocFreq

TermFreq --> DocDelta, Freq?

DocDelta,Freq --> VInt

TermFreqs序列按照項來排序（依據于.tis文件中的項，即項是隱含存在的）。

TermFreq元組按照文檔號升序排列。

DocDelta決定了文檔號和頻數。詳細的說，DocDelta/2表示相對于前一文檔號的偏移量（或者是0，表示這是TermFreqs里面的第一項）。當DocDelta是奇數時表示在該文檔中頻數為1，當DocDelta是偶數時，另一個VInt（Freq）就表示在該文檔中出現的頻數。

例如，假設某一項在文檔7中出現一次，在文檔11中出現了3次，在TermFreqs中就存在如下的VInts序列：

15, 22, 3

項位置（Position）

.prx文件包含了某文檔中某項出現的位置信息的列表。

ProxFile (.prx) --> <TermPositions>TermCount

TermPositions --> <Positions>DocFreq

Positions --> <PositionDelta>Freq

PositionDelta --> VInt

TermPositions按照項來排序（依據于.tis文件中的項，即項是隱含存在的）。

Positions元組按照文檔號升序排列。

PositionDelta是相對于前一個出現位置的偏移位置（或者為0，表示這是第一次在這個文檔中出現）。

例如，假設某一項在某文檔第4項出現，在另一個文檔中第5項和第9項出現，將存在如下的VInt序列：

4, 5, 4

標準化因子（Normalization Factor）

.nrm文件包含了每個文檔的標準化因子，標準化因子用來以后乘以這個這個域的命中數。

Norms (.nrm) --> <Byte>SegSize

每個字節記錄一個浮點數。位0-2包含了3位的尾數部分，位3-8包含了5位的指數部分。

按如下規則可將這些字節轉換為IEEE標準單精度浮點數：

1. 如果該字節是0，就是浮點0；

2. 否則，設置新浮點數的標志位為0；

3. 將字節中的指數加上48后作為新的浮點數的指數；

4. 將字節中的尾數映射到新浮點數尾數的高3位；并且

5. 設置新浮點數尾數的低21位為0。

被刪除的文檔（Deleted Document）

.del文件是可選的，只有在某段中存在刪除操作后才存在：

Deletions (.del) --> ByteCount,BitCount,Bits

ByteSize,BitCount --> Uint32

Bits --> <Byte>ByteCount

ByteCount表示的是Bits列表中Byte的數量。典型的，它等于（SegSize/8）+1。

BitCount表示Bits列表中多少個已經被設置過了。

Bits列表包含了一些位（bit），順序表示一個文檔。當對應于文檔號的位被設置了，就標志著這個文檔已經被刪除了。位的順序是從低到高。因此，如果Bits包含兩個字節，0x00和0x02，那么表示文檔9已經刪除了。

局限性（Limitations）

在以上的文件格式中，好幾處都有限制項和文檔的最大個數為32位數的極限，即接近于40億。今天看來，這不會造成問題，但是，長遠的看，可能造成問題。因此，這些極限應該或者換為UInt64類型的值，或者更好的，換為VInt類型的值（VInt值沒有上限）。

有兩處地方的代碼要求必須是定長的值，他們是：

1. FieldValuesPosition變量（存儲于域索引文件中，.fdx文件）。它已經是一個UInt64型，所以不會有問題。

2. TermCount變量（存儲于項信息文件中，.tis文件）。這是最后輸出到文件中的，但是最先被讀取，因此是存儲于文件的最前端 。索引代碼先在這里寫入一個0值，然后在其他文件輸出完畢后覆蓋這個值。所以無論它存儲在什么地方，它都必須是一個定長的值，它應該被變成UInt64型。

除此之外，所有的UInt值都可以換成VInt型以去掉限制。