倒排索引和正排索引
一 以有限對(duì)無(wú)限
這個(gè)世界很多東西是無(wú)限的,比如可以創(chuàng)造無(wú)限的小說(shuō),可以創(chuàng)造無(wú)限個(gè)程序耍群。但是小說(shuō)雖然無(wú)限，小說(shuō)中的字?jǐn)?shù)卻是有限蚪腋，拿漢字來(lái)說(shuō)扣癣，我查到的最高記錄也就9萬(wàn)多個(gè)，常用的就五六千個(gè)橡淆。程序雖然有限召噩，但是CPU的指令條數(shù)卻是有限。
從有限到無(wú)限給了我們極大的靈活性逸爵，像樂(lè)高積木具滴，積木種類(lèi)不多，卻可以有N多種組合师倔，而且越簡(jiǎn)單的單體的雖然組合看起來(lái)不多构韵，卻因?yàn)楹?jiǎn)單有了更多的可能性，比如圍棋趋艘，比如計(jì)算機(jī)的0和1組合贞绳。
反過(guò)來(lái)，我們?nèi)绾翁幚頍o(wú)限的東西致稀，比如我們?nèi)绾嗡阉餍≌f(shuō)冈闭，小說(shuō)的數(shù)量可以說(shuō)是無(wú)限的，因?yàn)榭梢圆粩嗟脑黾佣兜ィ绻蠳個(gè)小說(shuō)萎攒，我們?cè)谛≌f(shuō)里面搜索“真氣” ，如果沒(méi)有特定索引矛绘，我們要把N個(gè)小說(shuō)遍歷一遍耍休，且把小說(shuō)的每個(gè)詞都要遍歷一遍，工作量實(shí)在是太大了货矮。如果給小說(shuō)的名字羊精，用名字去搜小說(shuō)卻簡(jiǎn)單的多。因?yàn)橐话阈≌f(shuō)網(wǎng)站都會(huì)對(duì)小說(shuō)名字建立索引囚玫，比如采用上次聊的哈希表索引喧锦，可以簡(jiǎn)單的通過(guò)名字找到內(nèi)容读规； 這也類(lèi)似于我們背誦唐詩(shī)，給你個(gè)題目燃少，可以很容易背誦出來(lái)一首詩(shī)束亏，但是如果給你個(gè)詞語(yǔ)，比如明月阵具，讓你給出哪些詩(shī)里面包含這個(gè)詞語(yǔ)碍遍，卻很難想。
二 倒排索引和正排索引
第一次看到倒排索引阳液，還是16年的時(shí)候怕敬，一臉懵逼，為什么叫倒排索引帘皿，這么奇怪的名字东跪，何為倒何為正，那正排索引是什么,倒排索引又是什么?
可以簡(jiǎn)單理解從文章到詞語(yǔ)叫正排,從詞語(yǔ)到文章叫倒排矮烹。以這些方式建的索引分別叫正排索引和倒排索引越庇。
2.1 正排索引
這里面文檔可以是一篇文章,也可以是一個(gè)網(wǎng)頁(yè),還可以是一章小說(shuō)或者一本小說(shuō) 罩锐。文檔ID映射到詞語(yǔ)列表的索引叫正排索引,也就是說(shuō)我們首先對(duì)文檔進(jìn)行編號(hào),然后對(duì)文檔進(jìn)行分詞,建立一個(gè)文檔ID和文檔詞語(yǔ)對(duì)應(yīng)的哈希表, 同時(shí)保存的還有詞出現(xiàn)的次數(shù),位置等信息,如下圖:
這就是一個(gè)哈希表奉狈，key就是文檔的ID，value就是一個(gè)組合結(jié)構(gòu)涩惑，里面包含詞語(yǔ)仁期，詞語(yǔ)頻次，出現(xiàn)位置竭恬。只所以有出現(xiàn)位置跛蛋，搜索時(shí)候可以高亮顯示。
那么你可能會(huì)問(wèn)了痊硕，我們搜文章的時(shí)候不可能知道ID赊级，那怎么辦。簡(jiǎn)單岔绸，如果文檔少理逊，可以建個(gè)大數(shù)組啊，數(shù)組位置就作為ID盒揉，數(shù)組是有序的晋被，這樣用二分查找，找到文檔名稱(chēng)了刚盈，從而找到文檔ID羡洛，再去搜索就可以了。
如果文檔比較多藕漱，可以用跳表欲侮，紅黑樹(shù)等結(jié)構(gòu)保存文檔名稱(chēng)和ID崭闲，也可以方便地進(jìn)行搜索的。也可以用哈希表保存锈麸，以文章名作為key镀脂，以文檔ID作為value，可以快速搜到索引忘伞。
正排索引用處： 在ES薄翅，solr等開(kāi)源搜索引擎中仍然是存在的，在ES中為doc values氓奈，我們?cè)谒阉鞯臅r(shí)候使用倒排索引翘魄，但是聚合的時(shí)候，需要查這個(gè)文檔中有多少詞語(yǔ)舀奶，所以倒排索引并不高效暑竟。在ES中，doc values 伴隨倒排索引創(chuàng)建育勺，是可以被序列化到磁盤(pán)的數(shù)據(jù)結(jié)構(gòu)但荤，在內(nèi)存中用os的文件緩存來(lái)存儲(chǔ)。
如果不需要對(duì)字段進(jìn)行聚合涧至，排序以及腳本操作腹躁，而且不是需要再次分詞的字段可以關(guān)閉doc values，因?yàn)槟J(rèn)是開(kāi)著的南蓬。
PUT my_index
{
"mappings": {
"my_type": {
"properties": {
"mystring": {
"type": "keyword",
"doc_values": false
}
}
}
}
}
更改my_type字段不保存doc_values纺非，這樣設(shè)置可以節(jié)省內(nèi)存和磁盤(pán)空間。
正排索引缺點(diǎn)： 如果只有正排索引赘方，如果搜索特定詞語(yǔ)烧颖，比如搜索詞語(yǔ)22，我們必須遍歷整個(gè)哈希結(jié)構(gòu)窄陡，獲取每個(gè)文檔對(duì)應(yīng)的詞語(yǔ)列表炕淮，一個(gè)一個(gè)比較，顯然效率很低跳夭，N個(gè)文章涂圆，每個(gè)文章有M個(gè)詞語(yǔ)，那查找的復(fù)雜度至少是O(N*M)优妙。
2.2 倒排索引
如果按照前面說(shuō)的乘综，如果我們搜索包含特定詞語(yǔ)的詩(shī)詞，用正排索引套硼，顯然不合適卡辰，因?yàn)樯婕暗酱罅康谋闅v。直觀(guān)地想，搜索什么九妈，我們就對(duì)什么建索引反砌，對(duì)于詩(shī)詞，我們對(duì)每篇詩(shī)詞分詞后萌朱，建立一個(gè)以詞語(yǔ)作為key宴树，詩(shī)詞的ID列表以及位置，詞頻等作為value的哈希表晶疼，這樣我們?cè)谒阉髟~語(yǔ)的時(shí)候酒贬，可以在O(1)時(shí)間復(fù)雜度找到包含這個(gè)詞語(yǔ)的詩(shī)詞列表，如下：
三 倒排索引創(chuàng)建和查詢(xún)
3.1 倒排索引創(chuàng)建
倒排索引的創(chuàng)建過(guò)程翠霍，整體來(lái)說(shuō)比較簡(jiǎn)單锭吨，主要有以下幾步：
首先對(duì)文檔進(jìn)行編號(hào)，且排序寒匙，這里面我覺(jué)得可以按照文檔的編號(hào)遍歷零如，編號(hào)順序就是文檔的順序，
不然就需要對(duì)文檔進(jìn)行排序锄弱。
遍歷排序后的文檔考蕾，對(duì)每個(gè)文檔進(jìn)行分詞，生成《詞語(yǔ)会宪，文檔ID肖卧，位置》的一組組數(shù)據(jù)，只所以保存位置是為了高亮查詢(xún)的關(guān)鍵詞狈谊，有些多個(gè)詞語(yǔ)查詢(xún)喜命，如果兩個(gè)詞語(yǔ)靠的更近沟沙，得分會(huì)更高些河劝。
將《詞語(yǔ)，文檔ID矛紫，位置》插入到以詞語(yǔ)作為key赎瞎，《文檔ID，位置》作為value的哈希表中颊咬。
value中也可以多存點(diǎn)信息务甥，比如此在這個(gè)文檔中出現(xiàn)的次數(shù)，這對(duì)于我們搜索后排序很有用喳篇。
最后形成如上圖的倒排索引敞临，注意下，上面的倒排索引的value是個(gè)鏈表麸澜，而且是排序的鏈表（id小的在前面）挺尿。
內(nèi)存中的倒排索引可以這樣創(chuàng)建，實(shí)際中倒排索引創(chuàng)建還需要考慮很多因素，比如文檔數(shù)量很大编矾，且每個(gè)文檔也很大熟史，導(dǎo)致索引在內(nèi)存中無(wú)法保存怎么處理，需要將中間結(jié)果持久化到磁盤(pán)中窄俏； 一般還需要一個(gè)詞典保存所有詞語(yǔ)蹂匹，這樣，詞語(yǔ)就可以用編號(hào)來(lái)表示凹蜈，減少內(nèi)存的使用限寞；同樣我們還要考慮壓縮倒排所以的大小，比如對(duì)文檔ID仰坦，因?yàn)槭琼樞虼鎯?chǔ)昆烁，我們可以只保存差值，減少數(shù)據(jù)保存的位數(shù)缎岗。
3.2 利用倒排索引的查找
如果只是簡(jiǎn)單的一個(gè)詞語(yǔ)進(jìn)行查找静尼，利用倒排索引輕易查出posting list獲取到文檔ID，在通過(guò)文檔ID把一個(gè)個(gè)查詢(xún)出來(lái)的文檔提取出來(lái)就可以了传泊。
但是實(shí)際中鼠渺，我們查詢(xún)的關(guān)鍵詞經(jīng)常是多個(gè)，如果查詢(xún)即包含中國(guó)又包含真氣詞語(yǔ)的小說(shuō)眷细，我們會(huì)得到兩個(gè)posting list如下：
如上圖拦盹，查詢(xún)兩個(gè)關(guān)鍵詞，我們得到兩個(gè)posting list 然后進(jìn)行歸并溪椎，由于文檔是有序的普舆，所以歸并的過(guò)程性能還不錯(cuò)，我們通過(guò)兩個(gè)指針來(lái)指向posting list的開(kāi)頭校读，然后根據(jù)比較結(jié)果移動(dòng)指針沼侣，如果相同，把docID取出來(lái)放在結(jié)果集合中歉秫，如果不相等蛾洛，小的那個(gè)指針對(duì)后移動(dòng)，繼續(xù)進(jìn)行比較雁芙，直到一個(gè)posting list結(jié)束轧膘。
這是查詢(xún)同時(shí)包含兩個(gè)詞的情況，還有的情況需要查詢(xún)包含多個(gè)詞其中之一的兔甘，或者包含A詞語(yǔ)谎碍，卻不含有B詞語(yǔ)的無(wú)非是兩個(gè)集合的并集，交集洞焙，差集蟆淀。
雖然上面這種歸并的方法太援，性能還不錯(cuò)，但是實(shí)際工程中扳碍，需要用多種手段來(lái)優(yōu)化歸并的性能提岔，因?yàn)閜osting list很長(zhǎng)，如果上述的歸并算法是O(m+n),仍然難以性能要求笋敞，可以通過(guò)調(diào)表碱蒙，哈希表，位圖等多種手段優(yōu)化歸并性能夯巷。
四 倒排索引延申
倒排索引更重要是一種思想赛惩，是一種從有限到無(wú)限，從屬性到整體的建索引的思路趁餐。比如如何對(duì)pcap文件建索引喷兼，如果你查詢(xún)需要根據(jù)IP，端口后雷，四層協(xié)議去查詢(xún)的話(huà)季惯，很簡(jiǎn)單可以以這些查詢(xún)關(guān)鍵字作為key，pcapid作為value臀突，或者pcap的包的offset作為value勉抓。
通過(guò)這種方法，可以快速查詢(xún)到pcap候学，最近工作中的pcap的查詢(xún)就是大概采用這種方法藕筋，當(dāng)然其中有不少細(xì)節(jié)和優(yōu)化手段，下次再寫(xiě)篇文章和大家分享梳码。
五 詩(shī)詞欣賞
《水調(diào)歌頭》·無(wú)名氏
無(wú)名氏
平生太湖上隐圾，短棹幾經(jīng)過(guò)。如今重到掰茶，何事愁與水云多暇藏。
擬把匣中長(zhǎng)劍，換取扁舟一葉符匾，歸去老漁蓑叨咖。
銀艾非吾事瘩例，丘壑已蹉跎啊胶。
膾新鱸，斟美酒垛贤，起悲歌焰坪。
太平生長(zhǎng)，豈謂今日識(shí)兵戈聘惦。
欲瀉三江雪浪某饰，凈洗胡塵千里，不用挽天河。
回首望霄漢黔漂，雙淚墮清波诫尽。
根據(jù)曾敏行《獨(dú)醒雜志》記載，宋高宗紹興年間有人在吳江長(zhǎng)橋頭上題詞一首(即本詞)炬守，不寫(xiě)姓名牧嫉。以后這首詞傳入宮內(nèi)，高宗派人大力查訪(fǎng)减途。秦檜請(qǐng)高宗降黃榜招請(qǐng)酣藻，可作者竟然不到。人們議論說(shuō)鳍置，作者是隱士辽剧，不屑做官。秦檜請(qǐng)降黃榜税产，并非真心尋求怕轿，而是居心叵測(cè)。
作者：明翼
鏈接：http://www.reibang.com/p/3e9d0c039e13
來(lái)源：簡(jiǎn)書(shū)
著作權(quán)歸作者所有辟拷。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)撤卢，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
