1、索引總體結(jié)構(gòu)

1.1盏求、索引層次結(jié)構(gòu)

Lucene的索引結(jié)構(gòu)主要分以下幾個(gè)層次：

索引結(jié)構(gòu).png

• 索引(Index)：

在Lucene中一個(gè)索引是放在一個(gè)文件夾中的扼劈。同一文件夾中的所有的文件構(gòu)成一個(gè)Lucene索引。

• 段(Segment)：

一個(gè)索引可以包含多個(gè)段框产，段與段之間是獨(dú)立的，添加新文檔可以生成新的段错洁，不同的段可以合并秉宿。具有相同前綴文件的屬同一個(gè)段。

• 文檔(Document)：

文檔是我們建索引的基本單位屯碴，不同的文檔是保存在不同的段中的描睦，一個(gè)段可以包含多篇文檔。新添加的文檔是單獨(dú)保存在一個(gè)新生成的段中导而，隨著段的合并忱叭，不同的文檔合并到同一個(gè)段中。

• 域(Field)：

一篇文檔包含不同類型的信息今艺，可以分開(kāi)索引韵丑，比如標(biāo)題，時(shí)間虚缎，正文撵彻，作者等，都可以保存在不同的域里。不同域的索引方式可以不同千康。

• 詞(Term)：

詞是索引的最小單位享幽，是經(jīng)過(guò)詞法分析和語(yǔ)言處理后的字符串。

1.2拾弃、索引文件結(jié)構(gòu)

索引文件結(jié)構(gòu).png

1.3值桩、索引文件說(shuō)明

2蝌以、索引數(shù)據(jù)類型

Lucene索引文件中炕舵，用一下基本類型來(lái)保存信息：

• Byte：是最基本的類型，長(zhǎng)8位(bit)跟畅。

• UInt32：由4個(gè)Byte組成咽筋。

• UInt64：由8個(gè)Byte組成。

• VInt：

• 變長(zhǎng)的整數(shù)類型徊件，它可能包含多個(gè)Byte奸攻，對(duì)于每個(gè)Byte的8位，其中后7位表示數(shù)值虱痕，最高1位表示是否還有另一個(gè)Byte睹耐，0表示沒(méi)有，1表示有部翘。

• 越前面的Byte表示數(shù)值的低位疏橄，越后面的Byte表示數(shù)值的高位。

• 例如130化為二進(jìn)制為 1000, 0010略就，總共需要8位，一個(gè)Byte表示不了晃酒，因而需要兩個(gè)Byte來(lái)表示表牢，第一個(gè)Byte表示后7位，并且在最高位置1來(lái)表示后面還有一個(gè)Byte贝次，所以為(1) 0000010崔兴，第二個(gè)Byte表示第8位，并且最高位置0來(lái)表示后面沒(méi)有其他的Byte了，所以為(0) 0000001敲茄。

編碼.jpeg

• Chars：是UTF-8編碼的一系列Byte位谋。
• String：一個(gè)字符串首先是一個(gè)VInt來(lái)表示此字符串包含的字符的個(gè)數(shù)，接著便是UTF-8編碼的字符序列Chars堰燎。

3掏父、索引數(shù)據(jù)編碼規(guī)則及數(shù)據(jù)結(jié)構(gòu)

Lucene為了使的信息的存儲(chǔ)占用的空間更小，訪問(wèn)速度更快秆剪，采取了一些特殊的技巧赊淑。

3.1、 前綴后綴規(guī)則(Prefix+Suffix)

Lucene在反向索引中仅讽，要保存詞典(Term Dictionary)的信息陶缺，所有的詞(Term)在詞典中是按照字典順序進(jìn)行排列的，然而詞典中包含了文檔中的幾乎所有的詞洁灵，并且有的詞還是非常的長(zhǎng)的饱岸，這樣索引文件會(huì)非常的大，所謂前綴后綴規(guī)則徽千，即當(dāng)某個(gè)詞和前一個(gè)詞有共同的前綴的時(shí)候苫费，后面的詞僅僅保存前綴在詞中的偏移(offset)，以及除前綴以外的字符串(稱為后綴)罐栈。

term.jpeg

比如要存儲(chǔ)如下詞:term黍衙，termagancy，termagant荠诬，terminal琅翻，

