倒序索引的原理和在全文搜索中的應用

（Ceeji 原創，轉載請註明作者和出處網址）

我們都知道搜索引擎搜索一個詞是非常快的，但你有沒有想過為什麼搜索引擎能夠以這麼快的速度從數以億計的網頁中找到你想要的內容？一個很重要的原因是，現代的搜索引擎基本上都使用了倒序索引技術。

如果不使用倒序索引技術，在每次進行檢索時，搜索引擎必須遍歷每一個網頁，查找網頁中是否包含你指定的關鍵詞。這個工作量是十分巨大的，主要原因有二：

• 互聯網的網頁基數非常大；
• 在每一個網頁中檢索是否含有指定的關鍵詞不是一件簡單的事情，它需要遍歷網頁的每個字符。

為了更好的建立被搜索的關鍵字和含有這些關鍵字的頁面之間的映射關係，倒序索引產生了。簡單的說，倒序索引的倒序，指的是這個索引是從關鍵詞中查找對應的源的，而不是從源中檢索對應的關鍵詞。

舉例如下：為了檢索關鍵詞 A，首先從倒序索引的索引表中，找到關鍵詞 A，然後查找 A 所在的頁。由於倒序索引表排序後，在其中查找一個關鍵詞可以使用二分查找，特別是在採用分佈式數據、服務器集群、多線程技術等條件下，效率極高，所以，查找含有某個關鍵詞的頁變得非常簡單。

假設數據庫中含有1000000條記錄，其中有 10 條記錄符合搜尋條件，如果使用倒序索引，可以很快找到這些關鍵詞，並且定位到含有這些關鍵詞的十條記錄；否則，需要遍歷1000000條記錄，效率的差異可想而知。

所以，倒序索引相當於一本出處大字典，查閱其中的每個詞彙，都可以告訴你它的所有出處。

倒序索引中的關鍵詞，一般是蜘蛛（Spider）在網頁爬行時對網頁進行分詞的結果。中文分詞也是一件比較麻煩的事情。關於分詞技術，請查閱其他相關文章。

（我開發的題典（Tidian）搜索引擎採用了倒序索引技術和智能中文分詞技術。）