檢索用的好，下班走的早！值得收藏

這篇文章是可樂花了很長時間總結(jié)出來的，注意：本篇文章不是教大家如何檢索，而是教大家如何設(shè)計檢索系統(tǒng)。

我從宏觀層面介紹了各種數(shù)據(jù)結(jié)構(gòu)和算法，并在結(jié)尾介紹了如何設(shè)計一個搜索系統(tǒng)，下面是本文目錄截圖，相信大家看完一定會有收獲的。

1、什么是檢索？

指從用戶特定的信息需求出發(fā)，對特定的信息集合采用一定的方法、技術(shù)手段，根據(jù)一定的線索與規(guī)則從中找出相關(guān)信息。

對應(yīng)到我們實(shí)際工作中，檢索其實(shí)就是：

如何用最小的內(nèi)存(物理成本)，最快（時間成本）的取出我們需要的數(shù)據(jù)。

2、檢索體系架構(gòu)

3、存儲介質(zhì)層

3.1 磁盤為什么能存儲數(shù)據(jù)

機(jī)械硬盤的磁盤主體是一塊金屬薄片（也有用其他材料的），上面涂覆一層磁性材料，可以理解為一層小磁針。

硬盤工作時，磁盤在馬達(dá)的驅(qū)動下高速旋轉(zhuǎn)，轉(zhuǎn)速高達(dá)數(shù)千轉(zhuǎn)每分鐘，磁頭則在磁頭驅(qū)動系統(tǒng)的的控制下，在高速旋轉(zhuǎn)的磁盤表面飛行。

①、寫數(shù)據(jù)

磁頭線圈上通電，在其周圍產(chǎn)生磁場，磁化磁盤表面的磁性材料，不同方向的電流產(chǎn)生的磁場方向不同，磁盤表面的磁性材料被磁化的極性也不同，不同極性便代表0與1；

②、讀數(shù)據(jù)

磁頭線圈切割磁盤表面的磁性材料的磁場，產(chǎn)生電信號，不同極性的磁性材料產(chǎn)生的感應(yīng)電流方向不同，因此可以讀出0與1。

注意：斷電并不會影響磁盤表面的磁性材料的極性，因此斷電后數(shù)據(jù)仍然不會消失，但劇烈的碰撞或加熱則有可能導(dǎo)致數(shù)據(jù)丟失。

3.2 磁盤和內(nèi)存的區(qū)別

①、持久性

磁盤能永久存儲（HDD10年，SDD5年），斷電不丟失數(shù)據(jù)；

內(nèi)存斷電即丟失數(shù)據(jù)。

②、容量

磁盤通常是幾百G到幾個T；

內(nèi)存通常是幾個G到幾十個G。

③、價格

內(nèi)存 > 磁盤

④、讀寫速度

內(nèi)存 > SDD > HDD

4、數(shù)據(jù)結(jié)構(gòu)層

4.1 數(shù)組

1.數(shù)組是相同數(shù)據(jù)類型的元素的集合。

2.數(shù)組各元素是按照先后順序連續(xù)存儲的。

3.插入慢：無序數(shù)組末尾插入快，其余情況需要維護(hù)數(shù)組地址連續(xù)效率都是比較差。

4.查找：支持下標(biāo)隨機(jī)查找快，有序數(shù)組也可以用諸如二分法加快查找速度。

5.刪除慢：和插入類似，除了末尾插入快。其余情況需要維護(hù)數(shù)組地址連續(xù)都比較慢。

4.2 鏈表

1.鏈表物理存儲單元上非連續(xù)（可以充分利用計算機(jī)內(nèi)存）、非順序的存儲結(jié)構(gòu)。

2.不支持隨機(jī)讀取。

3.存儲空間會增大，比如單向鏈表每個節(jié)點(diǎn)都會存儲下一個節(jié)點(diǎn)的引用。

4.插入快。

5.刪除快。

6.查找慢。

其余比如棧、隊列、二叉樹，紅黑樹，B+樹等等都是這兩種數(shù)據(jù)結(jié)構(gòu)的單獨(dú)變化或組合變化。

