開(kāi)發(fā)Web應(yīng)用時(shí)，你經(jīng)常要加上搜索功能。甚至還不知道要搜什么，就在草圖上畫(huà)了一個(gè)放大鏡。
說(shuō)到目前計(jì)算機(jī)的文字搜索在應(yīng)用上的實(shí)現(xiàn)，象形文字天生就比拼音字母劣勢(shì)的多，分詞、詞性判斷、拼音文字轉(zhuǎn)換啥的，容易讓人香菇。
首先我們來(lái)了解下什么是Inverted index，翻譯過(guò)來(lái)的名字有很多，比如反轉(zhuǎn)索引、倒排索引什么的，讓人不明所以，可以理解為：一個(gè)未經(jīng)處理的數(shù)據(jù)庫(kù)中，一般是以文檔ID作為索引，以文檔內(nèi)容作為記錄。而Inverted index 指的是將單詞或記錄作為索引，將文檔ID作為記錄，這樣便可以方便地通過(guò)單詞或記錄查找到其所在的文檔。并不是什么高深概念。
oracle里常用的位圖索引（Bitmap index）也可認(rèn)為是Inverted index。位圖索引對(duì)于相異基數(shù)低的數(shù)據(jù)最為合適，即記錄多，但取值較少。比如一個(gè)100W行的表有一個(gè)字段會(huì)頻繁地被當(dāng)做查詢條件，我們會(huì)想到在這一列上面建立一個(gè)索引，但是這一列只可能取3個(gè)值。那么如果建立一個(gè)B*樹(shù)索引（普通索引）是不合適的，因?yàn)闊o(wú)論查找哪一個(gè)值，都可能會(huì)查出很多數(shù)據(jù)，這時(shí)就可以考慮使用位圖索引。位圖索引相對(duì)于傳統(tǒng)的B*樹(shù)索引，在葉子節(jié)點(diǎn)上采用了完全不同的結(jié)構(gòu)組織方式。傳統(tǒng)B*樹(shù)索引將每一行記錄保存為一個(gè)葉子節(jié)點(diǎn)，上面記錄對(duì)應(yīng)的索引列取值和行rowid信息。而位圖索引將每個(gè)可能的索引取值組織為一個(gè)葉子節(jié)點(diǎn)。每個(gè)位圖索引的葉子節(jié)點(diǎn)上，記錄著該索引鍵值的起始截止rowid和一個(gè)位圖向量串。如果不考慮起止rowid，那么就是取值有幾個(gè)，就有幾個(gè)索引，比如上例，雖說(shuō)有100W條記錄，但是針對(duì)只有3個(gè)可取值的字段來(lái)說(shuō)，索引節(jié)點(diǎn)只有3個(gè)，類(lèi)似于下圖：
需要注意的是，由于所有索引字段同值行共享一個(gè)索引節(jié)點(diǎn)，位圖索引不適用于頻繁增刪改的字段，否則可能會(huì)導(dǎo)致針對(duì)該字段（其它行）的增刪改阻塞（對(duì)其它非索引字段的操作無(wú)影響），是一種索引段級(jí)鎖。具體請(qǐng)參看 深入解析B-Tree索引與Bitmap位圖索引的鎖代價(jià)。
下面說(shuō)說(shuō)筆者知道的一些全文搜索的工具。
文中綠色文字表示筆者并不確定描述是否正確，紅色表示筆者疑問(wèn)，若有知道的同學(xué)請(qǐng)不吝賜教，多謝！
