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

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

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

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

隨著Lucene不斷發(fā)展，本文也應(yīng)該更新。不同語言寫成的Lucene實(shí)現(xiàn)版本應(yīng)當(dāng)盡力遵守文件格式，也必須產(chǎn)生本文的新版本。

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

定義

Lucene中最基礎(chǔ)的概念是索引（index），文檔（document），域（field）和項(xiàng)（term）。

索引包含了一個(gè)文檔的序列。

· 文檔是一些域的序列。

· 域是一些項(xiàng)的序列。

· 項(xiàng)就是一個(gè)字串。

存在于不同域中的同一個(gè)字串被認(rèn)為是不同的項(xiàng)。因此項(xiàng)實(shí)際是用一對(duì)字串表示的，第一個(gè)字串是域名，第二個(gè)是域中的字串。

倒排索引

為了使得基于項(xiàng)的搜索更有效率，索引中項(xiàng)是靜態(tài)存儲(chǔ)的。Lucene的索引屬于索引方式中的倒排索引，因?yàn)閷?duì)于一個(gè)項(xiàng)這種索引可以列出包含它的文檔。這剛好是文檔與項(xiàng)自然聯(lián)系的倒置。

域的類型

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

域的文本可能被分解許多項(xiàng)目而被索引，或者就被用作一個(gè)項(xiàng)目而被索引。大多數(shù)的域是被分解過的，但是有些時(shí)候某些標(biāo)識(shí)符域被當(dāng)做一個(gè)項(xiàng)目索引是很有用的。

段（Segment）

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

1. 為新加入的文檔創(chuàng)建新段。

2. 合并已經(jīng)存在的段。

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

文檔號(hào)（Document Number）

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

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

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

· 文檔刪除后，連續(xù)的號(hào)碼就出現(xiàn)了間斷。這可以通過合并索引來解決，段合并時(shí)刪除的文檔相應(yīng)也刪掉了，新合并而成的段并沒有號(hào)碼間斷。

緒論

索引段維護(hù)著以下的信息：

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

· 域值存儲(chǔ)表。每一個(gè)文檔都含有一個(gè)“屬性－值”對(duì)的列表，屬性即為域名。這個(gè)列表用來存儲(chǔ)文檔的一些附加信息，如標(biāo)題，url或者訪問數(shù)據(jù)庫的一個(gè)ID。在搜索時(shí)存儲(chǔ)域的集合可以被返回。這個(gè)表以文檔號(hào)標(biāo)識(shí)。

· 項(xiàng)字典。這個(gè)字典含有所有文檔的所有域中使用過的的項(xiàng)，同時(shí)含有使用過它的文檔的文檔號(hào)，以及指向使用頻數(shù)信息和位置信息的指針。

· 項(xiàng)頻數(shù)信息。對(duì)于項(xiàng)字典中的每個(gè)項(xiàng)，這些信息包含含有這個(gè)項(xiàng)的文檔的總數(shù)，以及每個(gè)文檔中使用的次數(shù)。

· 項(xiàng)位置信息。對(duì)于項(xiàng)字典中的每個(gè)項(xiàng)，都存有在每個(gè)文檔中出現(xiàn)的各個(gè)位置。

· Normalization factors. For each field in each document, a value is stored that is multiplied into the score for hits on that field. 標(biāo)準(zhǔn)化因子。對(duì)于文檔中的每一個(gè)域，存有一個(gè)值，用來以后乘以這個(gè)這個(gè)域的命中數(shù)（hits）。

· 被刪除的文檔信息。這是一個(gè)可選文件，用來表明那些文檔已經(jīng)刪除了。

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

文件的命名（File Naming）

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

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

基本數(shù)據(jù)類型（Primitive Types）

Byte

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

UInt32

32位無符號(hào)整數(shù)，由四個(gè)字節(jié)組成，高位優(yōu)先。

UInt32 --> <Byte>4

Uint64

64位無符號(hào)整數(shù)，由八字節(jié)組成，高位優(yōu)先。

UInt64 --> <Byte>8

VInt

可變長的正整數(shù)類型，每字節(jié)的最高位表明還剩多少字節(jié)。每字節(jié)的低七位表明整數(shù)的值。因此單字節(jié)的值從0到127，兩字節(jié)值從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

...

這種編碼提供了一種在高效率解碼時(shí)壓縮數(shù)據(jù)的方法。