如果按照正常方式來(lái)存儲(chǔ)，需要的空間如下：

[VInt = 4] [t][e][r][m]柑贞，[VInt = 10][t][e][r][m][a][g][a][n][c][y]方椎，[VInt = 9][t][e][r][m][a][g][a][n][t]，[VInt = 8][t][e][r][m][i][n][a][l]

共需要35個(gè)Byte.

如果應(yīng)用前綴后綴規(guī)則钧嘶，需要的空間如下：

[VInt = 4] [t][e][r][m]棠众，[VInt = 4 (offset)][VInt = 6][a][g][a][n][c][y]，[VInt = 8 (offset)][VInt = 1][t]有决，[VInt = 4(offset)][VInt = 4][i][n][a][l]

共需要22個(gè)Byte闸拿。

大大縮小了存儲(chǔ)空間，尤其是在按字典順序排序的情況下书幕，前綴的重合率大大提高新荤。

3.2、 差值規(guī)則(Delta)

在Lucene的反向索引中台汇，需要保存很多整型數(shù)字的信息苛骨，比如文檔ID號(hào)篱瞎，比如詞(Term)在文檔中的位置等等。

由上面介紹痒芝，我們知道俐筋，整型數(shù)字是以VInt的格式存儲(chǔ)的。隨著數(shù)值的增大严衬，每個(gè)數(shù)字占用的Byte的個(gè)數(shù)也逐漸的增多澄者。所謂差值規(guī)則(Delta)就是先后保存兩個(gè)整數(shù)的時(shí)候，后面的整數(shù)僅僅保存和前面整數(shù)的差即可瞳步。

存儲(chǔ).jpeg

比如要存儲(chǔ)如下整數(shù)：16386闷哆，16387，16388单起，16389

如果按照正常方式來(lái)存儲(chǔ)抱怔，需要的空間如下：

[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001]，[(1) 000, 0011][(1) 000, 0000][(0) 000, 0001]嘀倒，[(1) 000, 0100][(1) 000, 0000][(0) 000, 0001]屈留，[(1) 000, 0101][(1) 000, 0000][(0) 000, 0001]

供需12個(gè)Byte。

如果應(yīng)用差值規(guī)則來(lái)存儲(chǔ)测蘑，需要的空間如下：

[(1) 000, 0010][(1) 000, 0000][(0) 000, 0001]灌危，[(0) 000, 0001]，[(0) 000, 0001]碳胳，[(0) 000, 0001]

共需6個(gè)Byte勇蝙。

大大縮小了存儲(chǔ)空間，而且無(wú)論是文檔ID挨约，還是詞在文檔中的位置味混，都是按從小到大的順序，逐漸增大的诫惭。

3.3翁锡、 或然跟隨規(guī)則(A, B?)

Lucene的索引結(jié)構(gòu)中存在這樣的情況，某個(gè)值A(chǔ)后面可能存在某個(gè)值B夕土，也可能不存在馆衔，需要一個(gè)標(biāo)志來(lái)表示后面是否跟隨著B(niǎo)。

一般的情況下怨绣，在A后面放置一個(gè)Byte角溃，為0則后面不存在B，為1則后面存在B篮撑，或者0則后面存在B开镣，1則后面不存在B。

但這樣要浪費(fèi)一個(gè)Byte的空間咽扇，其實(shí)一個(gè)Bit就可以了邪财。

在Lucene中，采取以下的方式：A的值左移一位质欲，空出最后一位树埠，作為標(biāo)志位，來(lái)表示后面是否跟隨B嘶伟，所以在這種情況下怎憋，A/2是真正的A原來(lái)的值。

A值.jpeg

如果去讀Apache Lucene - Index File Formats這篇文章九昧，會(huì)發(fā)現(xiàn)很多符合這種規(guī)則的：

• .frq文件中的DocDelta[, Freq?]绊袋，DocSkip,PayloadLength?
• .prx文件中的PositionDelta,Payload? (但不完全是，如下表分析)

當(dāng)然還有一些帶?的但不屬于此規(guī)則的：

• .frq文件中的SkipChildLevelPointer?铸鹰，是多層跳躍表中癌别，指向下一層表的指針，當(dāng)然如果是最后一層蹋笼，此值就不存在展姐，也不需要標(biāo)志。

