搜索引擎原理（二）索引（1）

索引是資料庫中非常常用的技術之一，使用索引可以大幅提升系統效率。

在搜索引擎中，索引更是最重要的核心技術。在處理海量文本時，索引起到了非常重要的作用。

索引的內容比較多，所以會分兩篇文章闡述。

目錄：

搜索引擎原理（二）索引（1）

搜索引擎原理（二）索引（2）

本文主要包含以下內容：

1. 索引基礎
1. 單詞－文檔矩陣
2. 倒排索引概念及實例
2. 哈希鏈表
3. 樹形結構
4. 倒排列表
5. 建立索引
1. 兩遍文檔遍曆法
2. 排序法
3. 歸併法
6. 動態索引

索引基礎

單詞-文檔矩陣

單詞-文檔矩陣是單詞和文檔之間包含關係的概念模型，如（圖1）所示，每列代表一個文檔，每行代表一個單詞，打對勾的位置代表包含關係。

搜索引擎的索引實際上就是實現上述結構，只是實現的方式多有不同，如倒排索引、簽名文件、後綴樹等方式。目前的實踐表明，倒排索引是最佳的實現方式。

倒排索引

倒排索引包括以下這些概念：

• 文檔（Document）：文本格式，如Word、PDF、HTML、XML等。
• 文檔集合（Document Collection）：由若干文檔構成的集合成為文檔集合。比如海量互聯網網頁或大量的電子郵件。
• 文檔編號（Document ID）：為每一個文檔賦予的唯一一個內部編號，就像資料庫中的主鍵。
• 單詞編號（Word ID）：為某個單詞賦予的唯一編號。
• 倒排索引（Inverted Index）：倒排索引是實現單詞－文檔矩陣的一種具體存儲形式。通過倒排索引，可以根據單詞快速獲取包含這個單詞的文檔列表。
• 單詞詞典（Lexicon）：搜索引擎的索引單位是單詞，所以單詞詞典是所有單詞的字元串集合。
• 倒排列表（PostingList）：倒排列表記錄了出現了某個單詞的所有文檔編號，根據倒排列表就能知道哪些文檔中包含哪些單詞。
• 倒排文件（Inverted File）：所有單詞的倒排列表都存儲在磁碟中的某個文件里，倒排文件是存儲倒排索引的物理文件。

倒排索引基本概念如下所示：

倒排索引簡單實例

倒排索引本質是十分簡單的，下面會一一個例子來說明。

這是一篇來自readhub的新聞，從中我們可以看到readhub將這些新聞做了聚合，一起輸出。假如我們為上述新聞依次編號（不考慮最後一篇英文）為（1，2，3，4，5），那麼會產生如圖4的倒排索引。

實際的倒排索引還可以包含更多信息，如圖5所示，包含了單詞對應的文檔頻率信息和在某個文檔出現的位置信息。

以單詞騰訊為例，其單詞編號為1，文檔頻率為5，代表有5篇文檔出現過這個詞。對應的倒排列表為(1;1;<0>),(2;1;0),(3;1;21),(4;1;0),(5;1;20)，代表在文檔1，2，3，4，5中都出現過這個單詞，單詞頻率都為1，但是位置有所不同。

圖5所示的倒排結構是一個比較完備的索引系統了，基本上搜索引擎的索引結構都是如此，只是實現的具體數據結構有所不同。

在用戶輸入「騰訊」時，搜索引擎可以根據這個索引很快的響應用戶的查詢，首先找出了包含騰訊這個詞的文檔，這些文檔就是提供給用戶的搜索結果，然後利用詞頻、文檔頻率等信息對搜索結果進行排序，計算文檔和查詢的相似性，按照相似性得分由高到低輸出，此即為搜索系統的內部流程，具體方案後續會有敘述。

單詞詞典

單詞詞典是倒排索引中非常重要的組成部分，它用來維護文檔集合中出現過的所有單詞的信息，同時用來記載某個單詞對應的倒排列表在倒排文件中的具體位置信息。

對於一個規模巨大的文檔集合，可能包含幾十萬甚至上百萬不同的單詞，能否快速定位直接影響了搜索引擎的檢索速度，常用的數據結構包括哈希加鏈表結構和樹形詞典結構。

哈希加鏈表結構

圖6是哈希加鏈表結構的示意圖。這種結構由兩部分組成，主體是哈希表，哈希表的值保存一個指針，指針指向衝突鏈表，在衝突鏈表中，相同哈希值的單詞形成鏈表結構。所謂衝突鏈表，就是指兩個不同的單詞獲得相同的哈希值，所以造成衝突。

