MG--索引構造

顧名思義這章就是要談怎樣構造索引的問題，或者說在有限記憶體和有限時間内，怎麼樣高效的對大資料集構造索引檔案。一旦有了這個索引檔案，那麼索引的壓縮，基于索引的排序，前面的章節都已經講過。

連結清單

先來看看最一般的方法，在記憶體中建構這樣的資料結構，包含一個term字典，這個字典本身可以用數組，hash表，二分查找樹來實作，字典中的每 項，都包含一個指向term的倒排清單的指針，那麼對于一個term的倒排清單一般用單項連結清單來實作，因為這個是動态的，就是說每一項包含文檔号，文檔内 頻率，和下一項指針。

然後周遊每一篇文檔，對于文檔中的每個term，在字典中如果有就直接把文檔号和頻率挂在這個term的倒排清單後面，如果沒有，先在字典中加上這個term，然後再挂。

當所有文檔都處理完了， 我們就在記憶體中儲存了一個完整的反向索引，最後一步就是把這個記憶體中的索引存儲到磁盤上的一個倒排檔案。

那麼這個方法，容易了解，又簡單看上去很好，但有個問題，就是如果對于大文檔集，那記憶體的消耗是很大的。

那麼時間換空間，你可以把連結清單緩存到資料庫，或虛拟記憶體上面去，當然這個方法不可行，因為效率太低，在index文檔時，需要先周遊倒排清單去找到每個term所對應的連結清單， 這種随機通路會有大量的磁盤讀寫。

基于排序的倒排

對于大文檔集的索引，在有限記憶體情況下，不可能把索引都放在記憶體裡，必然要放到磁盤上，那麼對于磁盤的問題是，随機通路的效率很低。是以如果所有索引項都是有序的存放在檔案中，那麼這樣順序的通路磁盤檔案還是比較高效的。

那麼什麼樣的資料結構适合在檔案中排序了，答案是三元組 <t, d, fd,t >

這樣在index文檔時就不用去周遊查找了， 三元組本身就記錄了所有的關系，當然三元組會造成資料備援，在每個三元組中都要保留termid

算法是這樣的：

1. 建立空的字典s，和一個磁盤上的臨時檔案

2. 周遊每一篇文檔，對文檔中的term，字典中沒有的話，加到字典中，有的話，讀出termid，組成三元組<t, d, fd,t >并存到臨時檔案中。

3. 開始排序，因為記憶體有限不可能把所有三元組都讀進來排序，是以要分段排序

就是每次讀入記憶體能夠容納的k條三元組，按termid升序排序，termid相同的，就按docid升序排序

那麼這排序後的k條三元組就是一個有序段(sorted run)

然後将有序段寫回臨時檔案

這樣不斷的讀入直到全部處理完

4. 現在的狀況就是臨時檔案裡面都是有序段，那麼下面要做的就是merge，如果初始有r個有序段，那麼通過logr趟(pass)merge，生成最終的有序段，即排序完成，這是個标準的外排序的做法。

5. 最後将這個臨時檔案順序讀出來生成最終的壓縮倒排檔案，完成後可删掉臨時檔案。

這個方法的好處就是一直是順序讀磁盤，沒有那種需要查找周遊的随機通路。但有個問題就是會耗費比較多的磁盤，因為你在做兩段merge的時候，merge的結果必須存到一個新的臨時檔案中，就是峰值需要超過原始檔案2倍的磁盤空間。

索引壓縮

前面說了，基于排序的倒排要耗費過多的磁盤資源， 是以下面要談的是，怎麼在建立倒排檔案時盡量減少磁盤資源的耗費。

壓縮臨時檔案

臨時檔案裡面都是存放了三元組 <t, d, fd,t >，對于 d, fd,t 的壓縮前面在索引壓縮時候就談過，方法很多

那麼就來看看t的壓縮

在每個有序歸并段中，t值是非減的，是以選擇差分編碼是自然的選擇，就是記錄這個t和前一個的內插補點，這個t-gap是零或大于零的整數。

可以直接用一進制編碼來進行編碼，那麼可以想象的出，這樣存儲t所需的空間是很小的

可以看出想要有比較好的壓縮效果，必須對有序段做壓縮，上面的算法改成這樣

對于2，3合并為

周遊每篇文檔，取出term組成三元組<t, d, fd,t >這裡不直接存到臨時檔案，先存在記憶體中，當記憶體中存放的三元組條數達到k時，對這k條三元組進行排序，然後壓縮，最後把這個壓縮過的有序段寫入臨時檔案。

4.因為有序段時壓縮編碼過的，是以在并歸的時候要先解碼，并歸完再壓縮編碼，寫回臨時檔案

原地多路并歸

并歸階段是處理器密集型，而不是磁盤密集型， 是以使用多路并歸可以進一步降低倒排時間。

推廣一下， 假定目前全部的r個并歸段進行r路并歸，先要從每個并歸段讀入一個b位元組的塊，這個b的大小取決于記憶體大小，這個塊是每個并歸段的buffer，當一個并歸段的塊被讀完，則從磁盤上再讀入一塊。

r路并歸需要用到最小堆來從候選集合中有效的找到最小值。

那麼不斷的從堆頂取到最小值寫入新的臨時檔案中， 直到最後完成排序。那麼這樣我們還是需要2倍原始檔案的磁盤耗費，能不能進行原地并歸了，下面就介紹一下原地多路并歸算法，這個算法比較複雜，也挺有意思

原地并歸，就是不占用更多的磁盤空間，并歸完後還是寫回原臨時檔案，而不用寫入新的臨時檔案，為達到這個目的有幾點是需要認真考慮的

