摘要：?jiǎn)桚埜纾€有什么更好，更輕量級(jí)的方案么龍哥用樹(shù)，數(shù)據(jù)會(huì)膨脹文檔數(shù)標(biāo)題長(zhǎng)度這么多，標(biāo)題越長(zhǎng)，文檔數(shù)越多，內(nèi)存占用越大。

一、需求緣起
某并發(fā)量很大，數(shù)據(jù)量適中的業(yè)務(wù)線需要實(shí)現(xiàn)一個(gè)“標(biāo)題檢索”的功能：
（1）并發(fā)量較大，每秒20w次
（2）數(shù)據(jù)量適中，大概200w數(shù)據(jù)
（3）是否需要分詞：是
（4）數(shù)據(jù)是否實(shí)時(shí)更新：否

二、常見(jiàn)潛在解決方案及優(yōu)劣
（1）數(shù)據(jù)庫(kù)搜索法
具體方法：將標(biāo)題數(shù)據(jù)存放在數(shù)據(jù)庫(kù)中，使用like來(lái)檢索
優(yōu)點(diǎn)：方案簡(jiǎn)單
缺點(diǎn)：不能實(shí)現(xiàn)分詞，并發(fā)量扛不住

（2）數(shù)據(jù)庫(kù)全文檢索法
具體方法：將標(biāo)題數(shù)據(jù)存放在數(shù)據(jù)庫(kù)中，建立全文索引來(lái)檢索
優(yōu)點(diǎn)：方案簡(jiǎn)單
缺點(diǎn)：并發(fā)量扛不住

（3）使用開(kāi)源方案將索引外置
具體方法：搭建lucene，solr，ES等開(kāi)源外置索引方案
優(yōu)點(diǎn)：性能比上面兩種好
缺點(diǎn)：并發(fā)量可能有風(fēng)險(xiǎn)，系統(tǒng)比較重，為一個(gè)簡(jiǎn)單的業(yè)務(wù)搭建一套這樣的系統(tǒng)成本較高

三、58龍哥的建議
問(wèn)1：龍哥，58同城第一屆編程大賽的題目好像是“黃反詞過(guò)濾”，你是冠軍，當(dāng)時(shí)是用DAT來(lái)實(shí)現(xiàn)的么？
龍哥：是的
畫(huà)外音：什么是DAT？
普及：DAT是double array trie的縮寫(xiě)，是trie樹(shù)的一個(gè)變體優(yōu)化數(shù)據(jù)結(jié)構(gòu)，它在保證trie樹(shù)檢索效率的前提下，能大大減少內(nèi)存的使用，經(jīng)常用來(lái)解決檢索，信息過(guò)濾等問(wèn)題。（具體大伙百度一下“DAT”）

問(wèn)2：上面的業(yè)務(wù)場(chǎng)景可以使用DAT來(lái)實(shí)現(xiàn)么？
龍哥：DAT更新數(shù)據(jù)比較麻煩，不能增量

問(wèn)3：那直接使用trie樹(shù)可以么？
龍哥：trie樹(shù)比較占內(nèi)存
畫(huà)外音：什么是trie樹(shù)？
普及：trie樹(shù)，又稱單詞查找樹(shù)，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì)，保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)減少查詢時(shí)間，最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希樹(shù)高。（來(lái)源：百度百科）

例如：上面的trie樹(shù)就能夠表示｛and, as, at, cn, com｝這樣5個(gè)標(biāo)題的集合。

問(wèn)4：如果要支持分詞，多個(gè)分詞遍歷trie樹(shù)，還需要合并對(duì)吧？
龍哥：沒(méi)錯(cuò)，每個(gè)分詞遍歷一次trie樹(shù)，可以得到doc_id的list，多個(gè)分詞得到的list合并，就是最終的結(jié)果。

問(wèn)5：龍哥，還有什么更好，更輕量級(jí)的方案么？
龍哥：用trie樹(shù)，數(shù)據(jù)會(huì)膨脹文檔數(shù)*標(biāo)題長(zhǎng)度這么多，標(biāo)題越長(zhǎng)，文檔數(shù)越多，內(nèi)存占用越大。有個(gè)一個(gè)方案，內(nèi)存量很小，和標(biāo)題長(zhǎng)度無(wú)關(guān)，非常帥氣。

問(wèn)6：有相關(guān)文章么，推薦一篇？
龍哥：可能網(wǎng)上沒(méi)有，我簡(jiǎn)單說(shuō)一下吧，核心思想就是“內(nèi)存hash ＋ ID list”
索引初始化步驟為：對(duì)所有標(biāo)題進(jìn)行分詞，以詞的hash為key，doc_id的集合為value
查詢的步驟為：對(duì)查詢?cè)~進(jìn)行分詞，對(duì)分詞進(jìn)行hash，直接查詢hash表格，獲取doc_id的list，然后多個(gè)詞進(jìn)行合并
=====例子=====
例如：
doc1 : 我愛(ài)北京
doc2 : 我愛(ài)到家
doc3 : 到家美好
先標(biāo)題進(jìn)行分詞：
doc1 : 我愛(ài)北京 -> 我，愛(ài)，北京
doc2 : 我愛(ài)到家 -> 我，愛(ài)，到家
doc3 : 到家美好 -> 到家，美好
對(duì)分詞進(jìn)行hash，建立hash + ID list：
hash(我) -> {doc1, doc2}
hash(愛(ài)) -> {doc1, doc2}
hash(北京) -> {doc1}
hash(到家) -> {doc2, doc3}
hash(美好) -> {doc3}
這樣，所有標(biāo)題的初始化就完畢了，你會(huì)發(fā)現(xiàn)，數(shù)據(jù)量和標(biāo)題的長(zhǎng)度沒(méi)有關(guān)系。
用戶輸入“我愛(ài)”，分詞后變?yōu)閧我，愛(ài)}，對(duì)各個(gè)分詞的hash進(jìn)行內(nèi)存檢索
hash(我)->{doc1, doc2}
hash(愛(ài))->{doc1, doc2}
然后進(jìn)行合并，得到最后的查找結(jié)果是doc1+doc2。
=====例子END=====

問(wèn)7：這個(gè)方法有什么優(yōu)點(diǎn)呢？
龍哥：存內(nèi)存操作，能滿足很大的并發(fā)，時(shí)延也很低，占用內(nèi)存也不大，實(shí)現(xiàn)非常簡(jiǎn)單快速

問(wèn)8：有什么不足呢？和傳統(tǒng)搜索有什么區(qū)別咧？
龍哥：這是一個(gè)快速過(guò)度方案，因?yàn)樗饕旧頉](méi)有落地，還是需要在數(shù)據(jù)庫(kù)中存儲(chǔ)固化的標(biāo)題數(shù)據(jù)，如果不做高可用，數(shù)據(jù)恢復(fù)起來(lái)會(huì)比較慢。當(dāng)然做高可用也是很容易的，建立兩份一樣的hash索引即可。另外，沒(méi)有做水平切分，但數(shù)據(jù)量非常非常非常大時(shí)，還是要做水平切分改進(jìn)的。