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

在全文檢索領域， Lucene可謂是獨領風騷數十年。倒排索引構成全文檢索的根基，只有深入理解了倒排索引的實現原理，才能算是入門了全文檢索領域。本文將對Lucene的倒排索引的實現原理和技術細節進行詳細的剖析，這些內容適用于Lucene 5.x至7.x系列版本。文章整體內容組織如下：

倒排索引理論

Lucene倒排索引實現

Lucene索引文件構成

什么是Terms Index？

什么是Terms Dictionary?

結束語

理論

在學術上，倒排索引結構非常簡明易懂，如下：

也許你已接觸過倒排索引，下面這張圖你或許已經看過很多次了。本文將從你熟悉的部分開始，一步步深入去挖掘這張圖的一個個細節。這里先介紹兩個重要概念：

1. 索引，索引詞表。倒排索引并不需要掃描整個文檔集，而是對文檔進行預處理，識別出文檔集中每個詞。

2. 倒排表，倒排表中的每一個條目也可以包含詞在文檔中的位置信息（如詞位置、句子、段落），這樣的結構有利于實現鄰近搜索。詞頻和權重信息，用于文檔的相關性計算。

倒排索引由兩部分組成，所有獨立的詞列表稱為索引，詞對應的一系列表統稱為倒排表。 —— 來自《信息檢索》

如上圖所示，整個倒排索引分兩部分，左邊是Term Dictionary(索引表，可簡稱為Dictionary)，是由一系列的Terms組成的；右邊為Postings List(倒排表)，由所有的Term對應的Postings組成。

實際上Lucene所用的信息信息檢索方面的術語基本跟Information Retrieval（《信息檢索》原版）保持一致。比如Term、Dictionary、Postings等。

首先，有必要解釋一下，每個Segment中的每個字段(Field)都有這么一個獨立的結構。其次，它是不可改寫的，即不能添加或更改。至于為何選擇不可改寫的設計，簡單說有兩個方面：一是更新對磁盤來說不夠友好；另一方面是寫性能的影響，可能會引發各種并發問題。

我們可以用一個HashMap來簡單描述這個結構：Map>，這個Map的Key的即是Term，那它的Value即是Postings。所以它的Key的集合即是Dictionary了，這與上圖的描述太貼切了。由于HashMap的Key查找還是用了HashTable，所以它還解決Dictionary的快速查找的問題，一切顯得太美好了。這可以說是一個hello world版的倒排索引實現了。

Lucene的實現

全文搜索引擎通常是需要存儲大量的文本，Postings可能會占據大量的存儲空間，同樣Dictionary也可能是非常大的，因此上面說的基于HashMap的實現方式幾乎是不可行的。在海量數據背景下，倒排索引的實現都極其復雜，因為它直接關系到存儲成本以及搜索性能。為此，Lucene引入了多種巧妙的數據結構和算法。

Lucene索引文件構成

我們知道Lucene將索引文件拆分為了多個文件，這里我們僅討論倒排索引部分。

Lucene把用于存儲Term的索引文件叫Terms Index，它的后綴是.tip；把Postings信息分別存儲在.doc、.pay、.pox，分別記錄Postings的DocId信息和Term的詞頻、Payload信息、pox是記錄位置信息。Terms Dictionary的文件后綴稱為.tim，它是Term與Postings的關系紐帶，存儲了Term和其對應的Postings文件指針。

總體來說，通過Terms Index(.tip)能夠快速地在Terms Dictionary(.tim)中找到你的想要的Term，以及它對應的Postings文件指針與Term在Segment作用域上的統計信息。

postings: 實際上Postings包含的東西并不僅僅是DocIDs（我們通常把這一個有序文檔編號系列叫DocIDs），它還包括文檔編號、以及詞頻、Term在文檔中的位置信息、還有Payload數據。

所以關于倒排索引至少涉及5類文件，本文不會全面展開。

什么是Terms Index?

下面引用了一張來自網絡上的圖，非常直觀：

Terms Index即為上圖中.tip部分，它實際上是由一個或多個FST組成的，Segment上每個字段都有自己的一個FST（FSTIndex）記錄在.tip上，所以圖中FSTIndex的個數即是Segment擁有字段的個數。另外圖中為了方便我們理解把FST畫成Trie結構，然后其葉子節點又指向了tim的Block的，這實際上是用了一種叫Burst-Trie的數據結構。

Burst-Trie

.tip看起來是像一棵Trie，所以整張圖表現出來就是論文上的Burst-Trie結構了。上面一棵Trie，Trie的葉子節點是Container（即是Lucene中的Block）。下圖就是Paper上描述的Burst-Trie的結構：