4.3 棧

棧只支持兩個基本操作：入棧 push()和出棧 pop()。

典型應(yīng)用：

①、實(shí)現(xiàn)字符串逆序；

②、判斷標(biāo)簽是否匹配；

③、計算機(jī)中的函數(shù)調(diào)用；

4.4 隊列

和棧類似，也只支持兩個操作：入隊 enqueue()，放一個數(shù)據(jù)到隊列尾部；出隊 dequeue()，從隊列頭部取一個元素。

①、單向隊列（Queue）：只能在一端插入數(shù)據(jù)，另一端刪除數(shù)據(jù)。

②、雙向隊列（Deque）：每一端都可以進(jìn)行插入數(shù)據(jù)和刪除數(shù)據(jù)操作。

③、優(yōu)先級隊列（Priority Queue）：數(shù)據(jù)項(xiàng)按照關(guān)鍵字進(jìn)行排序，關(guān)鍵字最?。ɑ蛘咦畲螅┑臄?shù)據(jù)項(xiàng)往往在隊列的最前面，而數(shù)據(jù)項(xiàng)在插入的時候都會插入到合適的位置以確保隊列的有序。

④、阻塞隊列（Block Queue）：在隊列為空的時候，從隊頭取數(shù)據(jù)會被阻塞。因?yàn)榇藭r還沒有數(shù)據(jù)可取，直到隊列中有了數(shù)據(jù)才能返回；如果隊列已經(jīng)滿了，那么插入數(shù)據(jù)的操作就會被阻塞，直到隊列中有空閑位置后再插入數(shù)據(jù)，然后再返回。

典型的生產(chǎn)者-消費(fèi)者模型。

⑤、并發(fā)隊列

典型應(yīng)用：

①、線程池

②、數(shù)據(jù)庫連接池

對于大部分資源有限的場景，當(dāng)沒有空閑資源時，基本上都可以通過“隊列”這種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)請求排隊。

4.5 樹

①、二叉樹

②、紅黑樹

③、B+樹

典型應(yīng)用：關(guān)系型數(shù)據(jù)庫存儲數(shù)據(jù)結(jié)構(gòu)。

1.數(shù)據(jù)很大，不可能全部存儲在內(nèi)存中，還要持久化，故要存儲到磁盤上。

2.減少查找過程中磁盤I/O的存取次數(shù)。

局部性原理：當(dāng)一個數(shù)據(jù)被用到時，其附近的數(shù)據(jù)也通常會馬上被使用。

與磁盤預(yù)讀，預(yù)讀的長度一般為頁（page）的整倍數(shù)，（在許多操作系統(tǒng)中，頁得大小通常為4k）

葉子節(jié)點(diǎn)數(shù)據(jù)多。

3.支持范圍查找

④、LSM 樹

Log Structured Merge Trees

一個日志系統(tǒng)有如下特征：

一、數(shù)據(jù)量大且持續(xù)生成

二、寫入操作會特別頻繁

三、查詢快，且查詢一般不是全范圍的隨機(jī)搜索，而是近期檢索。

B+ 樹為什么不行？（葉子節(jié)點(diǎn)存儲在磁盤中，需要隨機(jī)寫磁盤，數(shù)據(jù)量大會導(dǎo)致性能急劇下降）

LSM 樹：

⑤、Trie 樹

字典樹、前綴樹、單詞查找樹。

典型應(yīng)用：

字符串檢索

百度谷歌搜索框

拼寫檢查

4.6 跳表

鏈表的基礎(chǔ)上增加了多級索引。

Redis 中的有序集合（Sorted Set）就是用跳表來實(shí)現(xiàn)的。

4.7 散列表

通過把關(guān)鍵值映射到表中一個位置來訪問記錄，這個映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

解決哈希沖突：

①、開放尋址法：線性探測、雙重散列

②、鏈表法

散列表設(shè)計原則：

①、散列函數(shù)

②、初始容量；

③、裝載因子；

④、散列沖突解決辦法；

典型應(yīng)用：

①、有限的數(shù)據(jù)集合中快速查詢數(shù)據(jù)

