正排索引
概念
正排表是以文檔的ID為key，表中記錄文檔中每個(gè)關(guān)鍵字的位置信息，查找時(shí)掃描表中每個(gè)文檔中字的信息直到找出所有包含查詢關(guān)鍵字的文檔。
特點(diǎn)
這種組織方法在建立索引的時(shí)候結(jié)構(gòu)比較簡單，建立比較方便且易于維護(hù);
因?yàn)樗饕腔谖臋n建立的，若是有新的文檔加入，直接為該文檔建立一個(gè)新的索引塊，掛接在原來索引文件的后面。
若是有文檔刪除，則直接找到該文檔號文檔對應(yīng)的索引信息，將其直接刪除。
但是在查詢的時(shí)候需對所有的文檔進(jìn)行掃描以確保沒有遺漏，這樣就使得檢索時(shí)間大大延長，檢索效率低下。
倒排索引
概念
倒排表以字或詞為關(guān)鍵字進(jìn)行索引，表中關(guān)鍵字所對應(yīng)的記錄表項(xiàng)記錄了出現(xiàn)這個(gè)字或詞的所有文檔，
一個(gè)表項(xiàng)就是一個(gè)字表段，它記錄該文檔的ID和字符在該文檔中出現(xiàn)的位置情況。
特點(diǎn)
每個(gè)字或詞對應(yīng)的文檔數(shù)量在動態(tài)變化，所以倒排表的建立和維護(hù)都較為復(fù)雜，
但是在查詢的時(shí)候由于可以一次得到查詢關(guān)鍵字所對應(yīng)的所有文檔，所以效率高于正排表。
在全文檢索中，檢索的快速響應(yīng)是一個(gè)最為關(guān)鍵的性能，而索引建立由于在后臺進(jìn)行，盡管效率相對低一些，但不會影響整個(gè)搜索引擎的效率。
示例：
假設(shè)對象為商品，特征為關(guān)鍵詞。下面舉例說明一下什么是正排索引，什么是倒排索引。
對于每個(gè)商品，我們將它的標(biāo)題和描述進(jìn)行分詞，然后可以建立如下正排索引（key是商品id，value是該商品的各個(gè)關(guān)鍵詞的出現(xiàn)次數(shù)和出現(xiàn)位置）：
商品1 -> [(關(guān)鍵詞1,出現(xiàn)3次，位置為1,3,5), (關(guān)鍵詞2,出現(xiàn)2次，位置為2,6), (關(guān)鍵詞4,出現(xiàn)1次，位置為10), …]
商品2 -> [(關(guān)鍵詞1,出現(xiàn)1次，位置為1), (關(guān)鍵詞3,出現(xiàn)4次，位置為2,4,7,9), …]
商品3 -> [(關(guān)鍵詞2,出現(xiàn)2次，位置為1,4), (關(guān)鍵詞4,出現(xiàn)3次，位置為2,7,10), …]
商品4 -> [(關(guān)鍵詞5,出現(xiàn)1次，位置為1), (關(guān)鍵詞6,出現(xiàn)1次，位置為2), …]
同時(shí)我們也可以建立如下倒排索引（key是關(guān)鍵詞，value是包含該關(guān)鍵詞的商品id列表）：
關(guān)鍵詞1 -> [商品1,商品2]
關(guān)鍵詞2 -> [商品1,商品3]
關(guān)鍵詞3 -> [商品2]
關(guān)鍵詞4 -> [商品1,商品3]
關(guān)鍵詞5 -> [商品4]
關(guān)鍵詞6 -> [商品4]
用戶搜索商品這個(gè)場景中，搜索引擎會做這么幾個(gè)事情：
①將用戶輸入的文字進(jìn)行分詞，比如說得到[關(guān)鍵詞1,關(guān)鍵詞4]；
②對于關(guān)鍵詞1，根據(jù)倒排索引，發(fā)現(xiàn)命中[商品1,商品2]；
③對于關(guān)鍵詞4，根據(jù)倒排索引，發(fā)現(xiàn)命中[商品1,商品3]；
④那么符合條件的商品就包括[商品1,商品2,商品3]，下面就需要使用正排索引來對它們進(jìn)行排序，我們簡單定義一下匹配度計(jì)算公式為目標(biāo)關(guān)鍵詞出現(xiàn)次數(shù)的總和（當(dāng)然真實(shí)商業(yè)場景不可能只有匹配度這么一個(gè)維度這么簡單粗暴?？赡芤P(guān)聯(lián)數(shù)十上百個(gè)正排索引，比如匹配度、熱度、好評率、給我們廣告費(fèi)非的多少等等很多指標(biāo)綜合決定）；
⑤對于商品1，使用正排索引計(jì)算得到匹配度為3+1=4；
⑥對于商品2，使用正排索引計(jì)算得到匹配度為1；
⑦對于商品3，使用正排索引計(jì)算得到匹配度為3；
⑧根據(jù)匹配度從高到低，最終搜索的排序結(jié)果為：[商品1,商品3,商品2]
因此總的來說倒排索引用于召回，從茫茫海洋中把所有符合條件的對象搜索出來；正排索引用于排序，把最符合搜索結(jié)果、對用戶(或者是商家 or 平臺)價(jià)值最高的對象放到首位。
注：
其中詞典結(jié)構(gòu)尤為重要，有很多種詞典結(jié)構(gòu)，各有各的優(yōu)缺點(diǎn)，最簡單如排序數(shù)組，通過二分查找來檢索數(shù)據(jù)，更快的有哈希表，磁盤查找有B樹、B+樹，但一個(gè)能支持TB級數(shù)據(jù)的倒排索引結(jié)構(gòu)需要在時(shí)間和空間上有個(gè)平衡，下圖列了一些常見詞典的優(yōu)缺點(diǎn)：
