Lucene倒排索引原理探秘(2)

上篇文章《Lucene倒排索引原理探秘(1)》詳細介紹了Lucene索引表的實現，內容涉及關于Terms Index以及Term Dictionary的剖析。

此文將繼續剖析Lucene倒排索引實現的另一部分核心內容： 倒排表（Postings）。Lucene的官方文檔關于該部分內容的描述非常豐富，所以學習起來也相對輕松。

Postings編碼

開始之前先介解Lucene在Postings采用了兩個關鍵的編碼格式，PackedBlock和VIntBlock。PackedBlock是在Lucene 4.0引入，帶來向量化優化。

VIntBlock

VIntBlock是能夠存儲復合數據類型的數據結構，主要通過變長整型（Variable Integer）編碼達到壓縮的目的。此外VIntBlock還能夠存儲byte[]，比如.pay用VIntBlock存儲了payloads數據等。

值得一提的是，VIntBlock可以存儲變長數據結構，如.doc用它存儲DocID和TermFreq時，由于在特定條件下(TermFreq=1)，Lucene會省略TermFreq以提高空間占用率。Lucene用一個VInt來表示DocID，VInt則用每個Byte左邊第一個Bit來表示是否需要讀取順續到下個Byte。也就是說一個VInt有效位是28bit，這就說明VInt頭部是有特殊含義的，因此Lucene只能在VInt最右邊的一個bit下功夫。讓VInt的右邊第一Bit來表示是否有下個數據。具體用法會在介紹.doc文件格式時介紹。

PackedBlock

PackedBlock只能存儲單一整數(Integer/Long)數組結構。這里主要介紹PackedInts：它將一個int[]打包成一個Block。PackedBlock只能存儲固定長度的數組（Lucene規定其長度為128個元素），它的壓縮方式是將每個元素截斷為一個預算的長度（length，單位是bit），以達到壓縮的目的。所以當長度length不是8的倍數時，會出現一個byte被多個元素占用的情形。

PackedBlock需要把整個int[]的所有條目指定長度編碼，所以PackedBlock只能選擇int[]最大的數來計算長度，否則會讓大數失真。反過來，PackedBlock都選擇64位，則會浪費空間，不能達到壓縮的目的。

Lucene預先編譯了64個PackedFormat編碼器和解碼器，即針對Long以內的每種長度都數據都有自己的解碼和編碼器，以提高編解碼的性能。

PackedPosDeltaBlock、PackedDocDeltaBlock以及PackedFreqBlock都采用了PackedInts結構，它能存儲的信息實際上是很有限的，只能存儲Int的數組。所以在PackedPosDeltaBlock的時候，只能存儲position信息，在VIntBlock則會存儲更多必要信息，減少搜索時的IO操作。

這也是為什么需要將DocId和TermFreq拆分成PackedDocDeltaBlock和PackedFreqBlock兩個Block存儲的原因了。

定長是指PackedBlock限定了一個Block僅允許存儲長度128的整型數組，而不是限定Block用多少個Bytes來存儲編碼后的結果。另外Block存儲占用的大小，是按數組中最大那個數的有效bits長度來計算整個Block需要占用多大的Bytes數組的。也就是Block的每個數據的長度都是一樣，都按最長bits來計算。

比如：（我們定義一個函數，bit(num)用來計算num占用多少個bits）

1. 數組中最大的是1，那么PackedBlock的長度僅是16Bytes。bit(1) * 128 / 8 = 16

2. 數組中最大的是128，PackedBlock長度則是144個Bytes。bit(128) * 128 / 8 = 144

3. 數組中最大的是520，PackedBlock則需要160Bytes。bit(520) * 128 / 8 = 160

簡單總結一下，PackedBlock相當于實現了向量化優化，Lucene通常會將整個PackedBlock加載到內存，既可以減少IO操作數，又能提高解碼的性能。相對而言VIntBlock則能夠更豐富數據類型，比較適合存儲少量數據。

Postings文件格式說明

進入正題，我們知道整個Postings被拆成三個文件存儲，實際上它們之間也是相對獨立的。基本所有的查詢都會用.doc，且一般的Query僅需要用到.doc文件就足夠了；近似查詢則需要用.pox；.pay則是用于Payloads搜索（關于這個之前寫一篇博客《Solr 遲到的Payloads》，介紹了Payloads用法和場景)。

Frequencies And Skip Data(.doc文件)

在Lucene倒排索引中，只有.doc是Postings必要文件，即它是不能被省略的。除此之外的兩個文件通過配置都是可以省略的。那么.doc到底存儲了哪些關鍵信息呢？直接上圖：

