Chapter+4+搜索引擎索引

1、Chapter 4 Chapter 4 搜索引擎索引搜索引擎索引陳珂銳陳珂銳計算機與信息工程學院計算機與信息工程學院快訊快訊o5500萬美元融資后，知乎聯合搜狗升級用戶搜索體驗目錄目錄o1.單詞詞典單詞詞典o2.倒排列表倒排列表o3.建立索引建立索引o4.動態(tài)索引動態(tài)索引o5.索引更新策略索引更新策略o6.查詢處理查詢處理o7.多字段索引多字段索引o8.短語查詢短語查詢o9.分布式索引分布式索引1.單詞詞典單詞詞典o哈希加鏈表o樹形結構1.單詞詞典單詞詞典-哈希加鏈表哈希加鏈表1.單詞詞典單詞詞典-樹形結構樹形結構2.倒排列表（倒排列表（1）2.倒排列表（倒排列表（2）3.建立索引建立索引o兩

2、遍文檔遍歷法（2-Pass In-Memory Inversion）o排序法（Sort-based Inversion）o歸并法（Merge-based Inversion）3.建立索引建立索引-兩遍文檔遍歷法兩遍文檔遍歷法3.建立索引建立索引-排序法（排序法（1）3.建立索引建立索引-排序法（排序法（2）3.建立索引建立索引-歸并法歸并法4.動態(tài)索引動態(tài)索引5.索引更新策略索引更新策略o完全重建策略（Complete Re-Build）o再合并策略（Re-Merge）o原地更新策略（In-Place）o混合策略（Hybrid）5.索引更新策略索引更新策略-完全重建策略完全重建策略5.索引更新

3、策略索引更新策略-再合并策略再合并策略5.索引更新策略索引更新策略-原地更新策略原地更新策略5.索引更新策略索引更新策略-混合策略混合策略o將單詞根據其不同性質進行分類，不同類別的單詞，對其索引采取不同的索引更新策略o將單詞的倒排列表長度進行區(qū)分，長倒排列表采取原地更新策略，短倒排列表采取再合并策略。6.查詢處理查詢處理o一次一文檔（Doc at a Time）o一次一單詞（Term at a Time）o跳躍指針（Skip Pointers）6.查詢處理查詢處理-一次一文檔一次一文檔6.查詢處理查詢處理-一次一單詞一次一單詞6.查詢處理查詢處理-跳躍指針跳躍指針6.查詢處理查詢處理-跳躍指針

4、跳躍指針7.多字段索引多字段索引o多索引方式o倒排列表方式o擴展列表方式7.多字段索引多字段索引-多索引方式多索引方式7.多字段索引多字段索引-倒排列表方式倒排列表方式7.多字段索引多字段索引-擴展列表方式擴展列表方式8.短語查詢短語查詢o位置信息索引（Position Index）o雙詞索引（Nextword Index）o短語索引（Phrase Index）o混合方法8.短語查詢短語查詢-位置信息索引位置信息索引8.短語查詢短語查詢-雙詞索引雙詞索引8.短語查詢短語查詢-短語索引短語索引8.短語查詢短語查詢-混合方法混合方法9.分布式索引分布式索引o按文檔劃分（Document Partitioning）o按單