• .tvf文件中的Positions?, Offsets?剖毯。

• 在此類情況下圾笨，帶?的值是否存在，并不取決于前面的值的最后一位逊谋。

• 而是取決于Lucene的某項(xiàng)配置擂达，當(dāng)然這些配置也是保存在Lucene索引文件中的。

• 如Position和Offset是否存儲(chǔ)胶滋，取決于.fnm文件中對(duì)于每個(gè)域的配置(TermVector.WITH_POSITIONS和TermVector.WITH_OFFSETS)

為什么會(huì)存在以上兩種情況板鬓，其實(shí)是可以理解的：

• 對(duì)于符合或然跟隨規(guī)則的，是因?yàn)閷?duì)于每一個(gè)A镀钓，B是否存在都不相同穗熬，當(dāng)這種情況大量存在的時(shí)候，從一個(gè)Byte到一個(gè)Bit如此8倍的空間節(jié)約還是很值得的丁溅。
• 對(duì)于不符合或然跟隨規(guī)則的唤蔗，是因?yàn)槟硞€(gè)值的是否存在的配置對(duì)于整個(gè)域(Field)甚至整個(gè)索引都是有效的教沾，而非每次的情況都不相同宴霸，因而可以統(tǒng)一存放一個(gè)標(biāo)志。

3.4赂鲤、跳躍表規(guī)則(Skip list)

為了提高查找的性能涯穷，Lucene在很多地方采取的跳躍表的數(shù)據(jù)結(jié)構(gòu)棍掐。

跳躍表(Skip List)是如圖的一種數(shù)據(jù)結(jié)構(gòu)，有以下幾個(gè)基本特征：

• 元素是按順序排列的拷况，在Lucene中作煌，或是按字典順序排列掘殴，或是按從小到大順序排列。
• 跳躍是有間隔的(Interval)粟誓，也即每次跳躍的元素?cái)?shù)奏寨，間隔是事先配置好的，如圖跳躍表的間隔為3鹰服。
• 跳躍表是由層次的(level)病瞳，每一層的每隔指定間隔的元素構(gòu)成上一層，如圖跳躍表共有2層悲酷。

跳躍表.jpeg

需要注意一點(diǎn)的是套菜，在很多數(shù)據(jù)結(jié)構(gòu)或算法書(shū)中都會(huì)有跳躍表的描述，原理都是大致相同的设易，但是定義稍有差別：

• 對(duì)間隔(Interval)的定義： 如圖中逗柴，有的認(rèn)為間隔為2，即兩個(gè)上層元素之間的元素?cái)?shù)亡嫌，不包括兩個(gè)上層元素嚎于；有的認(rèn)為是3，即兩個(gè)上層元素之間的差挟冠，包括后面上層元素于购，不包括前面的上層元素；有的認(rèn)為是4知染，即除兩個(gè)上層元素之間的元素外肋僧，既包括前面，也包括后面的上層元素控淡。Lucene是采取的第二種定義嫌吠。
• 對(duì)層次(Level)的定義：如圖中，有的認(rèn)為應(yīng)該包括原鏈表層掺炭，并從1開(kāi)始計(jì)數(shù)辫诅，則總層次為3，為1涧狮，2炕矮，3層；有的認(rèn)為應(yīng)該包括原鏈表層者冤，并從0計(jì)數(shù)肤视，為0，1涉枫，2層邢滑；有的認(rèn)為不應(yīng)該包括原鏈表層，且從1開(kāi)始計(jì)數(shù)愿汰，則為1困后，2層乐纸；有的認(rèn)為不應(yīng)該包括鏈表層，且從0開(kāi)始計(jì)數(shù)操灿，則為0锯仪，1層。Lucene采取的是最后一種定義趾盐。

跳躍表比順序查找，大大提高了查找速度小腊，如查找元素72救鲤，原來(lái)要訪問(wèn)2，3秩冈，7本缠，12，23入问，37丹锹，39，44芬失，50楣黍，72總共10個(gè)元素，應(yīng)用跳躍表后棱烂，只要首先訪問(wèn)第1層的50租漂，發(fā)現(xiàn)72大于50，而第1層無(wú)下一個(gè)節(jié)點(diǎn)颊糜，然后訪問(wèn)第2層的94哩治，發(fā)現(xiàn)94大于72，然后訪問(wèn)原鏈表的72衬鱼，找到元素业筏，共需要訪問(wèn)3個(gè)元素即可。

