按照不同劃分標準，索引有多種分類方式，僅常用類型也不止4種之多，而其中最為關鍵的則是“倒排索引”技術。
本文就是壹篇，介紹“倒排索引創建方法”的文章。
單詞—文檔矩陣
表達兩者包含關系的概念模型；
文檔
文本形式的存儲對象，包括Word、PDF、html、XML等不同格式的文件，以及短信、微博等內容；
文檔集合
若幹文檔的集合，如海量網頁、大量電子郵件等；
文檔編號
搜索引擎內部的文檔集合中，每個文檔所被賦予的區別於其他文檔的唯壹的內部編號，常用DocID表示；
單詞
搜索引擎的索引單位；
單詞詞典
文檔集合中出現過的所有單詞構成的字符串集合；記載著某個單詞對應的倒排列表在倒排文件中的位置信息；
單詞編號
搜索引擎內部的單詞詞典中，每個單詞所被賦予的區別於其他單詞的唯壹內部編號；
倒排列表
記載“出現過某個單詞的所有文檔列表”及“文檔中單詞位置信息”的倒排項的集合；
倒排文件
順序存儲所有單詞的倒排列表的物理文件；
倒排索引
由單詞詞典和倒排文件組成的，實現單詞—文檔矩陣的壹種具體存儲形式，是單詞到文檔映射關系的最佳實現方式（可以根據單詞快速獲取包含該單詞的文檔列表）。
比如，針對如下文檔集合
建立倒排索引的步驟：
1、用分詞系統將文檔自動切分成單詞序列，每個文檔就轉換為由單詞序列構成的數據流；
2、對每個不同單詞賦予唯壹的單詞編號（ID），並記錄每個單詞對應的文檔頻率（文檔集合中，包含某個單詞的文檔數量，占文檔總數量的比率）、包含該單詞的對應文檔編號（DocID）、該單詞在各對應文檔中的詞頻（TF）（在某個文檔中出現的次數）、該單詞出現在某個文檔中的位置（POS）等；
3、得到的倒排索引結果如下：
含義解讀：以單詞“跳槽”為例，其單詞編號為4，文檔頻率為2，代表整個文檔集合中有兩個文檔包含這個單詞，對應的倒排列表為｛（1；1；<4>）,（4;1;<4>）｝,其含義為在文檔1和文檔4中出現過這個單詞，單詞頻率都為1，單詞“跳槽”出現在兩個文檔中的位置都是4，即文檔中第四個單詞是“跳槽”。
單詞詞典
記載著某個單詞對應的倒排列表在倒排文件中的位置信息，支持搜索中基於查詢詞的倒排列表呈現。
對於包含成千上萬個單詞的大文檔集合來說，需要“基於高效數據結構”的詞典構建和查找方式，“哈希加鏈表”和“樹形詞典”就是這類數據結構的代表。
A.?哈希加鏈表詞典結構
哈希加鏈表：由“哈希表”及“沖突鏈表”組成，其中哈希表是主體。每個哈希表保存壹個指針，指向沖突鏈表；每個沖突鏈表，由相同哈希值的單詞組成；而有相同哈希值的壹組單詞，被稱作壹次沖突。
詞典建立過程：首先，對解析新文檔過程中出現的單詞T，利用哈希函數獲得哈希值；然後，根據哈希值，讀取對應的哈希表中的指針，並根據指針指向找到對應的沖突鏈表，而對沖突鏈表中不存在的單詞，將其作為首次出現單詞做“加入沖突鏈表”處理。隨著文檔解析完畢，相應的詞典便構建起來。
查詢響應過程：與詞典建立過程類似，區別在於，對於詞典中未包含單詞不做添加處理。
B.?樹形詞典結構
樹形詞典結構（又叫B樹或B+樹），由中間節點和最底層葉子節點構成，是壹種高效的層級查詢結構。
它需要字典項按照大小排序，中間節點指出壹定順序範圍的詞典項目存儲在哪個子樹中，根據詞典項比較大小進行導航；最底層葉子節點存儲單詞地址信息，根據地址便可以提取單詞字符串。
倒排列表
我們上面講了，倒排列表是倒排索引項（“某個單詞-文檔”的壹維矩陣）的集合，存儲著所有單詞，及包含每個單詞的相關文檔編號、詞頻、位置等信息。
而在實際搜索引擎中，為了便於壓縮，常以文檔編號差值（D-Gap）（倒排列表中相鄰兩個倒排索引項文檔編號的差值）取代實際的文檔編號，以保證倒排列表中後出現文檔編號大於前者。因此，文檔編號差值常是大於0的整數，比如，對應原始文檔編號 187、196、199，其編號差值可能為 187、9、3。
1、兩遍文檔遍歷法
兩遍文檔遍歷，即為兩遍文檔掃描，創建過程完全依賴在內存中進行。
第壹遍文檔遍歷
第壹遍掃描旨有兩個作用：首先，獲取全局的統計數據（文檔集合包含的文檔個數N，文檔集合包含的不同單詞個數M、每個單詞在多少個文檔中出現過的信息DF、所有單詞DF值相加得到的所需內存大小），據以分配存儲空間；其次，建立單詞對應倒排列表在內存中的位置信息（根據每個單詞的DF值，將存儲區劃分成不同大小的片段，不同的單詞通過指針對應著其所屬內存片段的起始和終止位置）。
第壹遍掃描之後，便為第二次掃描做好了資源準備工作。
第二遍文檔遍歷
第二遍文檔遍歷正式建立每個單詞的倒排列表信息，掃描結束的同時，所分配的內存空間也正好被填滿。每個單詞對應的內存片段，此時已被創建成該單詞的倒排列表。
兩遍掃描，便可完成索引建立，並將內存的倒排列表和詞典信息寫入磁盤。
優缺點：完全依賴內存，要求內存空間足夠大；從磁盤讀取和解析文檔耗時較長，速度慢。
2、排序法
壹種“在索引建立過程中，始終在內存分配固定大小的空間，用來存放詞典信息和索引中間結果，當分配空間被消耗殆盡，把中間結果寫入磁盤，並清空內存做新壹輪中間索引存儲”的方法，是兩遍遍歷索引的改進。
中間結果內存排序
a.讀入文檔，賦予唯壹的文檔ID；
b.解析文檔內容，賦予文檔中出現的單詞以唯壹的單詞ID（首次出現的單詞，賦予ID後做插入處理）；
c.為每個單詞建立包含“單詞ID”、“文檔ID”、”單詞頻率”信息的倒排列表項，並將其追加進中間結果存儲區末尾；對所有文檔依次做以上處理，直到所有文檔被處理完畢。
d.隨著存儲中間結果的內存被逐漸占滿，對三元組中間結果進行排序，將各單詞對應的倒排索引項變成有序形式，並將排好序的倒排列表寫入磁盤。排序原則：主鍵是單詞ID，即先按單詞ID從小到大排序；次鍵是文檔ID, 即相同單詞ID下，按文檔ID從小到大排序。
e.循環以上處理過程，待所有文檔被處理完畢，合並磁盤中每輪產生的中間結果文件。
中間結果文件合並
將存放中間結果的各緩沖區的有序數據，按單詞ID順序合並形成倒排列表寫入最終索引，同時清空各緩沖區並進行新壹輪三元組讀入操作，待所有中間結果文件被讀入緩沖區合並完成，最終索引文件便得以生成。
優缺點：只對中間結果做寫入磁盤操作，詞典信息始終在內存中維護，隨著內存被不斷占用，後續中間結果可用內存會越來越少。
3、歸並法
歸並法，是排序法的改進，每次將內存數據寫入磁盤時，包括詞典在內的中間結果信息也被寫入磁盤，以達到清空內存並為後續處理建立定額內存的目的。
子倒排索引
對目前所處理的文檔子集單獨在內存中建立壹整套的倒排索引；
將倒排索引寫入臨時文件
內存被占滿時，按照“詞典在前，倒排列表在後”的順序，將已建立的壹整套倒排索引寫入臨時文件，並清空內存。
合並部分倒排列表
合並每個單詞對應的部分倒排列表，形成單詞的最終倒排列表；同時，在合並過程中形成最終的詞典。