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