一、需求緣起
某併發量很大，資料量適中的業務線需要實現一個“標題檢索”的功能：
（1）併發量較大，每秒20w次
（2）資料量適中，大概200w資料
（3）是否需要分詞：是
（4）資料是否實時更新：否
二、常見潛在解決方案及優劣
（1）資料庫搜尋法
具體方法：將標題資料存放在資料庫中，使用like來檢索
優點：方案簡單
缺點：不能實現分詞，併發量扛不住
（2）資料庫全文檢索法
具體方法：將標題資料存放在資料庫中，建立全文索引來檢索
缺點：併發量扛不住
（3）使用開源方案將索引外接
具體方法：搭建lucene，solr，ES等開源外接索引方案
優點：效能比上面兩種好
缺點：併發量可能有風險，系統比較重，為一個簡單的業務搭建一套這樣的系統成本較高
三、58的建議
問1：58同城第一屆程式設計大賽的題目好像是“黃反詞過濾”，你是冠軍，當時是用DAT來實現的麼？
是的
畫外音：什麼是DAT？
普及：DAT是double array trie的縮寫，是trie樹的一個變體最佳化資料結構，它在保證trie樹檢索效率的前提下，能大大減少記憶體的使用，經常用來解決檢索，資訊過濾等問題。（具體大夥百度一下“DAT”）
問2：上面的業務場景可以使用DAT來實現麼？
DAT更新資料比較麻煩，不能增量
問3：那直接使用trie樹可以麼？
trie樹比較佔記憶體
畫外音：什麼是trie樹？
普及：trie樹，又稱單詞查詢樹，是一種樹形結構，是一種雜湊樹的變種。典型應用是用於統計，儲存大量的字串（但不僅限於字串），所以經常被搜尋引擎系統用於文字詞頻統計。它的優點是：利用字串的公共字首來減少查詢時間，最大限度地減少無謂的字串比較，查詢效率比雜湊樹高。
例如：上面的trie樹就能夠表示｛and, as, at, cn, com｝這樣5個標題的集合。
問4：如果要支援分詞，多個分詞遍歷trie樹，還需要合併對吧？
沒錯，每個分詞遍歷一次trie樹，可以得到doc_id的list，多個分詞得到的list合併，就是最終的結果。
問5：還有什麼更好，更輕量級的方案麼？
用trie樹，資料會膨脹文件數*標題長度這麼多，標題越長，文件數越多，記憶體佔用越大。有個一個方案，記憶體量很小，和標題長度無關，非常帥氣。
問6：有相關文章麼，推薦一篇？
可能網上沒有，我簡單說一下吧，核心思想就是“記憶體hash ＋ ID list”
索引初始化步驟為：對所有標題進行分詞，以詞的hash為key，doc_id的集合為value
查詢的步驟為：對查詢詞進行分詞，對分詞進行hash，直接查詢hash表格，獲取doc_id的list，然後多個詞進行合併
=====例子=====
例如：
doc1 : 我愛北京
doc2 : 我愛到家
doc3 : 到家美好
先標題進行分詞：
doc1 : 我愛北京 -> 我，愛，北京
doc2 : 我愛到家 -> 我，愛，到家
doc3 : 到家美好 -> 到家，美好
對分詞進行hash，建立hash + ID list：
hash(我) -> {doc1, doc2}
hash(愛) -> {doc1, doc2}
hash(北京) -> {doc1}
hash(到家) -> {doc2, doc3}
hash(美好) -> {doc3}
這樣，所有標題的初始化就完畢了，你會發現，資料量和標題的長度沒有關係。
使用者輸入“我愛”，分詞後變為{我，愛}，對各個分詞的hash進行記憶體檢索
hash(我)->{doc1, doc2}
hash(愛)->{doc1, doc2}
然後進行合併，得到最後的查詢結果是doc1+doc2。
=====例子END=====
問7：這個方法有什麼優點呢？
存記憶體操作，能滿足很大的併發，時延也很低，佔用記憶體也不大，實現非常簡單快速
問8：有什麼不足呢？和傳統搜尋有什麼區別咧？
這是一個快速過度方案，因為索引本身沒有落地，還是需要在資料庫中儲存固化的標題資料，如果不做高可用，資料恢復起來會比較慢。當然做高可用也是很容易的，建立兩份一樣的hash索引即可。另外，沒有做水平切分，但資料量非常非常非常大時，還是要做水平切分改進的。
一、需求緣起
某併發量很大，資料量適中的業務線需要實現一個“標題檢索”的功能：
（1）併發量較大，每秒20w次
（2）資料量適中，大概200w資料
（3）是否需要分詞：是
（4）資料是否實時更新：否
二、常見潛在解決方案及優劣
（1）資料庫搜尋法
具體方法：將標題資料存放在資料庫中，使用like來檢索
優點：方案簡單
缺點：不能實現分詞，併發量扛不住
（2）資料庫全文檢索法
具體方法：將標題資料存放在資料庫中，建立全文索引來檢索
優點：方案簡單
缺點：併發量扛不住
（3）使用開源方案將索引外接
具體方法：搭建lucene，solr，ES等開源外接索引方案
優點：效能比上面兩種好
缺點：併發量可能有風險，系統比較重，為一個簡單的業務搭建一套這樣的系統成本較高
三、58的建議
問1：58同城第一屆程式設計大賽的題目好像是“黃反詞過濾”，你是冠軍，當時是用DAT來實現的麼？
是的
畫外音：什麼是DAT？
普及：DAT是double array trie的縮寫，是trie樹的一個變體最佳化資料結構，它在保證trie樹檢索效率的前提下，能大大減少記憶體的使用，經常用來解決檢索，資訊過濾等問題。（具體大夥百度一下“DAT”）
問2：上面的業務場景可以使用DAT來實現麼？
DAT更新資料比較麻煩，不能增量
問3：那直接使用trie樹可以麼？
trie樹比較佔記憶體
畫外音：什麼是trie樹？
普及：trie樹，又稱單詞查詢樹，是一種樹形結構，是一種雜湊樹的變種。典型應用是用於統計，儲存大量的字串（但不僅限於字串），所以經常被搜尋引擎系統用於文字詞頻統計。它的優點是：利用字串的公共字首來減少查詢時間，最大限度地減少無謂的字串比較，查詢效率比雜湊樹高。
例如：上面的trie樹就能夠表示｛and, as, at, cn, com｝這樣5個標題的集合。
問4：如果要支援分詞，多個分詞遍歷trie樹，還需要合併對吧？
沒錯，每個分詞遍歷一次trie樹，可以得到doc_id的list，多個分詞得到的list合併，就是最終的結果。
問5：還有什麼更好，更輕量級的方案麼？
用trie樹，資料會膨脹文件數*標題長度這麼多，標題越長，文件數越多，記憶體佔用越大。有個一個方案，記憶體量很小，和標題長度無關，非常帥氣。
問6：有相關文章麼，推薦一篇？
可能網上沒有，我簡單說一下吧，核心思想就是“記憶體hash ＋ ID list”
索引初始化步驟為：對所有標題進行分詞，以詞的hash為key，doc_id的集合為value
查詢的步驟為：對查詢詞進行分詞，對分詞進行hash，直接查詢hash表格，獲取doc_id的list，然後多個詞進行合併
=====例子=====
例如：
doc1 : 我愛北京
doc2 : 我愛到家
doc3 : 到家美好
先標題進行分詞：
doc1 : 我愛北京 -> 我，愛，北京
doc2 : 我愛到家 -> 我，愛，到家
doc3 : 到家美好 -> 到家，美好
對分詞進行hash，建立hash + ID list：
hash(我) -> {doc1, doc2}
hash(愛) -> {doc1, doc2}
hash(北京) -> {doc1}
hash(到家) -> {doc2, doc3}
hash(美好) -> {doc3}
這樣，所有標題的初始化就完畢了，你會發現，資料量和標題的長度沒有關係。
使用者輸入“我愛”，分詞後變為{我，愛}，對各個分詞的hash進行記憶體檢索
hash(我)->{doc1, doc2}
hash(愛)->{doc1, doc2}
然後進行合併，得到最後的查詢結果是doc1+doc2。
=====例子END=====
問7：這個方法有什麼優點呢？
存記憶體操作，能滿足很大的併發，時延也很低，佔用記憶體也不大，實現非常簡單快速
問8：有什麼不足呢？和傳統搜尋有什麼區別咧？
這是一個快速過度方案，因為索引本身沒有落地，還是需要在資料庫中儲存固化的標題資料，如果不做高可用，資料恢復起來會比較慢。當然做高可用也是很容易的，建立兩份一樣的hash索引即可。另外，沒有做水平切分，但資料量非常非常非常大時，還是要做水平切分改進的。