背景
在關(guān)系型數(shù)據(jù)庫(kù)中途事，索引是檢索數(shù)據(jù)的最有效率方式，但是在海量的數(shù)據(jù)中雨让，需要實(shí)時(shí)檢索數(shù)據(jù)的時(shí)候，關(guān)系型數(shù)據(jù)庫(kù)的索引方式在性能方面并不能滿足我們的檢索要求忿等。打個(gè)比方：搜索引擎面對(duì)的是海量數(shù)據(jù)栖忠，像Google，百度這樣大型的商業(yè)搜索引擎索引都是億級(jí)甚至百億級(jí)的網(wǎng)頁(yè)數(shù)量 ，面對(duì)如此海量數(shù)據(jù) ,使得數(shù)據(jù)庫(kù)系統(tǒng)很難有效的管理庵寞。于是在很多搜索引擎中出現(xiàn)了一種相對(duì)于我們傳統(tǒng)的正序索引相反的一種索引：倒排索引或反序索引狸相，官方的名稱是：inverted index 。
倒排索引
1）基本概念
概括《這就是搜索引擎-核心技術(shù)詳解》總結(jié)出來就是：索引表包括了每條記錄的屬性值和屬性值記錄的地址捐川，檢索的時(shí)候脓鹃，通過屬性值來確定該條記錄的位置，而不是像傳統(tǒng)索引那樣通過屬性來確定屬性值古沥，通俗的說就是不在是通過key尋找value瘸右，而是通過value尋找key。也許這么闡述還是有點(diǎn)抽象岩齿，那么我們先了解倒排索引有關(guān)的幾個(gè)概念太颤，然后一點(diǎn)點(diǎn)深入。
文檔
一般搜索引擎的處理對(duì)象是互聯(lián)網(wǎng)網(wǎng)頁(yè)盹沈，而文檔這個(gè)概念更要寬泛一些龄章，代表以文本形式存在的存儲(chǔ)對(duì)象。相比于網(wǎng)頁(yè)來說襟诸，涵蓋更多形式瓦堵，比如Word、PDF歌亲、html菇用、XML等不同格式的文件都可以稱為文檔，再比如一封郵件陷揪、一條短信惋鸥、一條微博也可以稱為文檔。
文檔集合
顧名思義悍缠，一組或多個(gè)文檔構(gòu)成的集合卦绣，比如海量的互聯(lián)網(wǎng)網(wǎng)頁(yè)或者大量的電子郵件，都是文檔集合的具體例子飞蚓。
文檔編號(hào)
在搜索引擎內(nèi)部滤港，會(huì)為文檔集合內(nèi)每個(gè)文檔賦予一個(gè)唯一的內(nèi)部編號(hào)，以此編號(hào)作為這個(gè)文檔的唯一標(biāo)識(shí)趴拧，這樣方便內(nèi)部處理溅漾。
單詞編號(hào)（重點(diǎn)）
與文檔編號(hào)類似，搜索引擎內(nèi)部以唯一的編號(hào)來表征某個(gè)單詞著榴，單詞編號(hào)可以作為某個(gè)單詞的唯一表征添履。
倒排索引（重點(diǎn)）
倒排索引是實(shí)現(xiàn)單詞——文檔矩陣（文檔矩陣如下圖1，為了方便看脑又，就不直接采用書上的截圖暮胧，而是采用網(wǎng)友們的圖）的一種具體存儲(chǔ)形式锐借。通過倒排索引，可以根據(jù)單詞快速獲取包含這個(gè)單詞的文檔列表往衷。倒排索引主要由兩個(gè)部分組成：單詞詞典和倒排文件钞翔。
單詞詞典（重點(diǎn)）
搜索引擎通常的索引單位是單詞，單詞詞典是由文檔集合中出現(xiàn)過的所有單詞構(gòu)成的字符串集合席舍，單詞詞典內(nèi)每條索引項(xiàng)記載單詞本身的一些信息及指向倒排列表的指針嗅战。所以在用戶進(jìn)行查詢的時(shí)候，搜索引擎根據(jù)用戶的查詢?cè)~俺亮，去單詞詞典里查詢，就能夠獲得相應(yīng)的倒排列表疟呐，并以此作為后續(xù)排序的基礎(chǔ)脚曾。
對(duì)于一個(gè)規(guī)模很大的文檔集合來說，可能包含幾十萬(wàn)甚至上百萬(wàn)不同的單詞启具，能否快速定位某個(gè)單詞本讥，這直接影響搜索時(shí)的相應(yīng)速度，常用的數(shù)據(jù)結(jié)構(gòu)包括哈希加鏈表結(jié)構(gòu)和樹形詞典結(jié)構(gòu)鲁冯。
倒排列表
倒排列表記載了出現(xiàn)過某個(gè)單詞的所有文檔的文檔列表及單詞在該文檔中出現(xiàn)的位置信息拷沸，每條記錄稱為一個(gè)倒排項(xiàng)（Posting）。根據(jù)倒排列表薯演，即可獲知哪些文檔包含某個(gè)單詞撞芍。
倒排文件
所有單詞的倒排列表往往順序地存儲(chǔ)在磁盤的某個(gè)文件里，這個(gè)文件即被稱為倒排文件跨扮，倒排文件是存儲(chǔ)倒排索引的物理文件序无。
單詞-文檔矩陣：（單詞即一段文檔或者句子中的某個(gè)單詞，英文以空格分割衡创，文檔即一段句子或者一段文章）
稍微簡(jiǎn)述一下帝嗡，上述圖中的意思，我們首先把文檔看作一段英文句子璃氢，也就是說句子1哟玷，2，3一也，4巢寡，5在橫列中，然后每段句子構(gòu)成的單詞在列中塘秦，如果單詞在某個(gè)句子出現(xiàn)過讼渊，就在該句子與單詞構(gòu)成的矩陣交集處打勾，這樣就構(gòu)成了我們單詞文檔矩陣尊剔。
將上面的索引的元素組成后爪幻，大致關(guān)系圖如下圖2所示（由于書上的圖依舊不清晰菱皆，所以還是采用網(wǎng)上其他同學(xué)的圖）：
上面的圖也稍微解釋一下：
單詞的集合組成了詞典，每個(gè)單詞與文檔的組合組成了倒排索引挨稿，倒排索引的結(jié)匯組成了倒排列表仇轻，倒排列表組成了倒排文件。
倒排索引實(shí)例
這里我們就引用書中的例子：
圖1中有5個(gè)句子奶甘，然后我們把每句話的詞匯和句子構(gòu)成單詞-文檔矩陣篷店，第一列給每個(gè)單詞一個(gè)編號(hào)，即我們前面說的單詞編號(hào)臭家，便于檢索時(shí)候使用疲陕，第二列是單詞，第三列是每一個(gè)單詞在哪里句子里面出現(xiàn)的钉赁。然后這種索引列表過于簡(jiǎn)單蹄殃，我們可以繼續(xù)在圖2中我們?cè)诘古帕斜碇屑尤朊恳粋€(gè)單詞在每一個(gè)句子里面出現(xiàn)的頻率
如圖3所示，我們看到倒排列表中你踩，增加了每一個(gè)詞匯在句子出現(xiàn)的編號(hào)以及出現(xiàn)的頻率诅岩，當(dāng)然這樣還是很簡(jiǎn)單，并不達(dá)到我們的預(yù)期索引系統(tǒng)带膜，于是我們可以在增加單詞頻率的基礎(chǔ)上加入文檔頻率吩谦，即代表有多少個(gè)文檔包含了這類單詞。
如圖4所示：我們以“拉斯”為例子膝藕，其單詞編號(hào)為8式廷，文檔頻率為2，代理整個(gè)文檔中有兩個(gè)文檔包含這個(gè)單詞芭挽，對(duì)應(yīng)倒排列表是：{(3;1,<4>),(5;1,<4>)},其含義就是“拉斯”在文檔3和文檔5各出現(xiàn)一次懒棉，位置在第四個(gè)詞的位置。上述的例子即是一個(gè)完整的倒排索引系統(tǒng)览绿，在實(shí)際應(yīng)用中無(wú)非采取哪種數(shù)據(jù)的方式而已策严。
索引的存儲(chǔ)結(jié)構(gòu)
單詞詞典是倒排索引中非常重要的組成部分，它用來維護(hù)文檔集合中出現(xiàn)過的所有單詞的相關(guān)信息饿敲，同時(shí)用來記載某個(gè)單詞對(duì)應(yīng)的倒排列表在倒排文件中的位置信息属铁。在支持搜索時(shí)现横，根據(jù)用戶的查詢?cè)~垮媒，去單詞詞典里查詢恳谎，就能夠獲得相應(yīng)的倒排列表，并以此作為后續(xù)排序的基礎(chǔ)瓢对。
1）Hash的存儲(chǔ)方式
在建立索引的過程中寿酌，詞典結(jié)構(gòu)也會(huì)相應(yīng)地被構(gòu)建出來。比如在解析一個(gè)新文檔的時(shí)候硕蛹，對(duì)于某個(gè)在文檔中出現(xiàn)的單詞T醇疼，首先利用哈希函數(shù)獲得其哈希值硕并，之后根據(jù)哈希值對(duì)應(yīng)的哈希表項(xiàng)讀取其中保存的指針，就找到了對(duì)應(yīng)的沖突鏈表秧荆。如果沖突鏈表里已經(jīng)存在這個(gè)單詞倔毙，說明單詞在之前解析的文檔里已經(jīng)出現(xiàn)過。如果在沖突鏈表里沒有發(fā)現(xiàn)這個(gè)單詞乙濒，說明該單詞是首次碰到陕赃，則將其加入沖突鏈表里。這樣的存儲(chǔ)方式很類似于Java中HashMap解決hash沖突的方式颁股。
2）樹形結(jié)構(gòu)
B樹（或者B+樹的）存儲(chǔ)方式么库，這點(diǎn)很類似于Mysql的Inoodb的存儲(chǔ)引擎中采用B+樹的方式來存儲(chǔ)索引，由于采用了B樹的結(jié)構(gòu)甘有，即索引存儲(chǔ)在是一個(gè)平衡樹廊散，避免了查詢極端的情況，由于有序梧疲，所以能根據(jù)字典項(xiàng)需要的大小順序來構(gòu)建索引，這樣在檢索中可以快速通過字典項(xiàng)比較大小运准，最終確定葉子結(jié)點(diǎn)中詞匯的存儲(chǔ)地址信息幌氮。（由于B樹的構(gòu)建復(fù)雜，這里就不過多的講解胁澳，向深入了解该互，可以翻翻上學(xué)那會(huì)兒的《數(shù)據(jù)結(jié)構(gòu)》那本書喔）
總結(jié)
上面大致粗略的講解了一下倒排索引的概念，其實(shí)在實(shí)際中韭畸，倒排索引還會(huì)進(jìn)行索引壓縮宇智，排序的加工，也正因?yàn)檫@些加工胰丁，讓其成為目前許多搜索引擎采用的索引方式随橘。由于博主也是最近才介入搜索相關(guān)的工作，對(duì)于搜索引擎的話锦庸，還在初探階段机蔗，如有更好的見解，歡迎一起來學(xué)習(xí)甘萧。