來自Burst-Trie論文上的一張圖

Burst-Trie，關于Burst-Trie，網上有很多專業資料，這里只做簡單介紹。Burst-Trie可以認為是Trie的一種變種，它主要是將后綴進行了壓縮，降低了Trie的高度，從而獲取更好查詢性能。

Lucene工程上的實現方式

Burst-Trie在Lucene是如何應用的？

前面提到了Lucene是采用Burst-Trie的思想，但在實現上存在一定的出入，Lucene的Burst-Trie被拆成兩部分。如果一定把它們對應起來的話，我認為Burst-Trie的AccessTree的實現是FST，存在.tip文件中；Container的實現是Block，存在.tim文件里。Burst-Trie的Container內部是開放性結構，可能是Binary-Tree，可以也List。Lucene的block是數組，準確的說，就是把一系列的Block系列化寫到文件上，這里好像并沒有做特殊的處理。

FST

在Lucene，Terms Dictionary被存儲在.tim文件上。當一個Segment的文檔數量越來越多的時候Dictionary的詞匯也會越來越多，那查詢效率必然也會逐漸變低。因此需要一個很好的數據結構為Dictionary建構一個索引，將Dictionary的索引進一步壓縮，這就是后來的Terms Index(.tii)。這是在早期的版本中使用的，到Lucene 4.0之后做一次重構和升級，同時改名為.tip。

FST：Finite-State-Transducer，結構上是圖。我們知道把一堆字符串放一堆，把它們的同共前綴進行壓縮就會變成Burst-Trie。如果把后綴變成一個一個節點，那么它就是Trie結構了。如果將后綴也進行壓縮的話，那你就能發現他更變成一張圖結構了。 那么我們易知FST是壓縮字典樹后綴的圖結構，她擁有Trie高效搜索能力，同時還非常小。這樣的話我們的搜索時，能把整個FST加載到內存。

實際上，FST的結構非常復雜，我們可以簡單的將其理解為一個高效的K-V結構，而且空間占用率更高。這里想簡單強調一下：Lucene到底在FST里存了什么數據？?如果你已經了解FST在Lucene中充當的角色和作用的話，我想你可能會誤認為FST中存了Dictionary中所有的Terms數據，這樣可以通過FST是找到具體的Term的位置，或者通過FST可以切實獲知一個Term是否存在。

然而，事實并非如此。?FST即不能知道某個Term在Dictionary(.tim)文件上具體的位置，也不能僅通過FST就能確切的知道Term是否真實存在。它只能告訴你，查詢的Term可能在這些Blocks上，到底存不存在FST并不能給出確切的答案，因為FST是通過Dictionary的每個Block的前綴構成，所以通過FST只可以直接找到這個Block在.tim文件上具體的File Pointer，并無法直接找到Terms。關于FST的詳細細節，后面將以一篇獨立的文章來講解，這里暫時不展開過多細節。

下面會詳細的介紹Dictionary的文件結構，這里先提一下。每個Block都有前綴的，Block的每個Term實際不記錄共同前綴的。只有通過Block的共同的前綴，這是整個Block的每個Term共同的，所以每個Term僅需要記錄后綴可以通過計算得到，這可以減少在Block內查找Term時的字符串比較的長度。

簡單理解的話，你可以把它當成一個高級的BloomFilter，我們BloomFilter是有一定的錯誤率的；同時BloomFilter是通過HashCode實現的，只能用它來測試是否存在，并無法快速定位。在FST中，并無錯誤率且能快速定位。但是BloomFilter有更高的性能。

說了這么一大半天，Terms Index到底帶來哪些實質性的功能呢？?Terms Index是Dictionary的索引，它采用 了FST結構。上面已經提及了，FST提供兩個基本功能分別是：

1. 快速試錯，即是在FST上找不到可以直接跳出不需要遍歷整個Dictionary。類似于BloomFilter的作用。

2. 快速定位Block的位置，通過FST是可以直接計算出Block的在文件中位置（offset,FP）。

上面已經介紹了FST的一種功能，此外，FST還有別的功能，因為FST也是一個Automation(自動狀態機)。這是正則表達式的一種實現方式，所以FST能提供正則表達式的能力。通過FST能夠極大的提高近似查詢的性能，包括通配符查詢、SpanQuery、PrefixQuery等，甚至包括近期社區正在做的基于正則表達式的查詢。

什么是Terms Dictionary？

