搜尋引擎背後的資料結構與演算法#

搜尋引擎是技術驅動的產品典範，涉及大量經典的資料結構與演算法。

整體架構#

搜集 → 分析 → 索引 → 查詢

搜集階段#

網頁爬取#

將網際網路視為有向圖，使用廣度優先搜尋 (BFS) 策略：

1. 從種子網頁（高權重網站首頁）開始
2. 解析頁面中的連結，加入待爬取佇列
3. 持續爬取直到達到目標

為什麼用 BFS 而非 DFS？

• 離種子頁面越近，權重通常越高
• 優先爬取重要頁面
• 避免陷入低質量網站的深層頁面

核心檔案#

網頁判重#

使用布隆過濾器：

• 10 億網頁，100 億位元 ≈ 1.2 GB
• 定期持久化到磁碟，支援宕機恢復

分析階段#

1. 抽取網頁文本#

使用 AC 自動機（多模式串匹配）移除：

• <style>...</style>
• <script>...</script>
• <option>...</option>

2. 分詞#

使用 Trie 樹 + 最長匹配規則：

文本：「中國人民解放了」
詞庫：中國、中國人、中國人民、中國人民解放軍

結果：「中國人民」+「解放」+「了」

3. 建立臨時索引#

term_id | doc_id
--------|--------
   1    |   10
   2    |   10
   1    |   15

索引階段#

倒排索引 (Inverted Index)#

term_id | doc_ids
--------|------------------
   1    | [10, 15, 23, ...]
   2    | [10, 42, ...]

建立流程#

1. 對臨時索引按 term_id 排序（歸併排序，處理大檔案）
2. 順序走訪，合併相同 term_id 的記錄
3. 建立 term_offset.bin 記錄每個單詞在索引中的偏移位置

臨時索引（排序前）:
term1 -> doc10
term2 -> doc10
term1 -> doc15

臨時索引（排序後）:
term1 -> doc10
term1 -> doc15
term2 -> doc10

倒排索引:
term1 -> [doc10, doc15]
term2 -> [doc10]

查詢階段#

查詢流程#

1. 分詞：用戶輸入 → k 個單詞
2. 查編號：term_id.bin → k 個單詞編號
3. 查偏移：term_offset.bin → k 個偏移位置
4. 查網頁列表：index.bin → k 個網頁列表
5. 排序：統計每個網頁出現次數，排序輸出
6. 返回結果：doc_id.bin → 網頁連結

性能優化#

• 除倒排索引外，其他檔案載入記憶體
• 使用散列表組織，O(1) 查詢

涉及的資料結構與演算法#

搜尋引擎是資料結構與演算法的綜合應用典範。掌握這些基礎知識後，理解 Elasticsearch 等搜尋引擎的原理會容易許多。