Chars

Lucene輸出UNICODE字符序列，使用標(biāo)準(zhǔn)UTF-8編碼。

String

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

String --> VInt, Chars

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

這部分介紹每個(gè)索引包含的文件。

Segments文件

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

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

SegCount, SegSize --> UInt32

SegName --> String

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

SegSize是段索引中含有的文檔數(shù)。

Lock文件

有一些文件用來表示另一個(gè)進(jìn)程在使用索引。

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

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

Deleteable文件

名為"deletetable"的文件包含了索引不再使用的文件的名字，這些文件可能并沒有被實(shí)際的刪除。這種情況只存在與Win32平臺(tái)下，因?yàn)?/SPAN>Win32下文件仍打開時(shí)并不能刪除。

Deleteable --> DelableCount, <DelableName>DelableCount

DelableCount --> UInt32

DelableName --> String

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

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

域（Field）


域集合信息（Field Info）

所有域名都存儲(chǔ)在這個(gè)文件的域集合信息中，這個(gè)文件以后綴.fnm結(jié)尾。

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

FieldsCount --> VInt

FieldName --> String

FieldBits --> Byte

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

文件中的域根據(jù)它們的次序編號(hào)。因此域0是文件中的第一個(gè)域，域1是接下來的，等等。這個(gè)和文檔號(hào)的編號(hào)方式相同。


域值存儲(chǔ)表（Stored Fields）

域值存儲(chǔ)表使用兩個(gè)文件表示：

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

如下，對(duì)于每個(gè)文檔這個(gè)文件包含指向域值的指針：

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

FieldValuesPosition --> Uint64

FieldValuesPosition指示的是某一文檔的某域的域值在域值文件中的位置。因?yàn)橛蛑滴募卸ㄩL的數(shù)據(jù)信息，因而很容易隨機(jī)訪問。在域值文件中，文檔n的域值信息就存在n*8位置處（The position of document n's field data is the Uint64 at n*8 in this file.）。

2. 域值（.fdt文件）。

如下，每個(gè)文檔的域值信息包含：

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

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

FieldCount --> VInt

FieldNum --> VInt

Bits --> Byte

Value --> String

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

項(xiàng)字典（Term Dictionary）

項(xiàng)字典用以下兩個(gè)文件表示：

1. 項(xiàng)信息（.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

項(xiàng)信息按項(xiàng)排序。項(xiàng)信息排序時(shí)先按項(xiàng)所屬的域的文字順序排序，然后按照項(xiàng)的字串的文字順序排序。

項(xiàng)的字前綴往往是共同的，與字的后綴組成字。PrefixLength變量就是表示與前一項(xiàng)相同的前綴的字?jǐn)?shù)。因此，如果前一個(gè)項(xiàng)的字是"bone"，后一個(gè)是"boy"的話，PrefixLength值為2，Suffix值為"y"。

FieldNum指明了項(xiàng)屬于的域號(hào)，而域名存儲(chǔ)在.fdt文件中。

DocFreg表示的是含有該項(xiàng)的文檔的數(shù)量。

FreqDelta指明了項(xiàng)所屬TermFreq變量在.frq文件中的位置。詳細(xì)的說，就是指相對(duì)于前一個(gè)項(xiàng)的數(shù)據(jù)的位置偏移量（或者是0，表示文件中第一個(gè)項(xiàng)）。

ProxDelta指明了項(xiàng)所屬的TermPosition變量在.prx文件中的位置。詳細(xì)的說，就是指相對(duì)于前一個(gè)項(xiàng)的數(shù)據(jù)的位置偏移量（或者是0，表示文件中第一個(gè)項(xiàng)）。

2. 項(xiàng)信息索引（.tii文件）。

每個(gè)項(xiàng)信息索引文件包含.tis文件中的128個(gè)條目，依照條目在.tis文件中的順序。這樣設(shè)計(jì)是為了一次將索引信息讀入內(nèi)存能，然后使用它來隨機(jī)的訪問.tis文件。

這個(gè)文件的結(jié)構(gòu)和.tis文件非常類似，只在每個(gè)條目記錄上增加了一個(gè)變量IndexDelta。

TermInfoIndex (.tii)--> IndexTermCount, TermIndices

IndexTermCount --> UInt32