比如：Word 文檔中單詞拼寫檢查功能是如何實(shí)現(xiàn)的？

常用的英文單詞有 20 萬個左右，假設(shè)單詞的平均長度是 10 個字母，平均一個單詞占用 10 個字節(jié)的內(nèi)存空間，那 20 萬英文單詞大約占 2MB 的存儲空間，就算放大 10 倍也就是 20MB。

所以可以將全部英文單詞放到散列表，用戶輸入單詞直接去散列表里面查，沒有就報錯。

②、詞頻統(tǒng)計、訪問統(tǒng)計等等。

4.8 布隆過濾器

簡單來說就是一個二進(jìn)制數(shù)組。

典型應(yīng)用：數(shù)據(jù)海量，不要求一定準(zhǔn)確的場景。

①、判斷ID是否已經(jīng)注冊，即使誤判也能容忍。

②、爬蟲判斷網(wǎng)頁是否已經(jīng)爬過。

4.9 圖

存儲：

①、鄰接矩陣

②、鄰接表

DFS（Deep First Search）深度優(yōu)先搜索算法

BFS（Breath First Search）廣度優(yōu)先搜索算法

飛機(jī)航線

電子線路

城市地圖

好友關(guān)系

5、算法層

比較好用的查找算法是二分法O(logn)，在有序的數(shù)據(jù)結(jié)構(gòu)中是特別bug的，但是如何進(jìn)行快速的排序，有如下常用的排序算法：

實(shí)際應(yīng)用：

①、如何根據(jù)年齡給100W用戶排序？

利用桶排序，從1歲到150歲（有人會說超過150歲，這里超過三界之外的人不算），建立150個桶，然后遍歷這100W個用戶，依次放入150個桶中，遍歷完，邊排好序了。

②、如何快速查詢每個考生的高考排名？

同樣也是桶排序，高考分?jǐn)?shù)0-750，也就是頂多 750 個桶。

6、業(yè)務(wù)設(shè)計層

6.1 爬蟲系統(tǒng)

通過高性能的爬蟲系統(tǒng)來完成網(wǎng)頁的持續(xù)抓取，然后將抓取到的網(wǎng)頁存入存儲平臺中。

一般來說是是將抓取到的網(wǎng)頁存放在基于 LSM 的 HBase 中，以便支持?jǐn)?shù)據(jù)的高效讀寫。

①、爬取網(wǎng)頁

首先找到權(quán)重較高的網(wǎng)頁，比如新浪、騰訊，通過廣度優(yōu)先搜索算法放入爬取隊列中；

計算網(wǎng)頁權(quán)重算法：PageRank

網(wǎng)頁太多，持久化隊列，便于斷點(diǎn)爬取。

如何爬取網(wǎng)頁鏈接：可以獲取到網(wǎng)頁的 HTML 文件，看成一個大的字符串，然后利用字符串匹配算法，獲取 或者這樣的標(biāo)簽內(nèi)容。

②、網(wǎng)頁去重

利用布隆過濾器。

需要注意的是：布隆過濾器是在內(nèi)存中的，如果機(jī)器重啟，布隆過濾器就會被清空，防止網(wǎng)頁重復(fù)爬取，需要持久化布隆過濾器，比如定時每半小時持久化一次。

③、原始網(wǎng)頁存儲

便于后面的離線分析，索引構(gòu)建，需要將海量的原始網(wǎng)頁存儲。

網(wǎng)頁很多，通常的文件系統(tǒng)不適合存儲這么多的文件，而是將多個網(wǎng)頁存儲在一個文件中。

④、網(wǎng)頁編號和鏈接存儲

上一步給每個網(wǎng)頁分配了一個id，在存儲網(wǎng)頁的同時，也將網(wǎng)頁編號和網(wǎng)頁鏈接存儲在一個文件中。

6.2 分析索引系統(tǒng)

①、抽取網(wǎng)頁文本信息

網(wǎng)頁都是遵循 HTML 規(guī)范的，只需要去掉JavaScript代碼、CSS代碼，還有比如下拉框的代碼。

