鑽石舞台

點擊上方「Java基基」，選擇「設為星標」

做積極的人，而不是積極廢人！

每天14:00更新文章，每天掉億點點頭髮...

搜索引擎的索引其實是實現<關鍵詞，文檔>映射的具體的數據結構 ，其實現方式也是多種多樣的：倒排索引、簽名文件以及後綴樹等等 。實驗證明倒排索引 是最有效的實現方式，同時也是當前搜索引擎廣泛應用的索引技術。

基於 Spring Boot + MyBatis Plus + Vue & Element 實現的後台管理系統 + 用戶小程序，支持 RBAC 動態權限、多租戶、數據權限、工作流、三方登錄、支付、短信、商城等功能

平常我們想要查詢一個關鍵詞，最簡單的思路肯定是挨個每個文檔查看這個文檔是否存在這個關鍵詞，這就是建立<文檔，關鍵詞>這樣映射的索引。詳情圖示如下，大概解釋一下，這裡的網頁A中假設就是這篇博客，後面跟的是這篇博客中的關鍵詞。

這樣我們想查找索引 這個關鍵詞的時候，我們就需要先查網頁A，然後對它的關鍵詞一個個遍歷，直到遍歷完所有的網頁。這樣的過程時間複雜度是O(n2)，即便後面的關鍵詞列表我們用的是紅黑樹等高級數據結構，那樣最快的時間複雜度則是O(nlogn)。這樣的技術應用在搜索引擎這種特別依賴反應時間來滿足用戶需求的應用上就顯得非常吃力，這也是為什麼要採取倒排索引 的原因。倒排索引會建立<關鍵詞，文檔> 的映射，如下圖所示：

這樣我們想要搜索關鍵詞的時候，只需要經過一遍O(n)的過程就能得到我們想要的答案。如果用更好的數據結構且不在乎價格的話，甚至可以直接用哈希得到O(1)的效果。而實際上的數據結構可能並不是圖示這樣，其一般會採用這樣的數據結構：

可以看到，我們這裡多加了word_count_以及word_index_這兩個變量，這是因為文檔中單詞的頻率信息是在計算網頁相關度中非常重要的一個指標。而詞彙出現的位置對於短語查詢來說非常有用，這兩個都會在後面的博客中進行介紹。

注 ：實際上並不村存儲倒排索引項中實際文檔編號，而是代之以文檔編號的差值，這樣的目的其實是省空間，更好的進行數據的壓縮。

單詞詞典是倒排索引中非常重要的組成部分，其用來維護文檔集合中出現的所有單詞的相關信息。實現方式多種多樣，常有的就是哈希+鍊表、B+樹、紅黑樹等等。

在搜索引擎的應用中，網頁往往不是靜態的，其會是動態變化的。搜索引擎為了滿足這種動態變化的需求就不得不使用三個工具：倒排索引、臨時索引和已刪除文檔列表。

當搜索引擎系統發現有新的文檔被爬蟲下載，會先將其加入臨時索引中；如果有文檔被刪除，則將其加入刪除文檔隊列；文檔被更改的話，將原來的文檔加入刪除文檔隊列，更改後的文檔加入臨時文檔隊列。

如果是用戶的查詢請求的話，就會從臨時隊列和倒排索引中都進行查詢，對兩個結果進行合併，之後再查詢刪除文檔隊列，進行一個文檔過濾。

這個方法需要對文檔集合進行兩遍掃描。第一遍掃描的時候，並沒有立即開始創建索引，而是先收集一些全局的統計信息：網頁集合中網頁個數WebPageNum、網頁集合內包含的單詞數量WordCount，每個單詞在多少文檔中出現過的次數DF。得到這些信息的目的是為了知道我們需要開闢多大的內存，需要什麼資源 。

第二遍遍歷就是真正建立倒排索引的時候，我們先會獲取包含這個單詞的每個文檔的文檔ID，以及這個單詞在文檔中出現的次數。不斷重複這個過程，知道填滿我們申請的內存空間。

兩遍文檔遍曆法是非常消耗IO資源的，所以我們往往採用在內存中去構建索引，這要求我們要有錢整個大的內存。

歸併法是兩遍文檔遍曆法的改進，該方法在建立索引的過程中，始終在內存中分配固定大小的空間，用來存放詞典信息和所以對中間結果，當分配的空間被消耗光的時候，就把中間寫過寫入磁盤，和磁盤中間的結果進行合併。這樣內存就可以反覆復用，比較省錢。

像在內存中維護的索引往往都會到達內存的上線，這個時候我們就要考慮把索引合併到磁盤上，以釋放內存空間容納新的電腦。常用的更新策略如下：

基於 Spring Cloud Alibaba + Gateway + Nacos + RocketMQ + Vue & Element 實現的後台管理系統 + 用戶小程序，支持 RBAC 動態權限、多租戶、數據權限、工作流、三方登錄、支付、短信、商城等功能

在搜索引擎實際應用中，由於網頁中是有一定結構的：標題，引用，正文等等。如果說平常索引是判斷此文檔是否出現過關鍵詞，那麼多索引是判斷此關鍵詞是在文檔的哪一部分出現。而對於這種多字段類型的文檔，搜索引擎實現方式主要有以下幾種：

多索引方式 ：其針對每個不同的字段，分別建立一個索引，當用戶指定某個字段作為搜索範圍的時候，可以從相應的索引中提取結果；當用戶沒有指定特定字段的時候，搜索引擎會對所有字段都進行查找併合並多個字段的相關性得分，根據得分給出搜索結構。

倒排列表 ：假設文檔包含三個字段：標題、引用、正文。那麼我們可以用三個比特位進行標識，這樣就會形成如下圖的倒排索引結構，這裡每個倒排索引項格式如此<DocumentID，WordCount，Filed，Position>，那麼第一項就可以表示關鍵詞索引在198號文檔中出現了兩次，位置是引用和正文兩個位置。

擴展列表方式 ：這個是實際中用的比較多的多字段索引方式，其為每個字段建立一個擴展列表。而倒排索引項會記錄<DocumentID，WordCount，Position>這麼一個三元關係，但是其還包含多個個擴展項中，其中記錄<DocumentID，FIledRange>這麼一個關係，具體如下：假設我們搜索關鍵詞索引，這個時候根據倒排列表項，我們知道在198號文檔中出現了兩次，一次在2號位置，一次在10號位置。根據標題擴展列表，我們知道標題返回是1號~6號位置，那麼2號位置在標題中。根據正文擴展列表，我們知道10號位置是正文部分，這樣就達到了多索引的目的。雖然這種方式可能有兩次查詢的過程，但是它可以服用單索引，這也是常用的原因。

歡迎加入我的知識星球，一起探討架構，交流源碼。加入方式，長按下方二維碼噢：

已在知識星球更新源碼解析如下：