倒排索引源于實際應(yīng)用中需要根據(jù)屬性的值來查找記錄。這種索引表中的每一項都包括一個屬性值和具有該屬性值的各記錄的地址。由于不是由記錄來確定屬性值，而是由屬性值來確定記錄的位置，因而稱為倒排索引(inverted index)。帶有倒排索引的文件我們稱為倒排索引文件，簡稱倒排文件(inverted file)。
倒排列表概念
在實際的搜索引擎系統(tǒng)中，并不存儲倒排索引項中的實際文檔編號，而是代之以文檔編號差值（D-Gap）。文檔編號差值是倒排列表中相鄰的兩個倒排索引項文檔編號的差值，一般在索引構(gòu)建過程中，可以保證倒排列表中后面出現(xiàn)的文檔編號大于之前出現(xiàn)的文檔編號，所以文檔編號差值總是大于0的整數(shù)。如圖2所示的例子中，原始的 3個文檔編號分別是187、196和199，通過編號差值計算，在實際存儲的時候就轉(zhuǎn)化成了：187、9、3。
之所以要對文檔編號進(jìn)行差值計算，主要原因是為了更好地對數(shù)據(jù)進(jìn)行壓縮，原始文檔編號一般都是大數(shù)值，通過差值計算，就有效地將大數(shù)值轉(zhuǎn)換為了小數(shù)值，而這有助于增加數(shù)據(jù)的壓縮率。
倒排索引概念
倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)。通過倒排索引，可以根據(jù)單詞快速獲取包含這個單詞的文檔列表。倒排索引主要由兩個部分組成：“單詞詞典”和“倒排文件”。
倒排索引倒排索引有兩種不同的反向索引形式：
一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。
一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
后者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時間和空間來創(chuàng)建。
現(xiàn)代搜索引擎的索引都是基于倒排索引。相比“簽名文件”、“后綴樹”等索引結(jié)構(gòu)，“倒排索引”是實現(xiàn)單詞到文檔映射關(guān)系的最佳實現(xiàn)方式和最有效的索引結(jié)構(gòu)。
倒排索引一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。
一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
后者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時間和空間來創(chuàng)建。
現(xiàn)代搜索引擎的索引都是基于倒排索引。相比“簽名文件”、“后綴樹”等索引結(jié)構(gòu)，“倒排索引”是實現(xiàn)單詞到文檔映射關(guān)系的最佳實現(xiàn)方式和最有效的索引結(jié)構(gòu)。