然而Lucene在具體實(shí)現(xiàn)上鸟赫，與理論又有所不同蒜胖，在具體的格式中，會(huì)詳細(xì)說(shuō)明惯疙。

4翠勉、索引構(gòu)建的數(shù)據(jù)流邏輯

索引數(shù)據(jù)流邏輯.png

5、Segments文件

Lucene的索引可以由多個(gè)復(fù)合的子索引或者片斷組成霉颠。每一個(gè)segment都是一個(gè)完全獨(dú)立的索引对碌，它能夠被分離地進(jìn)行檢索。當(dāng)新添加文檔時(shí)蒿偎，會(huì)創(chuàng)建新的段文件朽们；當(dāng)段文件比較多時(shí)怀读，會(huì)合并小的段文件為大的段文件；檢索可以涉及多個(gè)復(fù)合的segments骑脱，或者多個(gè)復(fù)合的indexes菜枷。每一個(gè)index潛在地包含多個(gè)segments。

5.1叁丧、segment.gen文件格式

segments.gen文件包含了該索引中當(dāng)前生成的代（segments_N中的_N）啤誊。這個(gè)文件僅用于一個(gè)后退處理以防止當(dāng)前代不能被準(zhǔn)確地通過(guò)單獨(dú)地目錄文件列舉來(lái)確定（由于某些NFS客戶端因?yàn)榛跁r(shí)間的目錄的緩存終止而引起）。

segmentN.jpeg

5.2拥娄、segment_N文件格式

Lucene查找segment_N流程：

• 在所有的segments_N中選擇N最大的一個(gè)蚊锹。并將其作為genA。
• 打開(kāi)segments.gen稚瘾，其中保存了當(dāng)前的N值牡昆。讀出版本號(hào)(Version)，然后再讀出兩個(gè)N摊欠，如果兩者相等丢烘，則作為genB。
• 在上述得到的genA和genB中選擇最大的那個(gè)作為當(dāng)前的N些椒，打開(kāi)segments_N文件播瞳。

segmentN文件格式.png

其中N作為后綴，是36進(jìn)制的數(shù)字摊沉，segments_N里通過(guò)SegName記錄了這索引里所有.si文件名狐史。

segment_N格式說(shuō)明：

• Header（IndexHeader）：可編解碼的索引頭，記錄索引文件格式说墨，版本號(hào)骏全，文件實(shí)例Id等。
• LuceneVersion（VInt）：記錄提交時(shí)的Lucene代碼版本尼斧，由3個(gè)VInt組成：major姜贡，minor，bugfix棺棵；
• Version（Int64）：索引被修改的計(jì)數(shù)楼咳；
• NameCounter（Int32）：用于新的段文件名字的生成；
• SegCount（Int32）：段文件個(gè)數(shù)計(jì)數(shù)烛恤；
• MinSegmentLuceneVersion（VInt）：記錄提交時(shí)最老的Lucene版本母怜，由3個(gè)VInt組成：major，minor缚柏，bugfix苹熏；索引中有多個(gè)段時(shí)記錄此字段；
• [SegmentCommitInfo]：保存段提交信息；
• CommitUserData（Map<String轨域，String>）：存儲(chǔ)用戶提供的可選數(shù)據(jù)袱耽；
• Footer（CodecFooter）：可編解碼的索引腳，記錄校驗(yàn)算法的id及校驗(yàn)結(jié)果值干发；

[SegmentCommitInfo]格式說(shuō)明：

• SegName：段的名稱朱巨，同時(shí)也是構(gòu)成這個(gè)段索引的所有文件的名稱前綴；
• SegID：編解碼此段對(duì)應(yīng)的編解碼的id枉长；
• SegCodec：編解碼此段的編解碼器的名稱冀续；
• DelGen：刪除文件的分代年齡計(jì)數(shù)，如果為-1則表示無(wú)刪除的文件必峰；
• DeletionCount：記錄當(dāng)前段刪除的文檔數(shù)沥阳；
• FieldInfosGen：fieldInfos 文件的分代計(jì)數(shù)；
• DocValuesGen：可更新的DocValues的分代計(jì)數(shù)自点；
• UpdateFiles：記錄當(dāng)前段每個(gè)域更新的文件集合；

