索引的建立和更新

索引的建立

前一總結里說到，如果索引結構建立好了，可以提高搜索的速度，那么給定一個文檔集合，索引是如何建立起來的呢？建立索引的方式有很多種，在這里我就書中提到的三種方法簡單總結一下。

兩遍文檔遍歷法

• 第一次文檔遍歷

第一次掃描文檔集合時，并沒有立即開始建立索引，而是收集一些的統計信息，比如文檔集合包含的文檔個數N、文檔集合內包含的不同單詞個數M以及每個單詞在哪些文檔中出現過的信息DF等等。將所有單詞對應的DF值全部相加，就可以知道建立最終的索引需要多少內存了，然后在內存中將連續存儲區劃分成不同大小的片段，詞典內某個單詞根據自己對應的DF信息，可以通過指針指向屬于自己的內存片段的起始位置和終止位置 ， 這樣在第二遍掃描中，這個單詞對應的倒排列表信息會被填充進這個片段中。

• 第二次文檔遍歷

這一次掃描的時候，就開始真正建立每個單詞的倒排列表信息了，即對每個單詞來說，獲得包含這個單詞的每個文檔的文檔ID，以及這個單詞在文檔中出現的次數，這樣就可以不斷填充第一次遍歷掃描所分配的內存空間。當然，如果要記錄單詞在文檔中出現的位置也是可以的，第一次掃描中分配內存時加上這個位置信息就可以了。

值得注意的是：此方法完全是在內存里完成索引的創建過程的，而后面兩種方法則是通過內存和磁盤相互配合來完成索引建立任務的。而正因為創建索引是在內存中完成的，所以就要求內存一定要足夠大，否則文檔集合太大的話，內存不能夠滿足需求。而對文檔集合進行兩遍掃描，所以從速度上相比后面兩種方法不占優勢。

排序法

排序法在建立索引的過程中，始終在內存中分配固定大小的空間用來存放詞典信息和索引的中間結果，當分配的空間被消耗光的時候，把中間結果寫入磁盤，清空內存里中間結果所占的空間，以用作下一輪存放索引中間結果的存儲區。這種情況下，可以把內存看做驛站，它只是一個中間轉折點。這種方法分為兩個步驟：中間結果內存排序和合并中間結果。

為什么要進行排序呢？主要是為了方便后續的處理。因為在形成中間結果文件前，已經按照單詞ID和文檔ID進行了排序，所以進入內存緩沖區的數據都是已經排好序的，合并過程中，將不同緩沖區中包含同一個單詞ID的信息進行合并，如果某個單詞ID的所有信息全部合并完成，那么說明這個單詞的倒排列表已經構建完成了，將其寫入最終索引中，同時將各個緩沖區中對應這個單詞ID信息清空。就這樣一直往下進行，直到所有的單詞ID對應的倒排列表都已經創建完成。最后的結果，就是最終的索引文件。

歸并法

由于排序法有一個不足之處，那就是在將中間結果寫入磁盤的時候，詞典信息一直在內存中進行維護，這樣也會占據一部分的內存。歸并法就是對排序法做出了改進，即每次將內存中數據寫入磁盤時，包括詞典在內的所有中間結果信息都被寫入磁盤，這樣內存所有內容都可以被清空。

歸并法整體流程也是分為兩個大的階段，首先在內存里維護中間結果，當內存占滿時，將內存數據寫入磁盤臨時文件，第二階段對臨時文件進行歸并形成最終索引。

歸并法和排序法的區別

首先，排序法在內存中存放的是詞典信息和三元組數據（單詞ID，文檔ID，單詞頻率），在建立索引的過程中，詞典和三元組數據并沒有直接的聯系，詞典只是為了將單詞映射為單詞ID。而歸并法則是在內存中建立一個完整的內存索引結構，相當于對目前處理的文檔子集建立起了一個倒排索引。

其次，在將中間結果寫入磁盤臨時文件時，歸并法將整個內存的倒排索引寫入臨時文件，對于某個單詞的倒排列表在寫入磁盤文件時，將詞典項放在列表最前端，之后跟隨相應的倒排列表，這樣依次將單詞和對應的倒排列表寫入磁盤文件，隨后徹底清空所占內存。而排序法只是將三元組數據排序后寫入磁盤文件，詞典作為一個映射表一直存儲在內存中。

在最后合并為最終索引的過程中，排序法是根據同一單詞ID的這樣三元組依次進行合并，歸并法的臨時文件則是每個單詞對應的部分倒排列表，所以在合并時針對每個單詞的倒排列表進行合并，形成這個單詞的最終倒排列表就可以了，與此同時，最后的合并過程中也會形成最終的詞典信息。如果大家對算法里的歸并排序有所了解的話，就很清楚這種方法了吧。

?

索引更新策略

常用的索引更新策略有4種：完全重建策略、再合并策略、原地更新策略以及混合策略。

完全重建策略：很直觀的方法，當新增文檔達到一個數量時，將新增文檔和原先的老文檔進行合并，然后利用上文提到的建立索引的方式，對所有文檔重新建立索引。

再合并策略：有新增文檔進入搜索系統時，搜索系統在內存維護臨時倒排索引來記錄信息，當新增文檔達到一定數量的時候，則把臨時索引文件和老文檔的倒排索引文件進行合并，以生成新的索引。

原地更新策略：在索引合并時，并不生成新的索引文件，而是直接在原先的索引文件里進行追加操作，將增量索引里單詞的倒排列表項追加到老索引對應的倒排列表項的末尾，這樣的話，就只更新增量索引里出現的單詞相關信息，其他單詞信息不做變動。

混合策略：結合不同索引更新策略的優勢，將不同的索引更新策略混合以形成更高效的方法。

混合策略一般會將單詞根據其不同性質進行分類，不同類別的單詞，對其索引采取不同的索引更新策略。常見的做法是：根據單詞的倒排列表長度進行劃分，因為有些單詞經常在不同文檔中出現，所以其對應的倒排列表就較長，而有些單詞很少見，其倒排列表就較短。那么長倒排列表單詞采取原地更新策略，因為這種策略能夠節省磁盤讀寫次數；而短倒排列表就采取再和并策略。通過這種根據實際情況來分別采取實際策略的方法，效果體現的比較顯著，磁盤的讀寫操作和各種策略的優勢都充分體現出來了。

轉載于:https://www.cnblogs.com/BaiYiShaoNian/p/4548817.html

總結

以上是生活随笔為你收集整理的这就是搜索引擎--读书笔记五--索引的建立与更新的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。