倒排索引是搜索引擎中最為核心的一項技術之一，可以說是搜索引擎的基石。可以說正是有了倒排索引技術，搜索引擎才能有效率的進行數據庫查找、刪除等操作。
1. 倒排索引的思想
倒排索引源于實際應用中需要根據屬性的值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。
在搜索引擎中，查詢詞可以切分成若干個單詞，所以對于搜索引擎中的倒排索引對應的屬性就是單詞，而對應的記錄就是網頁（也可以廣泛地稱為是文檔）。所以，搜索引擎中的倒排索引是實現“單詞-文檔矩陣”的一種具體存儲形式，通過倒排索引，可以根據單詞（屬性）快速獲取包含這個單詞的文檔列表（記錄）。倒排索引主要由兩個部分組成：“單詞詞典”和“倒排文件”。
2. “單詞-文檔矩陣”
單詞-文檔矩陣是表達兩者之間所具有的一種包含關系的概念模型，圖1展示了其含義。圖1的每列代表一個文檔，每行代表一個單詞，打對勾的位置代表包含關系：
圖1 單詞-文檔矩陣
從縱向即文檔這個維度來看，每列代表文檔包含了哪些單詞，比如文檔1包含了詞匯1和詞匯4，而不包含其它單詞。從橫向即單詞這個維度來看，每行代表了哪些文檔包含了某個單詞。比如對于詞匯1來說，文檔1和文檔4中出現過單詞1，而其它文檔不包含詞匯1。矩陣中其它的行列也可作此種解讀。
搜索引擎的索引其實就是實現“單詞-文檔矩陣”的具體數據結構。可以有不同的方式來實現上述概念模型，比如“倒排索引”、“簽名文件”、“后綴樹”等方式。但是各項實驗數據表明，“倒排索引”是實現單詞到文檔映射關系的最佳實現方式。
3. 倒排索引的基本框架
單詞和單詞字典：搜索引擎的通常索引單位是單詞，單詞詞典是由文檔集合中出現過的所有單詞構成的字符串集合，單詞詞典內每條索引項記載單詞本身的一些信息以及指向“倒排列表”的指針。
倒排列表：倒排列表記載了出現過某個單詞的所有文檔的文檔列表及單詞在該文檔中出現的位置信息，每條記錄稱為一個倒排項(Posting)。根據倒排列表，即可獲知哪些文檔包含某個單詞。
倒排文件：所有單詞的倒排列表往往順序地存儲在磁盤的某個文件里，這個文件即被稱之為倒排文件，倒排文件是存儲倒排索引的物理文件。
搜索引擎中倒排索引大概流程框架：用戶在搜索引擎搜索框輸入查詢詞進行搜索時，搜索引擎會對查詢詞進行切詞以及近義詞匹配等操作，根據原始查詢詞得到一系列的單詞列表。然后根據搜索引擎內部的字典來查詢每個單詞對應的倒排列表，從而定位到包含這個單詞的網頁或者說是文檔。最后搜索引擎根據特定的網頁排序算法將查詢到的網頁進行排序，通過前端將搜索結果展示給用戶。下圖2為倒排索引的主要流程：
圖2 倒排索引流程框架
4. 單詞字典
其實，我們通過上述倒排索引的流程也可以看出來，倒排索引的關鍵技術在于建立單詞字典。
單詞詞典用來維護文檔集合中出現過的所有單詞的相關信息，同時用來記載某個單詞對應的倒排列表在倒排文件中的位置信息。在支持搜索時，根據用戶的查詢詞，去單詞詞典里查詢，就能夠獲得相應的倒排列表，并以此作為后續排序的基礎。
對于一個規模很大的文檔集合來說，可能包含幾十萬甚至上百萬的不同單詞，能否快速定位某個單詞，這直接影響搜索時的響應速度，所以需要高效的數據結構來對單詞詞典進行構建和查找，常用的數據結構包括哈希加鏈表結構（哈希存儲的拉鏈法）和樹形詞典結構。
1）哈希拉鏈法
圖3是這種詞典結構的示意圖。這種詞典結構主要由兩個部分構成：
主體部分是哈希表，每個哈希表項保存一個指針，指針指向沖突鏈表，在沖突鏈表里，相同哈希值的單詞形成鏈表結構。之所以會有沖突鏈表，是因為兩個不同單詞獲得相同的哈希值，如果是這樣，在哈希方法里被稱做是一次沖突，可以將相同哈希值的單詞存儲在鏈表里，以供后續查找。
圖3 哈希拉鏈法詞典結構
在建立索引的過程中，詞典結構也會相應地被構建出來。比如在解析一個新文檔的時候，對于某個在文檔中出現的單詞T，首先利用哈希函數獲得其哈希值，之后根據哈希值對應的哈希表項讀取其中保存的指針，就找到了對應的沖突鏈表。如果沖突鏈表里已經存在這個單詞，說明單詞在之前解析的文檔里已經出現過。如果在沖突鏈表里沒有發現這個單詞，說明該單詞是首次碰到，則將其加入沖突鏈表里。通過這種方式，當文檔集合內所有文檔解析完畢時，相應的詞典結構也就建立起來了。
在響應用戶查詢請求時，其過程與建立詞典類似，不同點在于即使詞典里沒出現過某個單詞，也不會添加到詞典內。以圖3為例，假設用戶輸入的查詢請求為單詞X，對這個單詞進行哈希，定位到哈希表內的4號槽，從其保留的指針可以獲得沖突鏈表，依次將單詞X和沖突鏈表內的單詞比較，發現單詞X在沖突鏈表內，于是找到這個單詞，之后可以讀出這個單詞對應的倒排列表來進行后續的工作，如果沒有找到這個單詞，說明文檔集合內沒有任何文檔包含單詞，則搜索結果為空。
2）樹形結構
B樹（或者B+樹）是另外一種高效查找結構，圖1-8是一個 B樹結構示意圖。B樹與哈希方式查找不同，需要字典項能夠按照大小排序（數字或者字符序），而哈希方式則無須數據滿足此項要求。
B樹形成了層級查找結構，中間節點用于指出一定順序范圍的詞典項目存儲在哪個子樹中，起到根據詞典項比較大小進行導航的作用，最底層的葉子節點存儲單詞的地址信息，根據這個地址就可以提取出單詞字符串。
5. 倒排索引的實例
假設文檔集合包含五個文檔，每個文檔內容如圖4所示，在圖中最左端一欄是每個文檔對應的文檔編號。我們的任務就是對這個文檔集合建立倒排索引。
圖4 文檔集合
中文和英文等語言不同，單詞之間沒有明確分隔符號，所以首先要用分詞系統將文檔自動切分成單詞序列。這樣每個文檔就轉換為由單詞序列構成的數據流，為了系統后續處理方便，需要對每個不同的單詞賦予唯一的單詞編號，同時記錄下哪些文檔包含這個單詞，在如此處理結束后，我們可以得到最簡單的倒排索引（參考圖3-4）。在圖3-4中，“單詞ID”一欄記錄了每個單詞的單詞編號，第二欄是對應的單詞，第三欄即每個單詞對應的倒排列表。比如單詞“谷歌”，其單詞編號為1，倒排列表為{1,2,3,4,5}，說明文檔集合中每個文檔都包含了這個單詞。
圖5 簡單的倒排索引
之所以說圖5所示倒排索引是最簡單的，是因為這個索引系統只記載了哪些文檔包含某個單詞，而事實上，索引系統還可以記錄除此之外的更多信息。在單詞對應的倒排列表中不僅記錄了文檔編號，還可以記載了單詞頻率信息（TF），即這個單詞在某個文檔中的出現次數，之所以要記錄這個信息，是因為詞頻信息在搜索結果排序時，計算查詢和文檔相似度是很重要的一個計算因子，所以將其記錄在倒排列表中，以方便后續排序時進行分值計算 實用的倒排索引還可以記載更多的信息，圖6所示索引系統除了記錄文檔編號和單詞頻率信息外，額外記載了兩類信息，即每個單詞對應的“文檔頻率信息”（對應圖6的第三欄）。
圖6 帶有單詞頻率、文檔頻率和出現位置信息的倒排索引
此外，除了上述信息，還可以在倒排列表中記錄單詞在某個文檔出現的位置信息。
圖6所示倒排索引已經是一個非常完備的索引系統，實際搜索系統的索引結構基本如此，區別無非是采取哪些具體的數據結構來實現上述邏輯結構。
有了這個索引系統，搜索引擎可以很方便地響應用戶的查詢，比如用戶輸入查詢詞“Facebook”，搜索系統查找倒排索引，從中可以讀出包含這個單詞的文檔，這些文檔就是提供給用戶的搜索結果，而利用單詞頻率信息、文檔頻率信息即可以對這些候選搜索結果進行排序，計算文檔和查詢的相似性，按照相似性得分由高到低排序輸出，最后為用戶展示出搜索結果。
