【搜索引擎】全文索引数据结构和算法
最近一直在研究sphinx的工作機制，在［搜索引擎］Sphinx的介紹和原理探索簡單地介紹了其工作原理之后，還有很多問題沒有弄懂，比如底層的數據結構和算法，于是更進一步地從數據結構層面了解其工作原理。在網上搜了很多資料，發現沒有很多介紹這方面的文章，后來找到了一本書，《這就是搜索引擎》，拜讀了本書的第三章，介紹了主流搜索引擎用的數據結構及其工作原理，sphinx使用的數據結構也是一樣的，用的也是倒排索引。
注：本文不會對sphinx和搜索引擎嚴格區分開，同一作搜索引擎看待。
先附圖一枚：
索引基礎
先介紹與搜索引擎有關的一些基本概念，了解這些概念對后續了解工作機制非常重要。
單詞-文檔矩陣
單詞-文檔矩陣是表達兩者之間所具有的一種包含關系的概念模型。如下圖所示，每列代表一個文檔，每行代表一個單詞，打對鉤的位置代表包含關系。
?
從縱向看，可以得知每列代表文檔包含了哪些單詞；從橫向看，每行代表了哪些文檔包含了某個單詞。搜索引擎的索引其實就是實現單詞-文檔矩陣的具體數據結構。可以有不同的方式來實現上述概念模型，比如倒排索引、簽名文件、后綴樹等方式。但實驗數據表明，倒排索引是單詞到文檔映射關系的最佳實現方式。
倒排索引基本概念
文檔（Document）：以文本形式存在的存儲對象。如：網頁、Word、PDF、XML等不同格式的文件。
文檔集合（Document Collection）：若干文檔構成的集合。如：大量的網頁。
文檔編號（Document ID）：搜索引擎內部，唯一標識文檔的唯一編號。
單詞編號（Word ID）：搜索引擎內部，唯一標識單詞的唯一編號。
倒排索引（Inverted Index）：實現單詞--文檔矩陣的一種具體存儲形式。倒排索引主要有單詞詞典和倒排文件組成。
單詞詞典（Lexicon）：文檔集合中出現過的所有單詞構成的字符串集合，單詞詞典內每條索引項記載單詞本身的一些信息及指向倒排列表的指針。
倒排列表（PostingList）：出現了某個單詞的所有文檔的文檔列表及單詞在該文檔中出現的位置信息。列表中每條記錄稱為一個倒排項（Posting）。
倒排文件（Inverted File）：保存所有單詞的倒排列表的文件，倒排文件是存儲倒排索引的物理文件。
概念之間的關系如圖：
?
倒排索引簡單實例
下面舉一個實例，這樣對倒排索引有一個更直觀的感受。
假設文檔集合包含5個文檔，每個文檔內容如下圖所示：
?
建立的倒排索引如下圖：
?
?
單詞ID：記錄每個單詞的單詞編號；
單詞：對應的單詞；
文檔頻率：代表再文檔集合中有多少個文檔包含某個單詞
倒排列表：包含單詞ID及其他必要信息
TF：單詞在某個文檔中出現的次數
POS：單詞在文檔中出現的位置
以單詞“加盟”為例，其單詞編號為8，文檔頻率為3，代表整個文檔集合中有三個文檔包含這個單詞，對應的倒排列表為{(2;1;<4>),(3;1;<7>),(5;1;<5>)}，含義是在文檔2，3，5出現過這個單詞，在每個文檔的出現過1次，單詞“加盟”在第一個文檔的POS是4，即文檔的第四個單詞是“加盟”，其他的類似。
這個倒排索引已經是一個非常完備的索引系統，實際搜索系統的索引結構基本如此。
?
單詞詞典
單詞詞典用來維護文檔集合中出現過的所有單詞的相關信息，同時用來記載某個單詞對應的倒排列表在倒排文件中的位置信息。在查詢時到單詞詞典里查詢，就能獲得相應的倒排列表，并以此作為后序排序的基礎。
?
常用數據結構：哈希加鏈表和樹形詞典結構。
哈希加鏈表
下圖是哈希加鏈表詞典結構的示意圖。主體是哈希表，每個哈希表項保存一個指針，指針指向沖突連表，相同哈希值的單詞形成鏈表結構。
構建過程：
對文檔進行分詞；
對于做好的分詞，利用哈希函數獲取哈希值；
根據哈希值對應的哈希表項找到對應的沖突鏈表；
如果沖突鏈表已經存在該單詞
不處理
否則
加入沖突連表
樹形結構
使用B樹或者B+樹的結構。與哈希表不同的是，需要字典項能按照大小排序，即使用數字或字符序。
樹形結構中，使用層級查找，中間節點保存一定順序范圍的詞典項目存儲在哪個子樹中，最底層的葉子節點存儲單詞的地址信息。
倒排列表
倒排列表用來記錄哪些文檔包含了某個單詞。倒排列表由倒排索引項組成，每個倒排索引項由文檔ID，單詞出現次數TD以及單詞在文檔中哪些位置出現過等信息。包含某單詞的一些列倒排索引項形成了某個單詞對應的倒排列表。下圖是倒排列表示意圖：
?
建立索引
前面介紹了索引結構，那么，有了數據之后索引是怎么建立的呢？主要有三種建立索引的方法。
兩遍文檔遍歷法（2-Pass In-Memory Inversion）
此方法在內存里完成索引的創建過程。要求內存要足夠大。
第一遍
收集一些全局的統計信息。包括文檔集合包含的文檔個數N，文檔集合內所包含的不同單詞個數M，每個單詞在多少個文檔中出現過的信息DF。
將所有單詞對應的DF值全部相加，就可以知道建立最終索引所需的內存大小是多少。
獲取信息后，根據統計信息分配內存等資源，同事建立好單詞相對應倒排列表在內存中的位置信息。
第二遍
逐個單詞建立倒排列表信息。獲得包含某個單詞的每個文檔的文檔ID，以及這個單詞在文檔中的出現次數TF，然后不斷填充第一遍掃描時所分配的內存。當第二遍掃描結束的時候，分配的內存正好被填充滿，每個單詞用指針所指向的內存區域“片段”，其起始位置和終止位置之間的數據就是這個單詞對應的倒排列表。
排序法（Sort-based Inversion）
在建立索引過程中，始終在內存中分配固定大小的空間，用來存放詞典信息和索引的中間結果，當分配的空間被消耗光的時候，把中間結果寫入磁盤，清空內存里中間結果所占空間，以用做下一輪存放索引中間結果的存儲區。參考下圖：
上圖是排序法建立索引中間結果的示意圖。建立過程：
讀入文檔后，對文檔進行編號，賦予唯一的文檔ID，并對文檔內容解析；
將單詞映射為單詞ID；
建立（單詞ID、文檔ID、單詞頻率）三元組；
將三元組追加進中間結果存儲區末尾；
然后依次序處理下一個文檔；
當分配的內存定額被占滿時，則對中間結果進行排序（根據單詞ID->文檔ID的排序原則）；
將排好序的三元組寫入磁盤文件中。
注：在排序法建立索引的過程中，詞典是一直存儲在內存中的，由于分配內存是固定大小，漸漸地詞典占用內存越來越大，那么，越往后，可用來存儲三元組的空間越來越少。
建立好索引后，需要合并。
合并時，系統為每個中間結果文件在內存中開辟一個數據緩沖區，用來存放文件的部分數據。將不同緩沖區中包含的同一個單詞ID的三元組進行合并，如果某個單詞ID的所有三元組全部合并完成，說明這個單詞的倒排列表已經構建完成，則將其寫入最終索引中，同事將各個緩沖區中對應這個單詞ID的三元組內容清空。緩沖區繼續從中間結果文件讀取后續的三元組進行下一輪合并。當所有中間結果文件都依次被讀入緩沖區，并合并完成后，形成最終的索引文件。
歸并法（Merge-based Inversion）
歸并法與排序法類似，不同的是，每次將內存中數據寫入磁盤時，包括詞典在內的所有中間結果都被寫入磁盤，這樣內存所有內容都可以被清空，后續建立索引可以使用全部的定額內存。歸并法的示意圖如下所示：
?
與排序法的差異：
1、排序法在內存中存放的是詞典信息和三元組數據，詞典和三元組數據并沒有直接的聯系，詞典只是為了將單詞映射為單詞ID。歸并法則是在內存中建立一個完整的內存索引結構，是最終文章索引的一部分。
2、在將中間結果寫入磁盤臨時文件時，歸并法將這個內存的倒排索引寫入臨時文件，隨后徹底清空所占內存。而排序法只是將三元組數據排序后寫入磁盤臨時文件，詞典作為一個映射表一直存儲在內存中。
3、合并時，排序法是對同一單詞的三元組依次進行合并；歸并法的臨時文件則是每個單詞對應的部分倒排列表，所以在合并時針對每個單詞的倒排列表進行合并，形成這個單詞的最終倒排列表。
動態索引
在真實環境中，搜索引擎需要處理的文檔集合內有些文檔可能被刪除或者內容被修改。如果要在內容被刪除或修改之后馬上在搜索結果中體現出來，動態索引可以實現這種實時性需求。動態索引有三個關鍵的索引結構：倒排索引、臨時索引和已刪除文檔列表。
臨時索引：在內存中實時建立的倒排索引，當有新文檔進入系統時，實時解析文檔并將其追加進這個臨時索引結構中。
已刪除列表：存儲已被刪除的文檔的相應文檔ID，形成一個文檔ID列表。當文檔被修改時，可以認為先刪除舊文檔，然后向系統增加一篇新文檔，通過這種間接方式實現對內容更改的支持。
當系統發現有新文檔進入時，立即將其加入臨時索引中。有新文檔被刪除時，將其加入刪除文檔隊列。文檔被更改時，則將原先文檔放入刪除隊列，解析更改后的文檔內容，并將其加入臨時索引。這樣就可以滿足實時性的要求。
在處理用戶的查詢請求時，搜索引擎同時從倒排索引和臨時索引中讀取用戶查詢單詞的倒排列表，找到包含用戶查詢的文檔集合，并對兩個結果進行合并，之后利用刪除文檔列表進行過濾，將搜索結果中那些已經被刪除的文檔從結果中過濾，形成最終的搜索結果，并返回給用戶。
索引更新策略
動態索引可以滿足實時搜索的需求，但是隨著加入文檔越來越多，臨時索引消耗的內存也會隨之增加。因此要考慮將臨時索引的內容更新到磁盤索引中，以釋放內存空間來容納后續的文檔，此時就需要考慮合理有效的索引更新策略。
完全重建策略（Complete Re-Build）
對所有文檔重新建立索引。新索引建立完成后，老的索引被遺棄釋放，之后對用戶查詢的響應完全由新的索引負責。在重建過程中，內存中仍然需要維護老的索引對用戶的查詢做出響應。如圖所示
再合并策略（Re-Merge）
有新文檔進入搜索系統時，搜索系統在內存維護臨時倒排索引來記錄其信息，當新增文檔達到一定數量，或者指定大小的內存被消耗完，則把臨時索引和老文檔的倒排索引進行合并，以生成新的索引。過程如下圖所示：
更新步驟：
1、當新增文檔進入系統，解析文檔，之后更新內存中維護的臨時索引，文檔中出現的每個單詞，在其倒排列表末尾追加倒排列表項，這個臨時索引可稱為增量索引
2、一旦增量索引將指定的內存消耗光，增量索引和老的倒排索引內容需要進行合并。
高效的原因：在對老的倒排索引進行遍歷時，因為已經按照索引單詞的詞典序由低到高排好順序，所以可以順序讀取文件內容，減少磁盤尋道時間。
缺點：因為要生成新的倒排索引文件，所以老索引中的倒排列表沒發生變化也需要讀出來并寫入新索引中。增加了I/O的消耗。
原地更新策略（In-Place）
原地更新策略的出發點是為了解決再合并策略的缺點。
在索引合并時，并不生成新的索引文件，而是直接在原先老的索引文件里進行追加操作，將增量索引里單詞的倒排列表項追加到老索引相應位置的末尾，這樣就可達到上述目標，即只更新增量索引里出現的單詞相關信息，其他單詞相關信息不變動。
為了能夠支持追加操作，原地更新策略在初始建立的索引中，會在每個單詞的倒排列表末尾預留出一定的磁盤空間，這樣，在進行索引合并時，可以將增量索引追加到預留空間中。如下圖：
實驗數據證明，原地更新策略的索引更新效率比再合并策略低，原因：
1、由于需要做快速遷移，此策略需要對磁盤可用空間進行維護和管理，成本非常高。
2、做數據遷移時，某些單詞及其對應倒排列表會從老索引中移出，破壞了單詞連續性，因此需要維護一個單詞到其倒排文件相應位置的映射表。降低了磁盤讀取速度及消耗大量內存（存儲映射信息）。
混合策略（Hybrid）
將單詞根據其不同性質進行分類，不同類別的單詞，對其索引采取不同的索引更新策略。常見做法：根據單詞的倒排列表長度進行區分，因為有些單詞經常在不同文檔中出現，所以其對應的倒排列表較長，而有些單詞很少見，則其倒排列表就較短。根據這一性質將單詞劃分為長倒排列表單詞和短倒排列表單詞。長倒排列表單詞采取原地更新策略，而短倒排列表單詞則采取再合并策略。
因為長倒排列表單詞的讀/寫開銷明顯比短倒排列表單詞大很多，所以采用原地更新策略能節省磁盤讀/寫次數。而大量短倒排列表單詞讀/寫開銷相對而言不算太大，所以利用再合并策略來處理，則其順序讀/寫優勢也能被充分利用。
查詢處理
建立好索引之后，如何用倒排索引來響應用戶的查詢呢？主要有下面三種查詢處理機制。
一次一文檔（Doc at a Time）
以倒排列表中包含的文檔為單位，每次將其中某個文檔與查詢的最終相似性得分計算完畢，然后開始計算另外一個文檔的最終得分，直到所有文檔的得分計算完畢為止。然后根據文檔得分進行大小排序，輸出得分最高的K個文檔作為搜索結果輸出，即完成了一次用戶查詢的響應。實際實現中，只需在內存中維護一個大小為K的優先級隊列。如下圖所示是一次一文檔的計算機制示意圖：
虛線箭頭標出查詢處理計算的前進方向。查詢時，對于文檔1而言，因為兩個單詞的倒排列表中都包含這個文檔，所以可以根據各自的TF和IDF等參數計算文檔和查詢單詞的相似性，之后將兩個分數相加得到文檔1和用戶查詢的相似性得分Score1。其他的也是類似計算。最后根據文檔得分進行大小排序，輸出得分最高的K隔文檔作為搜索結果輸出。
一次一單詞（Term at a Time）
與一次一文檔不同，一次一單詞采取“先橫向再縱向”的方式，首先將某個單詞對應的倒排列表中的每個文檔ID都計算一個部分相似性得分，也就是說，在單詞-文檔矩陣中首先進行橫向移動，在計算完某個單詞倒排列表中包含的所有文檔后，接著計算下一個單詞倒排列表中包含的文檔ID，即進行縱向計算，如果發現某個文檔ID已經有了得分，則在原先得分基礎上累加。當所有單詞都處理完畢后，每個文檔最終的相似性得分計算結束，之后按照大小排序，輸出得分最高的K個文檔作為搜索結果。 下圖是一次一單詞的運算機制。
虛線箭頭指示出了計算的前進方向，為了保存數據，在內存中使用哈希表來保存中間結果及最終計算結果。在查詢時，對于文檔1，根據TD和IDF等參數計算這個文檔對”搜索引擎“的相似性得分，之后根據文檔ID在哈希表中查找，并把相似性得分保存在哈希表中。依次對其他文檔計算后，開始下一個單詞（此處是”技術“）的相似性得分的計算。計算時，對于文檔1，計算了相似性得分后，查找哈希表，發現文檔1以及存在得分，則將哈希表對應的得分和剛剛計算得到的得分相加作為最終得分，并更新哈希表1中文檔1對應的得分，這樣就得到文檔1和用戶查詢最終的相似性得分，類似的計算其他文檔，最后將結果排序后輸出得分最高的K個文檔作為搜索結果。
跳躍指針（Skip Pointers）
基本思想：將一個倒排列表數據化整為零，切分為若干個固定大小的數據塊，一個數據塊作為一組，對于每個數據塊，增加元信息來記錄關于這個塊的一些信息，這樣即使是面對壓縮后的倒排列表，在進行倒排列表合并的時候也能有兩個好處：
1、無須解壓所有倒排列表項，只解壓部分數據即可
2、無須比較任意兩個文檔ID。
下圖是將“Google”這個查詢詞對應的倒排列表加入跳躍指針后的數據結構。
假設對于“Google”這個單詞的倒排列表來說，數據塊的大小為3。然后在每塊數據前加入管理信息，比如第一塊的管理信息是<<5,Pos1>>，5表示塊中第一個文檔ID編號，Pos1是跳躍指針，指向第2塊的起始位置。假設要在單詞“Google"壓縮后的倒排列表里查找文檔ID為7的文檔。首先，對倒排列表前兩個數值進行數據解壓縮，讀取第一組的跳躍指針數據，發現其值為<5,Pos1>，其中Pos1指出了第2組的跳躍指針在倒排列表中的起始位置，于是可以解壓縮Pos1位置處連續兩個數值，得到<13,Pos2>。5和13是兩組數據中最小的文檔ID（即每組數據的第一個文檔ID），我們要找的是7，那么如果7號文檔包含在單詞”Google“的倒排列表中的話，就一定會出現在第一組，否則說明倒排列表中不包含這個文檔。解壓第1組數據后，根據最小文檔編號逆向恢復其原始的文檔編號，此處<2,1>的原始文檔ID是：5+2=7，與我們要找的文檔ID相同，說明7號文檔在單詞”Google“的倒排列表中，于是可以結束這次查找。
從上面的查找過程可知，在查找數據時，只需要對其中一個數據塊進行解壓縮和文檔編號查找即可獲得結果，而不必解壓所有數據，很明顯加快查找速度，并節省內存空間。
缺點：增加指針比較操作的次數。
實踐表明：假設倒排列表的長度為L（即包含L個文檔ID），使用根號L作為塊大小，則效果較好。
多字段索引
即對文檔的多個字段進行索引。
實現多字段索引的方式：多索引方式、倒排列表方式和擴展列表方式。
多索引方式
針對每個不同的字段，分別建立一個索引，當用戶指定某個字段作為搜索范圍時，可以從相應的索引里提取結果。當用戶沒有指定特定字段時，搜索引擎會對所有字段都進行查找并合并多個字段的相關性得分，這樣效率較低。多索引方式示意圖如下：
倒排列表方式
將字段信息存儲在某個關鍵詞對應的倒排列表內，在倒排列表中每個文檔索引項信息的末尾追加字段信息，這樣在讀出用戶查詢關鍵詞的倒排列表的同時，就可以根據字段信息，判斷關鍵詞是否在某個字段出現，以此來進行過濾。倒排列表方式示意圖如下：
擴展列表方式
這是用得比較多的支持多字段索引的方法。為每個字段建立一個列表，該列表記錄了每個文檔這個字段對應的出現位置信息。下圖是擴展列表的示意圖：
為方便起見，只針對”標題“字段所建立擴展列表。比如第一項<1,(1,4)>，代表對于文檔1而言，其標題的位置為從第一個單詞到第4個單詞這個范圍，其他項含義類似。
對于查詢而言，假設用戶在標題字段搜索”搜索引擎“，通過倒排列表可以知道文檔1、3、4包含這個查詢詞，接下來需要判斷這些文檔是否在標題字段中出現過查詢詞？對于文檔1，”搜索引擎“這個查詢詞的出現位置是6和10。而通過對應的標題擴展列表可知，文檔1的標題范圍是1到4，說明文檔1的標題內不包含查詢詞，即文檔1不滿足要求。對于文檔3，”搜索引擎出現的位置是2、8、15，對應的標題擴展列表中，標題出現范圍為1到3，說明在位置2出現的這個查詢詞是在標題范圍內的，即滿足要求，可以作為搜索結果輸出。文檔4也是類似的處理。
短語查詢
短語查詢的本質是如何在索引中維護單詞之間的順序關系或者位置信息。較常見的支持短語查詢技術包括：位置信息索引、雙詞索引和短語索引。也可將三者結合使用。
位置信息索引（Position Index）
在索引中記錄單詞位置信息，可以很方便地支持短語查詢。但是其付出的存儲和計算代價很高。示意圖如下：
<5,2,[3,7]>的含義是，5文檔包含“愛情“這個單詞，且這個單詞在文檔中出現2次，其對應的位置為3和7，其他的含義與此相同。
查詢時，通過倒排列表可知，文檔5和文檔9同時包含兩個查詢詞，為了判斷在這兩個文檔中，用戶查詢是否以短語的形式存在，還要判斷位置信息。”愛情“這個單詞在5號文檔的出現位置是3和7，而”買賣“在5號文檔的出現位置是4，可以知道5號文檔的位置3和位置4分別對應單詞”愛情“和”買賣“，即兩者是一個短語形式，而根據同樣的分析可知9號文檔不是短語，所以5號文檔會被作為搜索結果返回。
雙詞索引（Nextword Index）
統計數據表明，二詞短語在短語中所占比例最大，因此針對二詞短語提供快速查詢，能解決短語查詢的問題。但是這樣做的話倒排列表個數會發生爆炸性增長。雙詞索引的數據結構如下圖：
由圖可知，內存中包含兩個詞典，分別是”首詞“和”下詞“詞典，”首詞“詞典有指向”下詞“詞典某個位置的指針，”下詞“詞典存儲了緊跟在”首詞“詞典的常用短語的第2個單詞，”下詞“詞典的指針指向包含這個短語的倒排列表。比如”我的“這個短語，其倒排列表包含文檔5和7，”的父親“這個短語，其倒排列表包含文檔5，其余詞典也是類似的含義。
對于查詢，用戶輸入”我的父親“進行查詢，搜索引擎將其進行分詞得到”我的“和”的父親“兩個短語，然后分別查找詞典信息，發現包含”我的“這個短語的是文檔5和文檔7，而包含”的父親“這個短語的有文檔5。查看其對應的出現位置，可以知道文檔5是符合條件的搜索結果，這樣就完成了對短語查詢的支持。
雙詞索引會使得索引急劇增大，一般實現并非對所有單詞都建立雙詞索引，而是只對計算代價高的短語建立雙詞索引。
短語索引（Phrase Index）
直接在詞典中加入多次短語并維護短語的倒排列表。缺點就是不可能事先將所有短語都建好索引。通用做法就是挖掘出熱門短語。下圖是加入短語索引后的整體索引結構：
對于查詢，當搜索引擎接收到用戶查詢后，現在短語索引里查找，如果找到，則計算后返回給用戶搜索結果，否則仍然利用常規索引進行查詢處理。
混合方法
將三者結合起來，接收到用戶查詢后，系統首先在短語索引中查找，如果找到則返回結果，否則在雙詞索引中查找，如果找到則返回結果，否則從常規索引中對短語進行處理，充分發揮各自的優勢。3種方式的混合索引結構如下圖所示：
短語查詢用來對熱門短語和高頻短語進行索引，雙詞索引對包含停用詞等高代價短語進行索引。
對于查詢，系統首先在短語索引中查找，如果找到則返回結果，否則在雙詞索引中查找，如果找到則返回結果，否則從常規索引中對短語進行處理，這樣就充分發揮各自的優勢。
分布式索引（Parallel Indexing）
當搜索引擎需要處理的文檔集合太多的時候，就需要考慮分布式解決方案。每臺機器維護整個索引的一部分，有多臺機器協作來完成索引的建立和對查詢的響應。
按文檔劃分（Document Paritioning）
將整個文檔集合切割成若干個子集合，而每臺機器負責對某個文檔子集合建立索引，并響應查詢請求。按文檔劃分示意圖如下：
工作原理：查詢分發服務器接收到用戶查詢請求后，將查詢廣播給所有索引服務器。每個索引服務器負責部分文檔子集合的索引維護和查詢響應。當索引服務器接收到用戶查詢后，計算相關文檔，并將得分最高的K個文檔送返查詢分發服務器。查詢分發服務器綜合各個索引服務器的搜索結果后，合并搜索結果，將得分最高的m個文檔作為最終搜索結果返回給用戶。
按單詞劃分（Term Paritioning）
每個索引服務器負責詞典中部分單詞的倒排列表的建立和維護。按單詞劃分示意圖如下：
工作原理：一次一個單詞。假設查詢包含A、B、C三個單詞，查詢服務器接收到查詢后，將查詢轉發到包含單詞A倒排列表的索引服務器節點1，索引服務器節點1提取A的倒排列表，并累計計算搜索結果的中間的分，然后將查詢和中間結果傳遞給包含單詞B倒排列表的索引服務器節點，索引服務器節點2也是類似處理，并繼續到索引服務器節點3。然后將最終結果返回給查詢分發服務器，查詢分發服務器計算得分最高的K個文檔作為搜索結果輸出。
兩種方案比較
按文檔比較常用，按單詞劃分只在特殊應用場合才使用。
按單詞劃分的不足：
可擴展性
搜索引擎處理的文檔是經常變動的。如果按文檔來對索引劃分，只需要增加索引服務器，操作起來很方便。但如果是按單詞進行索引劃分，則對幾乎所有的索引服務器都有直接影響，因為新增文檔可能包含所有詞典單詞，即需要對每個單詞的倒排列表進行更新，實現起來相對復雜。
負載均衡
常用單詞的倒排列表非常龐大，可能會達到幾十M大小。如果按文檔劃分，這種單詞的倒排列表會比較均勻地分布在不同的索引服務器上，而按單詞進行索引劃分，某個常見單詞的倒排列表全部內容都由一臺索引服務器維護。如果該單詞同時是一個流行詞匯，那么該服務器會成為負載過大的性能瓶頸。
容錯性
假設某臺服務器出現故障。如果按文檔進行劃分，那么只影響部分文檔子集合，其他索引服務器仍然能響應。但如果按單詞進行劃分，若索引服務器發生故障，則某些單詞的倒排列表無法訪問，用戶查詢這些單詞的時候，會發現沒有搜索結果，直接影響用戶體驗。
對查詢處理方式的支持
按單詞進行索引一次只能查詢一個單詞，而按文檔劃分的不受此限制。
總結
通過了解搜索引擎使用的數據結構和算法，對其工作原理有了進一步的認識。對于sphinx來說，在線上環境可以考慮增量索引和一次全量索引結合達到實時性的效果。
?
轉自：https://www.cnblogs.com/hoohack/p/5462884.html
轉載于:https://www.cnblogs.com/itplay/p/10940630.html
總結
以上是生活随笔為你收集整理的【搜索引擎】全文索引数据结构和算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 18.linux日志收集数据到hdfs上
- 下一篇： 配置https域名