5.3脉让、si格式：

si文件格式.png

segmentInfo文件桂敛，就是一個(gè)獨(dú)立的子索引，其中Files是一個(gè)列表溅潜，里面存儲(chǔ)了本segment所有相關(guān)的索引文件术唬。

Lucene70SegmentInfoFormat格式說(shuō)明：

• Header（IndexHeader）：可編解碼的索引頭，記錄索引文件格式滚澜，版本號(hào)粗仓，文件實(shí)例Id等。
• SegVersion（String）：創(chuàng)建當(dāng)前段的代碼版本设捐；
• SegSize（Int32）：此段索引包含的文件數(shù)量借浊；
• IsCompoundFile（Int8）：記錄當(dāng)前段是非被寫(xiě)入混合的文件中；
• Diagnostics（Map<String,String>）:IndexWriter寫(xiě)入的私有信息萝招，可用于debug蚂斤，其包括lucene版本，OS信息槐沼，java版本等待曙蒸；
• Files（Set<String>）:當(dāng)前段相關(guān)的文件的集合；
• Attributes（Map<String,String>）:
• IndexSort（Int32）：
• Footer（CodecFooter）：

6岗钩、Compound文件格式

從Lucene 1.4版本開(kāi)始纽窟，compound文件格式成為缺省信息。這是一個(gè)簡(jiǎn)單的容器兼吓，其服務(wù)所有除delete文件外的文件臂港。

6.1、cfs文件格式

此文件為可選的虛擬文件，其包含了其他所有的索引文件趋艘，其主要是為某些文件句柄耗盡的系統(tǒng)使用疲恢。

scf文件格式.png

FileData（raw file data）：文件數(shù)據(jù)；

6.2瓷胧、cfe文件格式

cfe文件格式.png

FileCount（VInt）：標(biāo)識(shí)當(dāng)前的cfs混合文件包含的文件個(gè)數(shù)显拳；

FileName（String）：文件名

DataOffset（UInt64）：數(shù)據(jù)偏移；

DataLength（UInt64）：文件大写晗簟杂数；

7、Fild相關(guān)文件

7.1瘸洛、域名稱格式(.fnm)

fnm文件格式.png

存儲(chǔ)了Document所包含的FieldName以及Field的內(nèi)部表示FieldNumber（可以理解為ID）揍移。 同時(shí)，每個(gè)Field相關(guān)索引配置反肋，都通過(guò)byte來(lái)存儲(chǔ)保存下來(lái)那伐。其中DocValueBits里，不同類型的Field, 處理DocValue數(shù)據(jù)是不一樣的石蔗。

Lucene50FieldInfosFormat格式說(shuō)明：

• Header（IndexHeader）：頭部標(biāo)識(shí)罕邀；
• FieldsCount （VInt）：文件中存儲(chǔ)測(cè)域個(gè)數(shù)；
• FieldName （String）：UTF-8格式的Field的名稱养距；
• FieldNumber （VInt）：field的編號(hào)诉探；
• FieldBits（Byte）：一系列標(biāo)志位，表明對(duì)此域的索引方式棍厌；
• IndexOptions（Byte）：一系列標(biāo)志位肾胯，表明對(duì)此域的索引方式；
• DocValuesBits （Byte）：存儲(chǔ)每個(gè)文檔的值包含的類型耘纱；
• DocValuesGen （Int64）：保存DocValues的分代計(jì)數(shù)敬肚；
• Attributes （Map<String,String>）：編解碼相關(guān)的私有數(shù)據(jù)；
• Footer（CodecFooter）：尾部標(biāo)識(shí)揣炕；

7.2帘皿、域數(shù)據(jù)相關(guān)信息（.fdx .fdt）