TermIndices --> <TermInfo, IndexDelta>IndexTermCount

IndexDelta --> VInt

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

項(xiàng)頻數(shù)（Frequencies）

.frq文件包含每一項(xiàng)的文檔的列表，還有該項(xiàng)在對(duì)應(yīng)文檔中出現(xiàn)的頻數(shù)。

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

TermFreqs --> <TermFreq>DocFreq

TermFreq --> DocDelta, Freq?

DocDelta,Freq --> VInt

TermFreqs序列按照項(xiàng)來排序（依據(jù)于.tis文件中的項(xiàng)，即項(xiàng)是隱含存在的）。

TermFreq元組按照文檔號(hào)升序排列。

DocDelta決定了文檔號(hào)和頻數(shù)。詳細(xì)的說，DocDelta/2表示相對(duì)于前一文檔號(hào)的偏移量（或者是0，表示這是TermFreqs里面的第一項(xiàng)）。當(dāng)DocDelta是奇數(shù)時(shí)表示在該文檔中頻數(shù)為1，當(dāng)DocDelta是偶數(shù)時(shí)，另一個(gè)VInt（Freq）就表示在該文檔中出現(xiàn)的頻數(shù)。

例如，假設(shè)某一項(xiàng)在文檔7中出現(xiàn)一次，在文檔11中出現(xiàn)了3次，在TermFreqs中就存在如下的VInts序列：

15, 22, 3

項(xiàng)位置（Position）

.prx文件包含了某文檔中某項(xiàng)出現(xiàn)的位置信息的列表。

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

TermPositions --> <Positions>DocFreq

Positions --> <PositionDelta>Freq

PositionDelta --> VInt

TermPositions按照項(xiàng)來排序（依據(jù)于.tis文件中的項(xiàng)，即項(xiàng)是隱含存在的）。

Positions元組按照文檔號(hào)升序排列。

PositionDelta是相對(duì)于前一個(gè)出現(xiàn)位置的偏移位置（或者為0，表示這是第一次在這個(gè)文檔中出現(xiàn)）。

例如，假設(shè)某一項(xiàng)在某文檔第4項(xiàng)出現(xiàn)，在另一個(gè)文檔中第5項(xiàng)和第9項(xiàng)出現(xiàn)，將存在如下的VInt序列：

4, 5, 4

標(biāo)準(zhǔn)化因子（Normalization Factor）

.nrm文件包含了每個(gè)文檔的標(biāo)準(zhǔn)化因子，標(biāo)準(zhǔn)化因子用來以后乘以這個(gè)這個(gè)域的命中數(shù)。

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

每個(gè)字節(jié)記錄一個(gè)浮點(diǎn)數(shù)。位0-2包含了3位的尾數(shù)部分，位3-8包含了5位的指數(shù)部分。

按如下規(guī)則可將這些字節(jié)轉(zhuǎn)換為IEEE標(biāo)準(zhǔn)單精度浮點(diǎn)數(shù)：

1. 如果該字節(jié)是0，就是浮點(diǎn)0；

2. 否則，設(shè)置新浮點(diǎn)數(shù)的標(biāo)志位為0；

3. 將字節(jié)中的指數(shù)加上48后作為新的浮點(diǎn)數(shù)的指數(shù)；

4. 將字節(jié)中的尾數(shù)映射到新浮點(diǎn)數(shù)尾數(shù)的高3位；并且

5. 設(shè)置新浮點(diǎn)數(shù)尾數(shù)的低21位為0。

被刪除的文檔（Deleted Document）

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

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

ByteSize,BitCount --> Uint32

Bits --> <Byte>ByteCount

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

BitCount表示Bits列表中多少個(gè)已經(jīng)被設(shè)置過了。

Bits列表包含了一些位（bit），順序表示一個(gè)文檔。當(dāng)對(duì)應(yīng)于文檔號(hào)的位被設(shè)置了，就標(biāo)志著這個(gè)文檔已經(jīng)被刪除了。位的順序是從低到高。因此，如果Bits包含兩個(gè)字節(jié)，0x00和0x02，那么表示文檔9已經(jīng)刪除了。

局限性（Limitations）

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

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

1. FieldValuesPosition變量（存儲(chǔ)于域索引文件中，.fdx文件）。它已經(jīng)是一個(gè)UInt64型，所以不會(huì)有問題。

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

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