來源：架構師之路
常見的文本檢索方案有哪些？
（1）數據庫LIKE法
將標題數據存放在數據庫中，使用like來查詢，方案非常簡單，能支持簡單的模糊搜索，但不支持分詞。
畫外音：顯然不適用于本例。
（2）數據庫全文檢索法
將標題數據存放在數據庫中，建立全文索引來檢索，方然依然簡單，利用了數據庫的能力，不用額外開發，但性能較低。
畫外音： 本例的并發肯定扛不住。
（3）開源方案索引外置 法
搭建lucene，solr，ES等開源搜索工具，建立索引，支持分詞，支持數據量和吞吐量的水平擴展。
該方案能夠很好的滿足本例的需求。但是，殺雞焉用牛刀，本例有一些業務特性： 文本短，更新不頻繁 ，如果利用好這兩個特點，能有更巧妙的方案。
畫外音： 任何脫離業務的架構設計，都是耍流氓。
針對“更新不頻繁”的特性 ，可以使用“ 分詞+DAT ”方案。
畫外音：分詞就不多說了。
什么是DAT？
DAT是double array trie的縮寫，是trie樹的一個變體優化數據結構，它在保證trie樹檢索效率的前提下，能大大減少內存的使用，經常用來解決檢索，信息過濾等問題。
畫外音：更具體的，可以google一下“DAT”，DAT的缺點是，需要提前建立索引，索引不能實時更新。
為什么用trie樹的變種DAT， 是否可以 直接使用trie樹呢？
trie樹的優點是，索引可以實時更新；不足是，占用內存非常大。
本例索引無需實時更新，無法利用trie樹的優點。但是，如果300W短文本建立好trie樹內存能裝下，則可以使用trie樹，否則只能使用DAT。
普及， 什么是trie樹？
trie樹，又稱單詞查找樹，經常 用于搜索引擎詞頻統計，短文本檢索，輸入法輸入提示等。
畫外音：什么數據結構適合什么業務場景，一定要爛熟于胸。
它的特點是，能利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較， 其查詢時間復雜度只與樹的高度有關，與查詢數據量級無關 ，因此查詢效率非常高。
畫外音：“時間復雜度與查詢數量級無關”這個太屌了。
例如： 上面的trie樹就能夠表示｛and, as, at, cn, com｝這樣5個標題的集合，可以用來做這5個字符串的詞頻統計，或者檢索。
畫外音：檢索時，節點存儲命中該item的doc_list<doc_id>。
分詞之后，是不是需要多次掃描trie樹？
是的。
分詞之后，每個item都要掃描一次trie樹，得到的doc_list<doc_id>的交集，就是最終命中每個item的檢索結果。
針對“短文本”“500W數據”“不頻繁更新”這些特性 ，還能使用“ 分詞+內存hash ”方案。
這個方案需要 先對索引進行初始化 ：
對所有短文本進行分詞，以詞的hash為key，doc_id的集合為value。
查詢的過程 也很簡單：
對查詢字符串進行分詞，對每個分詞進行hash，直接查詢hash表格得到doc_list<doc_id>，再對每個分詞的檢索結果進行交集。
舉個栗子進行說明。
例如：
doc1 : 我愛北京
doc2 : 我愛到家
doc3 : 到家美好
先對短文本進行分詞：
doc1 : 我愛北京 -> 我，愛，北京
doc2 : 我愛到家 -> 我，愛，到家
doc3 : 到家美好 -> 到家，美好
對分詞進行hash，建立hash表：
hash(我) -> {doc1, doc2}
hash(愛) -> {doc1, doc2}
hash(北京) -> {doc1}
hash(到家) -> {doc2, doc3}
hash(美好) -> {doc3}
這樣，所有短文本初始化完畢，與trie樹類似，查詢時間復雜度與文本數據量也沒有關系。
畫外音：只與被分詞后有多少數據量，即hash桶個數有關。
查詢的過程是這樣的：
假如用戶輸入“我愛”，分詞后變為{我，愛}，對各個分詞的hash進行內存檢索
hash(我)->{doc1, doc2}
hash(愛)->{doc1, doc2}
然后進行合并，得到最后的查找結果是{doc1, doc2}。
這個方法的 優點 是， 純內存操作，能滿足很大的并發，時延也很低，占用內存也不大，實現非常簡單快速，而且冗余索引很容易水平擴展。
畫外音： 做索引高可用也不難，建立兩份一樣的hash索引即可。
它的 缺點 也很明顯，索引全內存， 沒有落地，還是需要在數據庫中存儲固化的短文本數據，如果內存數據全丟失，數據恢復起來會比較慢。
總結
短文本，高并發，支持分詞，不用實時更新的檢索場景，可以使用：
（1）ES，殺雞用牛刀；
（2）分詞+DAT(trie)；
（3）分詞+內存hash；
等幾種方式解決。
思路比結論重要 ，希望大家有收獲。