這里畫得不夠清晰，每個Term都有成對的TermFreqs和SkipData的。換言之，SkipData是為TermFreqs構建的跳表結構，所以它們是成對出現的。

TermFreqs — Frequencies

TermFreqs存儲了Postings最核心的內容，DocID和TermFreqs，分別表示文檔號和對應的詞頻，它們是一一對應的，Term出現在文檔上，就會有Term在文檔中出現次數（TermFreqs）。

Lucene早期的版本還沒有PackedBlock結構，所以DocID與TermFreq是以一個二元組的方式存儲的。這個結構簡單，有助于理解，但卻并不準確。既然是想深入剖析，還是有必要還原真相的。

TermFreqs采用的是混合存儲，由Packed Blocks和VInt Blocks兩種結構組成。由于PackedBlock是定長的，當前Lucene默認是128個Integers。所以在不滿128個值的時候，Lucene采用VIntBlocks結構存儲。需要注意的是當用Packed Blocks結構時，DocID和TermFreq是分開存儲的，各自將128個值寫入到一個Block。

當用VIntBlocks結構時，還是沿用舊版本的存儲方式，即上面描述的二元組的方式存儲。所以說，將DocID和TermFreq當成一條數據的說法是不完全準確的。

在Lucene4.0之前的版本，還沒有引入PackedBlock時，DocID和TermFreq確定完全是成對出現，當時只有VIntBlock一種結構。

Lucene盡可能優先采用PackedBlocks，剩余部分（不足128部分）則用VIntBlocks存儲。引入PackedBlock之后，PackedDocDeltaBlock跟PackedFreqBlock是成對的，所以它的寫出來的示意圖應該是如下：

每個PackedBlock由一個PackedDocDeltaBlock和一個PackedFreqBlock構成，它們都采用PackedInts格式。

例如，在同一個Segment里，某一個Term A在259個文檔同一個字段出現，那么Term A就需要把這259個文檔的文檔編號和Term A在每個文檔出現的頻率一同記下來存儲在.doc。此時，Lucene需要用到2個PackedBlocks和3個VIntBlocks來存儲它們。

VIntBlock結構相對復雜一些，它以一種巧妙的方式存儲復雜的多元組結構。在.doc文件中，用VIntBlock存儲DocID和TermFreqs二元組。后面將介紹的Positions則用VIntBlock存儲了Postition、Payload和Offset多元組， byte[]和VInt多種數據類型。

這里每一個PackedBlock結構都包含了一個PackedDocDeltaBlock和一個PackedFreqBlock，如果沒有省略Frequencies（TermFreq）；如果用戶配置了不存儲詞頻（TermFreq），此時一個PackedBlock僅包含一個PackedDocDeltaBlock。PackedFreqBlock（TermFreq）的存儲方式跟PackedDocDeltaBlock（DocID）完全一致，包括后面要講的pos/pay也都一樣的，都使用Packed Block這種編碼方式。

在VIntBlock上如何存儲DocDelta和TermFreq？如果設置了不存儲TermFreq時，Lucene將所有DocDelta以Variable Integer的編碼方式直接寫到文件里。當設置為存儲TermFreq信息時，實際上，TermFreq信息會被按需存儲。Lucene做了一個小優化，即當TermFreq=1時，TermFreq將不被存儲。那么原本DocDelta（DocID的增量）后面緊跟一個Frequencies的情況變得不再確定，因為壓根無法知道DocDelta后面還有沒有TermFreq信息。那應該如何識別TermFreq信息是否存在？Lucene先把數值向左移動一位，然后用最右的一個Bit的標記是否存儲TermFreq。最后右邊的一個bit為1表示沒有存儲，0作為有存儲TermFreq。實際上這是Lucene的慣用手段。

左移一位，實際上等同于X2，當最后一個bit是0，此時是一定是偶數，表示后面還存 儲了TermFreq；左移一位再+1，相當于偶數+1，那就是奇數，此時最后一個bit是1，表示TermFreq=1，所以后面沒有存儲TermFreq。

DocFreq=1時，Lucene做一個叫Singletion（僅出現在一個文檔中）的優化，此時就沒有TermFreq和SkipData。因為TermFreq等同于TotalTermFreq（上篇文章介紹過，存儲在.tim的FieldMetadata上）。

Multi-level SkipList — SkipData

SkipData是.doc文件核心部件之一，Lucene采用的是多層次跳表結構，首先我們先預熱一下SkipList的邏輯結構圖，最后剖析Lucene存儲SkipList的物理結構圖。下圖(源自網圖)很好的描述了SkipList的結構：

