在關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)里，索引是檢索數(shù)據(jù)最有效率的方式,。但對(duì)于搜索引起，他它并不能滿(mǎn)足其特殊要求：
1）海量數(shù)據(jù)：搜索引擎面對(duì)的是海量數(shù)據(jù)，像Google，百度這樣大型的商業(yè)搜索引擎索引都是億級(jí)甚至幾千的網(wǎng)頁(yè)數(shù)量 ，面對(duì)如此海量數(shù)據(jù) ,使得數(shù)據(jù)庫(kù)系統(tǒng)很難有效的管理。
2）數(shù)據(jù)操作簡(jiǎn)單：搜索引擎使用的數(shù)據(jù)操作簡(jiǎn)單 ,一般而言 ,只需要增、 刪、 改、 查幾個(gè)功能 ,而且數(shù)據(jù)都有特定的格式 ,可以針對(duì)這些應(yīng)用設(shè)計(jì)出簡(jiǎn)單高效的應(yīng)用程序。而一般的數(shù)據(jù)庫(kù)系統(tǒng)則支持大而全的功能 ,同時(shí)損失了速度和空間。最后 ,搜索引擎面臨大量的用戶(hù)檢索需求 ,這要求搜索引擎在檢索程序的設(shè)計(jì)上要分秒必爭(zhēng) ,盡可能的將大運(yùn)算量的工作在索引建立時(shí)完成 ,使檢索運(yùn)算盡量的少。一般的數(shù)據(jù)庫(kù)系統(tǒng)很難承受如此大量的用戶(hù)請(qǐng)求 ,而且在檢索響應(yīng)時(shí)間和檢索并發(fā)度上都不及我們專(zhuān)門(mén)設(shè)計(jì)的索引系統(tǒng)。
來(lái)自維基百科定義：
倒排索引（英語(yǔ)：Inverted index），也常被稱(chēng)為反向索引、置入檔案或反向檔案，是一種索引方法，被用來(lái)存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。它是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)。通過(guò)倒排索引，可以根據(jù)單詞快速獲取包含這個(gè)單詞的文檔列表。倒排索引主要由兩個(gè)部分組成：“單詞詞典”和“倒排文件”。
倒排索引有兩種不同的反向索引形式：
一條記錄的水平反向索引（或者反向檔案索引）包含每個(gè)引用單詞的文檔的列表。
一個(gè)單詞的水平反向索引（或者完全反向索引）又包含每個(gè)單詞在一個(gè)文檔中的位置。
后者的形式提供了更多的兼容性（比如短語(yǔ)搜索），但是需要更多的時(shí)間和空間來(lái)創(chuàng)建。
現(xiàn)代搜索引起的索引都是基于倒排索引。相比“簽名文件”、“后綴樹(shù)”等索引結(jié)構(gòu)，“倒排索引”是實(shí)現(xiàn)單詞到文檔映射關(guān)系的最佳實(shí)現(xiàn)方式和最有效的索引結(jié)構(gòu).
倒排索引的簡(jiǎn)單實(shí)例： 搜索引擎-倒排索引基礎(chǔ)知識(shí)
倒排列表用來(lái)記錄有哪些文檔包含了某個(gè)單詞。一般在文檔集合里會(huì)有很多文檔包含某個(gè)單詞，每個(gè)文檔會(huì)記錄文檔編號(hào)（DocID），單詞在這個(gè)文檔中出現(xiàn)的次數(shù)（TF）及單詞在文檔中哪些位置出現(xiàn)過(guò)等信息，這樣與一個(gè)文檔相關(guān)的信息被稱(chēng)做倒排索引項(xiàng)（Posting），包含這個(gè)單詞的一系列倒排索引項(xiàng)形成了列表結(jié)構(gòu)，這就是某個(gè)單詞對(duì)應(yīng)的倒排列表。圖1是倒排列表的示意圖，在文檔集合中出現(xiàn)過(guò)的所有單詞及其對(duì)應(yīng)的倒排列表組成了倒排索引。
圖1 倒排列表
在實(shí)際的搜索引擎系統(tǒng)中，并不存儲(chǔ)倒排索引項(xiàng)中的實(shí)際文檔編號(hào)，而是代之以文檔編號(hào)差值（D-Gap）。文檔編號(hào)差值是倒排列表中相鄰的兩個(gè)倒排索引項(xiàng)文檔編號(hào)的差值，一般在索引構(gòu)建過(guò)程中，可以保證倒排列表中后面出現(xiàn)的文檔編號(hào)大于之前出現(xiàn)的文檔編號(hào)，所以文檔編號(hào)差值總是大于0的整數(shù)。如圖2所示的例子中，原始的 3個(gè)文檔編號(hào)分別是187、196和199，通過(guò)編號(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ù)值，通過(guò)差值計(jì)算，就有效地將大數(shù)值轉(zhuǎn)換為了小數(shù)值，而這有助于增加數(shù)據(jù)的壓縮率。
索引的構(gòu)建相當(dāng)于從正排表到倒排表的建立過(guò)程。當(dāng)我們分析完網(wǎng)頁(yè)時(shí) ,得到的是以網(wǎng)頁(yè)為主碼的索引表。當(dāng)索引建立完成后 ,應(yīng)得到倒排表 ,具體流程如圖3所示：
圖3 索引構(gòu)建
流程：
1）將文檔分析稱(chēng)單詞term標(biāo)記，
2）使用hash去重單詞term
3）對(duì)單詞生成倒排列表
倒排列表就是文檔編號(hào)DocID，沒(méi)有包含其他的信息（如詞頻，單詞位置等），這就是簡(jiǎn)單的索引。
這個(gè)簡(jiǎn)單索引功能可以用于小數(shù)據(jù)，例如索引幾千個(gè)文檔。然而它有兩點(diǎn)限制：
1）需要有足夠的內(nèi)存來(lái)存儲(chǔ)倒排表，對(duì)于搜索引擎來(lái)說(shuō)， 都是G級(jí)別數(shù)據(jù)，特別是當(dāng)規(guī)模不斷擴(kuò)大時(shí) ,我們根本不可能提供這么多的內(nèi)存。
2）算法是順序執(zhí)行，不便于并行處理。
4.3 合并法建立索引
歸并法,即每次將內(nèi)存中數(shù)據(jù)寫(xiě)入磁盤(pán)時(shí)，包括詞典在內(nèi)的所有中間結(jié)果信息都被寫(xiě)入磁盤(pán)，這樣內(nèi)存所有內(nèi)容都可以被清空，后續(xù)建立索引可以使用全部的定額內(nèi)存。
如圖4 歸并示意圖：
圖4：歸并索引
合并流程如圖5：
1）頁(yè)面分析，生成臨時(shí)倒排數(shù)據(jù)索引A，B，當(dāng)臨時(shí)倒排數(shù)據(jù)索引A，B占滿(mǎn)內(nèi)存后，將內(nèi)存索引A，B寫(xiě)入臨時(shí)文件生成臨時(shí)倒排文件，
2) 對(duì)生成的多個(gè)臨時(shí)倒排文件 ,執(zhí)行多路歸并 ,輸出得到最終的倒排文件 ( inverted file)。
圖5 合并流程
索引創(chuàng)建過(guò)程中的頁(yè)面分析 ,特別是中文分詞為主要時(shí)間開(kāi)銷(xiāo)。算法的第二步相對(duì)很快。這樣創(chuàng)建算法的優(yōu)化集中在中文分詞效率上。
4.2 并行與分布式建立索引
在 搜索引擎-網(wǎng)絡(luò)爬蟲(chóng), 已經(jīng)提到云存儲(chǔ)文檔，使用Map/Reduce并行計(jì)算模型，對(duì)文檔生成倒排索引列：
對(duì)于建立倒排索引這個(gè)任務(wù)來(lái)說(shuō)，如圖6所示，輸入數(shù)據(jù)也是網(wǎng)頁(yè)，以網(wǎng)頁(yè)的DOCID作為輸入數(shù)據(jù) 的Key, 網(wǎng)頁(yè)中出現(xiàn)的單詞集合是輸入數(shù)據(jù)的 Value; Map 操作將輸入數(shù)據(jù)轉(zhuǎn)化為 (word，DOCID)的形式，即某個(gè)單詞作為Key， DOCID作為中間數(shù)據(jù)的value，其含義是單詞 word在DOCID這個(gè)網(wǎng)頁(yè)出現(xiàn)過(guò)；Reduce操作將中間數(shù)據(jù)中相同Key的記錄融合，得到某 個(gè)單詞對(duì)應(yīng)的網(wǎng)頁(yè)ID列表： <word，List(DodD:pos)>。這就是單詞word對(duì)應(yīng)的倒排列表。通過(guò) 這種方式就可以建立簡(jiǎn)單的倒排索引，在Reduce階段也可以做些復(fù)雜操作，獲得形式更為復(fù)雜的倒排索引。
圖6
更新策略有四種：完全重建、再合并策略、原地更新策略以及混合策略。
參考文獻(xiàn)：
《這就是搜索引擎:核心技術(shù)詳解》
《搜索引擎—信息檢索實(shí)踐》聯(lián)系客服