Lucene50StoredFieldsFormat通過(guò)壓縮文檔塊以提高文檔的壓縮比，其壓縮算法為L(zhǎng)Z4畸陡，每個(gè)壓縮塊為16KB鹰溜，LZ4壓縮算法的壓縮及解壓速度都很快。當(dāng)壓縮配置選項(xiàng)為：BEST_SPEED丁恭，使用LZ4壓縮算法曹动，此算法更注重的壓縮速度；當(dāng)壓縮配置為：BEST_COMPRESSION牲览，使用DEFLATE（同ZIP）壓縮算法墓陈，其更注重?cái)?shù)據(jù)壓縮比。

域數(shù)據(jù)文件（fdt）：

文件保存文檔的壓縮數(shù)據(jù)，每個(gè)壓縮塊為16KB或更大贡必。當(dāng)數(shù)據(jù)寫(xiě)入段時(shí)兔港，文檔就會(huì)被擴(kuò)充到內(nèi)存緩沖區(qū)中，當(dāng)緩沖區(qū)大小大于16KB時(shí)仔拟，文檔相關(guān)的配置信息會(huì)被刷寫(xiě)到硬盤(pán)中衫樊，同時(shí)一個(gè)壓縮的域數(shù)據(jù)文件也被寫(xiě)入。

fdt文件格式.png

域索引文件（fdx）：

fdx文件格式.png

8利花、Tearm相關(guān)信息

8.1科侈、詞向量數(shù)據(jù)信息（tvx tvd）

tvd.png

詞向量文檔文件(tvd)：

• 一個(gè)段(segment)包含N篇文檔，此文件就有N項(xiàng)炒事，每一項(xiàng)包含了此文檔的所有的域的信息臀栈。
• 每一項(xiàng)首先是此文檔包含的域的個(gè)數(shù)NumFields，然后是一個(gè)NumFields大小的數(shù)組挠乳，數(shù)組的每一項(xiàng)是域號(hào)权薯。然后是一個(gè)(NumFields - 1)大小的數(shù)組，由前面我們知道睡扬，每篇文檔的第一個(gè)域在tvf中的偏移量在tvx文件中保存崭闲，而其他(NumFields - 1)個(gè)域在tvf中的偏移量就是第一個(gè)域的偏移量加上這(NumFields - 1)個(gè)數(shù)組的每一項(xiàng)的值。

詞向量索引文件(tvx)：

• 一個(gè)段(segment)包含N篇文檔威蕉，此文件就有N項(xiàng)，每一項(xiàng)代表一篇文檔橄仍。
• 每一項(xiàng)包含兩部分信息：第一部分是詞向量文檔文件(tvd)中此文檔的偏移量韧涨，第二部分是詞向量域文件(tvf)中此文檔的第一個(gè)域的偏移量。

tvx.png

8.2侮繁、詞典及詞典索引數(shù)據(jù)（tim tip ）

tim文件為詞典文件虑粥，tip為詞典索引文件；

tim中包含包含了每個(gè)域的詞統(tǒng)計(jì)信息及元數(shù)據(jù)信息宪哩；tip包含詞典的索引信息娩贷，通過(guò)索引可隨機(jī)訪問(wèn)詞數(shù)據(jù)信息。

timtip.png

8.3锁孟、文檔號(hào)及詞頻（frq）

Lucene內(nèi)部通過(guò)一個(gè)整數(shù)的文檔編號(hào)（document number）來(lái)表示文檔彬祖。第一篇被添加到索引中的文檔編號(hào)為0，每一篇隨后被添加的document獲得一個(gè)比前一篇更大的數(shù)字品抽。 需要注意的是一篇文檔的編號(hào)（document’s number）可以更改储笑，所以在Lucene之外存儲(chǔ)這些編號(hào)時(shí)需要特別小心。

frq.png

pos.png

pay.png

8.4圆恤、量化因子信息

量化因子.png

參考博客：

http://www.shenyanchao.cn/blog/2018/12/04/lucene-index-files/

https://lucene.apache.org/core/8_2_0/core/org/apache/lucene/codecs/lucene50/Lucene50PostingsFormat.html#Termindex
https://www.cnblogs.com/forfuture1978/archive/2009/12/14/1623599.html

參考文檔：

《Lucene實(shí)戰(zhàn)》
《AnnotatedLucene》
《開(kāi)放源代碼的全文檢索引擎Lucene》