跳表的原理非常簡單，跳表其實就是一種可以進行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級索引，通過索引來實現快速查找。首先在最高級索引上查找最后一個小于當前查找元素的位置，然后再跳到次高級索引繼續查找，直到跳到最底層為止，這時候以及十分接近要查找的元素的位置了(如果查找元素存在的話)。由于根據索引可以一次跳過多個元素，所以跳查找的查找速度也就變快了。 ——— 百度百科

將搜索時耗時轉嫁給索引時，這就是Lucene索引的“空間換時間”的基本思想。為此Lucene為Postings構建SkipList ，并把按層級將它系列化存儲。第一個SkipLevel是最高，擁有最少的索引數。

Lucene在索引時構建了SkipList，在Segment中每個Term都有自己唯一的Postings，每個Postings都有需要構建一個SkipList，這三者是一一對應的。所以畫出來結構圖如下：

除了第0層之外所有SkipLevel的每個跳表數據塊（SkipDatum）會存儲了指向下一個SkipLevel的指針。圖中SkipChildLevelFPg帶?的原因是在Level 0時，SkipDatum沒有下一級可以記錄。如果Postings有存儲positions、payloads和offsets的話，在跳表數據塊中也會記錄它們的Block所有文件指針。

通過SkipList可以找到DocID和TermFreq之外，還能找到Positions、Payloads和Offsets這三部分信息。因此，在搜索時通過SkipList可以快速定位Postings的所有相關信息。

關于Lucene構建SkipList的幾點細節(Lucene規定SkipList的層級不超過10層)：

1. 第0層，SkipList為每個Block增加索引，所以VIntBlock不在SkipList上。

2. 第9層，SkipList的第一個節點是在第89?(227)Block。（這個數確實有點大）

3. 第n層，SkipList的第m個節點的位置是第8^n * m個Block。

跳表的第一層是最密的，越高層越稀疏。按層級從低到高依次系列化為寫入.doc的SkipData部分。換言之，SkipDatum個數越多，SkipLevelLength則會越大。

SkipLevelLength說明當前層次Skip系列化之后的長度，SkipLevel是包含該層的所有節點的數據SkipDatum。SkipDatum包含四部分信息，doc_id和term_freq、positions、payloads、以及下一層開始的位置（是第N層指向第N-1層的前一個索引）。

SkipList主要是搜索時的優化，主要是減少集合間取交集時需要比較的次數，比如在Query被分詞器分成多個關鍵詞時，搜索結果需要同時滿足這些關鍵詞的，此時需要將每個Term對應的DocId集合進行析取操作，通過跳表能夠有效有減少比較的次數。

Postitions(.pos文件)

.pos文件存儲所有Terms出現文檔中的位置信息。為了更好的搜索性能，Lucene還在VIntBlock上存儲了部分payloads和offsets信息。實際上只有VIntBlock才有能力來存儲復雜的數據結構，PackedBlock是不具備這樣的能力的。具體請參考下面的示意圖：

Lucene把同一個Term的所有position信息存儲在同一個TermPositions上，并沒有邏輯或者物理上的劃分。將在一個文檔里出現的所有位置信息，按出現的先后順序依次寫入。 關鍵在于，position與TermFreq并不是在一維度上，TermFreq的數值就是position的個數。也就是說，通過.pos文件無法知道每個position的具體含義，PostingsReader通過.doc文件的DocID和TermFreq信息才能算出Postition的是在哪個文檔上的哪個位置。

Payloads and Offsets(.pay文件)

Payloads，可以理解為Term的附加信息，它是與Term成對出現的，類似于Map。在用法上也是如此，Payloads的信息需要用byte數組存儲，所以在TermPayloads并不能用PackedBlock結構來存儲。TermOffsets由2個int來表示Offset的開始位置和長度，可以將它們拆成兩個等size的int[]，因此可以用PackedBlock存儲。如下圖：

總結

開篇先學習了Lucene用于存儲Postings的兩種結構，PackedBlock和VIntBlock。PackedBlock是Lucene4.0引用的，它的核心就是一個int[]，為Postings提供向量化優化，VIntBlock也是一種很巧妙且優雅的結構，能存儲復雜的類型。

而后，在介紹.doc文件格式的同時，又對上面的兩大結構深入剖析，了解這兩個結構是理解postings的基礎。接下來剖析了.doc文件上采用的SkipList數據結構，主要是搜索時集合間AND操作上的一個優化。至于postings中其它兩個文件格式，僅做了簡單介紹。

Lucene倒排索引部分內容到這里全部結束，包含很多優雅的設計和巧妙的結構，其中蘊含的Lucene設計之美，值得我們反復研讀。

本文轉載自微信公眾號【Nosql漫談】。

NoSQL數據庫

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。