在網(wǎng)頁這個大字符串中，一次性查找 , ,

②、網(wǎng)頁質(zhì)量分析

去掉低質(zhì)量的垃圾網(wǎng)頁

③、反作弊

避免一些作弊網(wǎng)頁來干擾搜索結(jié)果

④、分詞創(chuàng)建臨時索引

抽取到網(wǎng)頁文本信息之后，對文本信息進(jìn)行分詞，并創(chuàng)建臨時索引文件。

英文網(wǎng)頁：只需要通過空格、標(biāo)點(diǎn)符號等分隔符，將每個單詞分割開來就可以了。

中文網(wǎng)頁：借助詞庫并采用最長匹配規(guī)則，來對文本進(jìn)行分詞。

臨時索引文件如下：

注意這里存的是單詞編號，因?yàn)閱卧~很多，為了節(jié)省內(nèi)存，用一個散列表存儲：單詞編號-單詞。

⑤、通過臨時索引創(chuàng)建倒排索引

⑥、記錄單詞編號在倒排索引文件的偏移位置

幫助我們快速地查找某個單詞編號在倒排索引中存儲的位置，進(jìn)而快速地從倒排索引中讀取單詞編號對應(yīng)的網(wǎng)頁編號列表。

6.3 查詢

doc_id.bin：記錄網(wǎng)頁鏈接和編號之間的對應(yīng)關(guān)系。

term_id.bin：記錄單詞和編號之間的對應(yīng)關(guān)系。

index.bin：倒排索引文件，記錄每個單詞編號以及對應(yīng)包含它的網(wǎng)頁編號列表。

term_offsert.bin：記錄每個單詞編號在倒排索引文件中的偏移位置。

①、當(dāng)用戶在搜索框中，輸入某個查詢文本的時候，我們先對用戶輸入的文本進(jìn)行分詞處理。假設(shè)分詞之后，我們得到 k 個單詞。

然后對這 k 個單詞進(jìn)行糾錯模型判斷：

②、糾錯完成之后，我們拿這 k 個單詞，去 term_id.bin 對應(yīng)的散列表中，查找對應(yīng)的單詞編號。經(jīng)過這個查詢之后，我們得到了這 k 個單詞對應(yīng)的單詞編號。

③、我們拿這 k 個單詞編號，去 term_offset.bin 對應(yīng)的散列表中，查找每個單詞編號在倒排索引文件中的偏移位置。經(jīng)過這個查詢之后，我們得到了 k 個偏移位置。

④、我們拿這 k 個偏移位置，去倒排索引（index.bin）中，查找 k 個單詞對應(yīng)的包含它的網(wǎng)頁編號列表。經(jīng)過這一步查詢之后，我們得到了 k 個網(wǎng)頁編號列表。

⑤、我們針對這 k 個網(wǎng)頁編號列表，統(tǒng)計每個網(wǎng)頁編號出現(xiàn)的次數(shù)。具體到實(shí)現(xiàn)層面，我們可以借助散列表來進(jìn)行統(tǒng)計。統(tǒng)計得到的結(jié)果，我們按照出現(xiàn)次數(shù)的多少，從小到大排序。出現(xiàn)次數(shù)越多，說明包含越多的用戶查詢單詞（用戶輸入的搜索文本，經(jīng)過分詞之后的單詞）。

經(jīng)過這一系列查詢，我們就得到了一組排好序的網(wǎng)頁編號。我們拿著網(wǎng)頁編號，去 doc_id.bin 文件中查找對應(yīng)的網(wǎng)頁鏈接，分頁顯示給用戶就可以了。

10、總結(jié)

檢索核心思路：通過合理的組織數(shù)據(jù)，盡可能的快速減少查詢范圍。

①、合理選擇存儲介質(zhì)、存儲數(shù)據(jù)結(jié)構(gòu)；

②、合理創(chuàng)建索引，使得索引和數(shù)據(jù)分離；

③、減少磁盤IO，將頻繁讀取的數(shù)據(jù)加載到內(nèi)存中；

④、讀寫分離；

⑤、分層處理；