1. 要進行r路并歸，會先從每個并歸段讀入b位元組的塊到記憶體，那麼容易想到我們隻要把排序的結果也組成b位元組的塊，就可以覆寫到這些已被讀過的塊空間上，實作原地并歸。

問題是每個并歸塊不一定是b的整數倍，最後讀出的一個塊可能會小于b，那麼這樣這個不規則的塊會給這個算法帶來困擾，那麼這個的解決辦法很簡單，就是padding，對每個并歸段後面加上padding，使他一定為b的整數倍。

2. 按上面的說法，我們把排好序的塊寫回被讀過的空塊中，有個問題是這些空塊是零散的，無序的。是以我們需要一個快表block table來記錄塊的順序，如block_table[1]表示目前臨時檔案中的第一塊實際的塊順序是多少，比如block_table[1]＝3，表示 現在放第一塊的應該移到第三塊。

那麼是以最後我們還要根據block table對臨時檔案進行重排，以恢複原來的順序，這個算法是可以線上性時間裡完成的

算法如下，算法的目的就是滿足block_table[i]＝i，

從1到n周遊塊表，如果block_table[i] 設為k不等于i, 說明臨時檔案第i塊裡面放的不是真正順序上的第i塊，

那麼做法是，把目前的第i塊放到緩存中，然後去找block_table[j]＝i，就是找出順序上的第i塊，放到i位置上

現在第j塊空出來了， 看一下k是否等于j，如果等于正好放到j位置上

如果不等于，繼續去找block_table[s]＝j，放到j位置上，這樣一直找下去，直到block_table[k]，可以把緩存中的第k塊放進去。

當周遊一遍，保證從1到n塊都滿足block_table[i]＝i，則重排完成。

3. b值大小的選取，如果b值選的過大會導緻記憶體中放不下r+1個b塊，選的過小會耗費過多的磁盤讀寫次數。

做法是給b一個2的幂形式的初值，這樣當b過大時，友善b/2來折半，而且這種方法保證歸并段仍然是新的b值的倍數。

那麼具體做法就是當b*(r+1) > m時，set b ＝ b/2

那麼給出原地并歸的完整算法，

1. 初始化

    建立空字典s

    建立空臨時檔案

    設 l為字典占的空間大小

    設 k =(m -l)/w, k為并歸段包含三元組的個數，w為一個三元組 <t, d, fd,t >所占用的空間

    設 b ＝ 50kb

    設 r ＝0， r為并歸段的個數

2. 處理文檔和生成臨時檔案

    周遊每一篇文檔d

          parse文檔成term

          對于每個term

                如果term在s中存在，取出termid

                在s中不存在

                     把term加到s中

                     更新l，k （因為字典s變大，使可用記憶體變小，是以k會變小）

                把<t, d, fd,t >加到triple數組中

           任何時候，當triple數組中的triple個數達到k時，生成一個并歸段

                 對并歸段按term進行排序

                 對各個field進行壓縮

                 最後對并歸段進行padding，保證是b的倍數，寫入臨時檔案

                 r = r+1

                 當b*(r+1) > m時，set b ＝ b/2

3. 并歸

    從每個并歸段讀入一塊，在這些塊的number加到freelist裡面， 就是說這些塊讀過了，可以被輸出塊覆寫

    從每個塊取一個triple，共r個triple，建最小堆

    不斷取堆頂triple， 放到輸出塊中， 并從相應的塊中取新的triple加到堆中

    當輸出塊滿的時候，從freelist中找一個空的塊，如果沒有空的，就建立一個新的塊append到臨時檔案後。

    把輸出塊寫入這個空塊，更新freelist和block table

    同時當每個并歸段讀入的塊耗完的時候，再讀相應并歸段的next block，并更新freelist

4. 臨時檔案重排

5. truncate 并釋放尾部無用的空間

壓縮的記憶體内倒排

現在把基于排序的倒排方法放在一邊， 回到前面提到的記憶體内的鍊結清單方法，這種方法結合壓縮技術也可以達到比較好的效果。

現在将要描述的這個方法，基于一個假設就是，每個術語t的文檔頻率ft 在倒排前已知。 當然想要已知，實作中，就是先周遊統計一遍，第二遍再來建立倒排。

那麼費這個勁去預先統計術語t的文檔頻率ft 有什麼好處嗎

a. 之前每個term的倒排清單都是用單向連結清單的結構來實作，因為你不知道到底有多少文檔，必須動态的；那麼現在你知道文檔頻率，那麼就可以确切知道需要配置設定多少空間了，可以用數組來代替單項連結清單，那麼至少可以省下這個next指針的耗費。

b. 知道文檔的總數n，那麼文檔編号可以用logn位去編碼，而不用整型大小32位

c. 同樣知道最大的文檔内頻率m，也可以用logm位編碼fd,t

總之就是說，事先知道一些資訊，可以減少資料編碼的可能性，也就是說資訊熵變小，是以用于編碼的位數也就會變小，進而節省了空間。

當然這樣做對于記憶體的占用還是很大，那麼又有底下兩種方法，來減少記憶體的消耗

基于字典的切分

基于文本的切分

原理就是把全部倒排清單放記憶體裡面太大，那麼就把建倒排的任務分成若幹個小任務，每次在記憶體裡面隻保留倒排的一部分

基于字典的切分，就是每次隻建立和部分term相關的倒排，分多趟覆寫整個字典。

基于文本的切分，就是每次隻建立部分文本的倒排，分多趟覆寫整個文本集。

本文章摘自部落格園，原文釋出日期：2011-07-04