前面我們已經介紹了Terms Dictionary的索引，Terms Index。已經頻頻提到的Terms Dictionary到底是什么東東？Terms Dictionary是Segment的字典，索引表。它能夠讓你知道你的查詢的這個Term的統計信息，如tf-idf中df(doc_freq)和Total Term Frequence（Term在整個Segment出現頻率）；還能讓你知道Postings的元數據，這里是指Term的docids、tf以及offset等信息在Postings各個文件的文件指針FP。

Block并不記錄這個Block的起始和結束的范圍，所以當FST最終指向多個Block時，就會退化為線性搜索。那什么時候會出現FST最終指向多個Block呢？最簡單的一種情況是，超過48個的Term，且出現首字母相同的term的個數不超過25個。這種情況下由于沒有每個Block都沒有共同前綴，所以構建出來的FST只有一個結束節點記錄每個Block的文件尋址的偏移增量。

Lucene規定，每個Block的大小在25-48范圍內。

說這么多，還是覺得太抽象了，我們來看一下.tim文件結構示意圖：

主要是大兩部分信息，1. Block信息，包含所有Term的詳情；2. Field的自有屬性和統計信息。接下來我們將展開來介紹這兩部分內容。

Block信息 - NodeBlock

在整個.tim文件上，我覺得比較復雜且值得拎出來講的只有NodeBlock。那么，Block又是什么東東？它是如何被構建的？這部分代碼，還是比較晦澀難懂得，我每次讀時也都會產生一些新的疑問。

我們前面所有說的Block即是NodeBlock的一個Entry。 由上圖可以知道，Block中有兩種OuterNode和InnerNode。這里我想引用代碼上兩個類名來輔助我們接下來的剖析：PendingTerm/PendingBlock，我們暫且把它們叫作待寫的Term和子Block的指針吧。

NodeBlock從構建邏輯上來講是它是樹型結構，所以它由葉子節點和非葉子節點兩種節點組成。葉子節點就叫OutterNode，非葉子節點就叫InnerNode。一個Block可能含有一堆的Term(PendingTerm)和PendingBlock(當它是非葉子節點時)，實際上PendingBlock也是不可能出現在葉子節點上的。如果是PendingBlock，那么這個Entry只記錄兩個信息：后綴(這個Block的共同后綴)以及子Block的文件指針，此時就不必再記上所說的統計信息和postings信息了。

如圖所示，一個Block記錄的信息非常多，首先是Block的類型和Entry的條數等元數據信息，而后是該Block擁有的所有Entry。

這里每個Entry含有后綴、統計信息(對應為前面據說的權重，它含有ttf和df)、Postings的位置信息(這就是反復提及postings相關的文件指針，postings是拆分多文件存儲的)。 關于Postings更多細節，放到下個章節來討論。

Field信息 - FieldMetadata

相對來說FieldMetadata組織結構就簡單多了，純粹的線性寫入即可。但Field信息記錄的內容還是挺多的，包括字段本身的屬性，如字段編號、Terms的個數、最大和最小的Terms；此外還記錄了Segment級別的一些統計信息，包括tdf、擁有該字段的文檔總數（如果文檔沒有該字段，或者該字段為空就不計了）。

1. RootCode實際上指向該字段第一個Block的文件指針。

2. LongsSize這個名字有點隱晦，它是說該字段的字段存儲哪些Postings信息。因為我們是可以指定Postings存儲或者不存儲諸如位置信息和Payload信息的，存與不存將被表現在這里了。

從搜索流程來看，Lucene先讀到FieldMetadata的信息，然后判斷Query上Terms是否落在這里字段的MinTerm和MaxTerm之間。如果不在的話，完全不需要去讀NodeBlock的。MinTerm和MaxTerm可以有效的避免讀取不必要的.tip文件。

結束語

到這里，關于倒排索引結構中第一部分內容已經介紹完了，限于篇幅的原因，還有更多有趣的小細節沒有呈現出來。簡單總結一下：我們先從Information Retrieve開始了解學術上倒排索引結構，接著我們又對Luecne的實現做了深入剖析。Lucene對索引詞表也做了索引（叫Terms Index，文件后綴是.tip），索引詞表的索引采用Finite-State Transducer這種數據結構。由于這種結構占用空間極小，所以它完成可以被加載到內存加速Terms Dictionary的查找過程。而后又介紹了Terms Dictionary，Terms Dictionary以Terms Index共同構成與Burst-Trie類似的數據結構，Terms Dictionary含兩部分信息：1. NodeBlock記錄Dictionary的所有Terms；2. FieldMetadata存儲了FieldInfos信息和Segment的統計信息。

關于倒排索引還有Postings List，這部分內容將在下篇文章中介紹。

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

NoSQL數據庫

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

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