概述
倒排索引在關係資料庫系統里，索引
是檢索數據最有效率的方式,。但對於搜尋引擎，它並不能滿足其特殊要求：
1）海量數據：搜尋引擎面對的是海量數據，像Google，百度這樣大型的商業搜尋引擎索引都是億級甚至百億級的網頁數量 ，面對如此海量數據 ,使得資料庫系統很難有效的管理。
2）數據操作簡單：搜尋引擎使用的數據操作簡單 ,一般而言 ,只需要增、 刪、 改、 查幾個功能 ,而且數據都有特定的格式 ,可以針對這些套用設計出簡單高效的應用程式。而一般的資料庫系統則支持大而全的功能 ,同時損失了速度和空間。最後 ,搜尋引擎面臨大量的用戶檢索需求 ,這要求搜尋引擎在檢索程式的設計上要分秒必爭 ,儘可能的將大運算量的工作在索引建立時完成 ,使檢索運算儘量的少。一般的資料庫系統很難承受如此大量的用戶請求 ,而且在檢索回響時間和檢索並發度上都不及我們專門設計的索引系統。
相關概念及定義
倒排列表
倒排索引倒排列表用來記錄有哪些文檔包含了某個單詞。一般在文檔集合里會有很多文檔包含某個單詞，每個文檔會記錄文檔編號（DocID），單詞在這個文檔中出現的次數（TF）及單詞在文檔中哪些位置出現過等信息，這樣與一個文檔相關的信息被稱做倒排索引項（Posting），包含這個單詞的一系列倒排索引項形成了列表結構，這就是某個單詞對應的倒排列表。右圖是倒排列表的示意圖，在文檔集合中出現過的所有單詞及其對應的倒排列表組成了倒排索引。
倒排索引在實際的搜尋引擎系統中，並不存儲倒排索引項中的實際文檔編號，而是代之以文檔編號差值（D-Gap）。文檔編號差值是倒排列表中相鄰的兩個倒排索引項文檔編號的差值，一般在索引構建過程中，可以保證倒排列表中後面出現的文檔編號大於之前出現的文檔編號，所以文檔編號差值總是大於0的整數。如圖2所示的例子中，原始的 3個文檔編號分別是187、196和199，通過編號差值計算，在實際存儲的時候就轉化成了：187、9、3。
之所以要對文檔編號進行差值計算，主要原因是為了更好地對數據進行壓縮，原始文檔編號一般都是大數值，通過差值計算，就有效地將大數值轉換為了小數值，而這有助於增加數據的壓縮率。
倒排索引
倒排索引倒排索引
（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜尋下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。通過倒排索引，可以根據單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：“單詞詞典”和“倒排檔案”。
倒排索引
有兩種不同的反向索引形式：
一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。
一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
後者的形式提供了更多的兼容性（比如短語搜尋），但是需要更多的時間和空間來創建。
現代搜尋引擎的索引
都是基於倒排索引。相比“簽名檔案”、“後綴樹”等索引結構，“倒排索引”是實現單詞到文檔映射關係的最佳實現方式和最有效的索引結構.
構建方法
簡單法
倒排索引索引的構建
相當於從正排表到倒排表的建立過程。當我們分析完網頁時 ,得到的是以網頁為主碼的索引表。當索引建立完成後 ,應得到倒排表 ,具體流程如圖所示：
流程描述如下：
1）將文檔分析稱單詞term標記，
2）使用hash去重單詞term
3）對單詞生成倒排列表
倒排列表就是文檔編號DocID，沒有包含其他的信息（如詞頻，單詞位置等），這就是簡單的索引。
這個簡單索引功能可以用於小數據，例如索引幾千個文檔。然而它有兩點限制：
1）需要有足夠的記憶體來存儲倒排表，對於搜尋引擎來說， 都是G級別數據，特別是當規模不斷擴大時 ,我們根本不可能提供這么多的記憶體。
2）算法是順序執行，不便於並行處理。
合併法
歸併法
,即每次將記憶體中數據寫入磁碟時，包括詞典在內的所有中間結果信息都被寫入磁碟，這樣記憶體所有內容都可以被清空，後續建立索引可以使用全部的定額記憶體。
歸併索引如圖 歸併示意圖：
合併流程：
1）頁面分析，生成臨時倒排數據索引A，B，當臨時倒排數據索引A，B占滿記憶體後，將記憶體索引A，B寫入臨時檔案生成臨時倒排檔案，
2) 對生成的多個臨時倒排檔案 ,執行多路歸併 ,輸出得到最終的倒排檔案 ( inverted file)。
合併流程索引創建過程中的頁面分析 ,特別是中文分詞為主要時間開銷。算法的第二步相對很快。這樣創建算法的最佳化集中在中文分詞效率上。
更新策略
更新策略有四種
：完全重建、再合併策略、原地更新策略以及混合策略。
完全重建策略：當新增文檔到達一定數量，將新增文檔和原先的老文檔整合，然後利用靜態索引創建方法對所有文檔重建索引，新索引建立完成後老索引會被遺棄。此法代價高，但是主流商業搜尋引擎一般是採用此方式來維護索引的更新（這句話是書中原話）
再合併策略：當新增文檔進入系統，解析文檔，之後更新記憶體中維護的臨時索引，文檔中出現的每個單詞，在其倒排表列表末尾追加倒排表列表項；一旦臨時索引將指定記憶體消耗光，即進行一次索引合併，這裡需要倒排檔案里的倒排列表存放順序已經按照索引單詞字典順序由低到高排序，這樣直接順序掃描合併即可。其缺點是：因為要生成新的倒排索引檔案，所以對老索引中的很多單詞，儘管其在倒排列表並未發生任何變化，也需要將其從老索引中取出來並寫入新索引中，這樣對磁碟消耗是沒必要的。
原地更新策略：試圖改進再合併策略，在原地合併倒排表，這需要提前分配一定的空間給未來插入，如果提前分配的空間不夠了需要遷移。實際顯示，其索引更新的效率比再合併策略要低。
混合策略：出發點是能夠結合不同索引更新策略的長處，將不同索引更新策略混合，以形成更高效的方法。
原理
Lucene倒排索引原理Lucene是一個高性能的java全文檢索工具包，它使用的是倒排檔案索引結構。該結構及相應的生成算法如下：0）設有兩篇文章1和2文章1的內容為：Tom lives in Guangzhou,I live in Guangzhou too.文章2的內容為：He once lived in Shanghai.取得關鍵字1)由於lucene是基於關鍵字索引和查詢的，首先我們要取得這兩篇文章的關鍵字，通常我們需要如下處理措施a.我們現在有的是文章內容，即一個字元串，我們先要找出字元串中的所有單詞，即分詞。英文單詞由於用空格分隔，比較好處理。中文單詞間是連在一起的需要特殊的分詞處理。b.文章中的”in”, “once” “too”等詞沒有什麼實際意義，中文中的“的”“是”等字通常也無具體含義，這些不代表概念的詞可以過濾掉c.用戶通常希望查“He”時能把含“he”，“HE”的文章也找出來，所以所有單詞需要統一大小寫。d.用戶通常希望查“live”時能把含“lives”，“lived”的文章也找出來，所以需要把“lives”，“lived”還原成“live”e.文章中的標點符號通常不表示某種概念，也可以過濾掉在lucene中以上措施由Analyzer類完成經過上面處理後文章1的所有關鍵字為：[tom] [live] [guangzhou] [i] [live] [guangzhou]文章2的所有關鍵字為：[he] [live] [shanghai]建立倒排索引2) 有了關鍵字後，我們就可以建立倒排索引了。上面的對應關係是：“文章號”對“文章中所有關鍵字”。倒排索引把這個關係倒過來，變成：“關鍵字”對“擁有該關鍵字的所有文章號”。文章1，2經過倒排後變成關鍵字 文章號guangzhou 1he 2i 1live 1,2shanghai 2tom 1通常僅知道關鍵字在哪些文章中出現還不夠，我們還需要知道關鍵字在文章中出現次數和出現的位置，通常有兩種位置：a)字元位置，即記錄該詞是文章中第幾個字元（優點是關鍵字亮顯時定位快）；b)關鍵字位置，即記錄該詞是文章中第幾個關鍵字（優點是節約索引空間、詞組（phase）查詢快），lucene中記錄的就是這種位置。加上“出現頻率”和“出現位置”信息後，我們的索引結構變為：關鍵字 文章號[出現頻率] 出現位置guangzhou 1 3，6he 2 1i 1 4live 1,2 2，5，2shanghai 2 3tom 1 1以live 這行為例我們說明一下該結構：live在文章1中出現了2次，文章2中出現了一次，它的出現位置為“2,5,2”這表示什麼呢？我們需要結合文章號和出現頻率來分析，文章1中出現了2次，那么“2,5”就表示live在文章1中出現的兩個位置，文章2中出現了一次，剩下的“2”就表示live是文章2中第 2個關鍵字。以上就是lucene索引結構中最核心的部分。我們注意到關鍵字是按字元順序排列的（lucene沒有使用B樹結構），因此lucene可以用二元搜尋算法快速定位關鍵字。
實現
實現時 lucene將上面三列分別作為詞典檔案（Term Dictionary）、頻率檔案(frequencies)、位置檔案 (positions)保存。其中詞典檔案不僅保存有每個關鍵字，還保留了指向頻率檔案和位置檔案的指針，通過指針可以找到該關鍵字的頻率信息和位置信息。Lucene中使用了field的概念，用於表達信息所在位置（如標題中，文章中，url中），在建索引中，該field信息也記錄在詞典檔案中，每個關鍵字都有一個field信息(因為每個關鍵字一定屬於一個或多個field)。
壓縮算法
為了減小索引檔案的大小，Lucene對索引還使用了壓縮技術。首先，對詞典檔案中的關鍵字進行了壓縮，關鍵字壓縮為<前綴長度 後綴="後綴">，例如：當前詞為“阿拉伯語”，上一個詞為“阿拉伯”，那么“阿拉伯語”壓縮為<3，語>。其次大量用到的是對數字的壓縮，數字只保存與上一個值的差值（這樣可以減小數字的長度，進而減少保存該數字需要的位元組數）。例如當前文章號是16389（不壓縮要用3個位元組保存），上一文章號是16382，壓縮後保存7（只用一個位元組）。前綴長度
套用原因
下面我們可以通過對該索引的查詢來解釋一下為什麼要建立索引。假設要查詢單詞 “live”，lucene先對詞典二元查找、找到該詞，通過指向頻率檔案的指針讀出所有文章號，然後返回結果。詞典通常非常小，因而，整個過程的時間是毫秒級的。而用普通的順序匹配算法，不建索引，而是對所有文章的內容進行字元串匹配，這個過程將會相當緩慢，當文章數目很大時，時間往往是無法忍受的。