在建立索引的過程中，詞典結構也會被構建出來。比如在解析一個新文檔的時候，對於某個在文檔中出現的單詞T，首先利用哈希函數獲得哈西值，之後根據哈希值讀取指針，也就是衝突鏈表。如果衝突鏈表中已經存在這個單詞，說明單詞在之前解析的文檔中就已經出現過；如果衝突鏈表中沒有發現這個單詞，說明是首次碰到，所以將其加到衝突鏈表中。通過這種方式，當文檔集合內所有文檔解析完畢時，相應的詞典結構就被構造出來了。

在響應查詢請求時，稍有不同。因為是查詢，所以不會有增加操作。僅僅是通過鏈表讀出對應的倒排列表來進行後續工作，如果沒有找到這個單詞則搜索結果為空。

樹形結構

B樹（或B+樹）是另一種高效查找結構，圖7是一個B樹結構示意圖。B樹與哈希方式查找不同，需要字典項能按照大小排序（數字或者字元序）。

B樹形成了層級查找結構，中間節點用於指出一定順序範圍的詞典項目存儲在哪個子樹中，起到根據詞典項比較大小進行導航的作用，最底層的葉子節點存儲單詞的地址信息，根據這個地址就可以提取出單詞字元串。

倒排列表

圖5中展示了一個比較完備的倒排列表，但在實際生產中，不存儲文檔標號，而是存儲文檔編號的差值，如圖8所示：

這樣能有效對數據進行壓縮，且無損。

建立索引

索引的建立有三種比較使用的方法

兩遍文檔遍曆法

顧名思義，這種方法就是對文檔集合進行量表掃描。這種方法在內存中完成索引的創建，而另外兩種是通過內存和磁碟相互配合完成。

第一遍文檔遍歷

第一遍文檔遍歷時，不建立索引，而是收集一些統計信息，比如文檔個數N，不同單詞個數M，每個單詞在文檔中出現的頻率DF。將所有單詞對應的DF相加，就可以知道建立最終索引需要的內存大小。

第二遍文檔遍歷

在第二遍掃描的時候，開始建立倒排列表信息，即獲得包含這個單詞的每個文檔的ID，以及這個單詞在文檔中的出現次數TF。

經過兩遍掃描後，即可將內存的倒排列表和詞典信息寫入磁碟。

由於要進行兩次遍歷，所以速度並不佔優，以下兩種方法在速度方面更好一些。

排序法

排序法就是進行一次掃描，分配固定的內存空間，當內存空間被消耗光時，把中間結果寫進磁碟，清空內存里中間結果所佔空間。

排序法的流程如下：

讀入文檔後，對文檔進行編號，賦予唯一的ID，並對內容進行解析。對於文檔中出現的單詞，通過查詞典將單詞轉換為對應的單詞ID。如果詞典中沒有這個單詞，則將其插入。在完成了由單詞映射為單詞ID的過程之後，可以對該文檔內每個單詞建立一個（單詞ID，文檔ID，單詞頻率）三元組，這個三元組就是單詞對應文檔的倒排列表項，然後將這個三元組插入到中間結果存儲區末尾，接著開始處理下一個文檔。

隨著文檔被處理完成，三元組集合所佔內存會越來越大，當分配的內存被用完時，可以對三元組進行排序。排序的原則是，主鍵是ID，次鍵是文檔ID，從小到大排序。通過以上方式，三元組變成有序方式。如圖9所示。

之所以要對三元組進行排序，是為了合併中間結果。

合併過程中，系統將不同緩存去中包含同一個單詞ID的三元組進行合併，如果某個單詞ID的所有三元組全部合併完成，說明這個單詞的倒排列表已經構建完成，則將其寫入最終索引中。當所有三元組合併完成後，就形成了索引文件。

歸併法

歸併法和排序法流程基本相同，但在具體實現上有較大差異。

1. 排序法使用詞典信息和三元素，歸併法是在內存中建立一個完整的內存索引系統，相當於對目前處理的文檔子集單獨在內存中建立起了一整套倒排索引，其和最終索引在形式和結構上是一樣的，區別是這個索引是部分索引而不是全部索引。
2. 寫入臨時文件時，歸併法會將整個內存寫入臨時文件。
3. 最終合併時，歸併法直接將每個單詞的倒排列表進行合併，沒有三元組的處理過程。

動態索引

動態索引指，索引的內容需要不停的變化。能夠應對新文檔的進入和舊文檔的刪除。

一般會再加兩個索引，一個是臨時索引，用來存儲新文檔。另一個是已刪除索引，用來存儲被刪除的舊文檔。

本篇文章到此就講完了，下一篇會闡述索引更新策略和查詢處理，見：搜索引擎原理（二）索引（2）

推薦閱讀：