【Elasticsearch 7 探索之路】（三）倒排索引

Coder編程 2022-04-29

展開全文

上一篇，我們介紹了 ES 文檔的基本 CURE 和批量操作。我們都知道倒排索引是搜索引擎非常重要的一種數(shù)據(jù)結構，什么是倒排索引，倒排索引的原理是什么。

1 索引過程

在講解倒排索引前，我們先了解索引創(chuàng)建，下圖是 Elasticsearch 中數(shù)據(jù)索引過程的流程。

從上圖可以看到，文檔未在 ES 中進行索引，而是由 Analyzer 組件對其執(zhí)行一些操作并將其拆分為 token/term。然后將這些術語作為倒排索引存儲在磁盤中。假設我們有兩個名為 name 和 age 字段，當要將文檔索引到 ES 時，Analyzers 組件以某些定界符（有默認定界符，例如空格，句號等）將它們分割開獲取 token，再對每個 token 應用特定的過濾器。經(jīng)過分析的這些標記稱為 term。然后將這些 term 針對該字段）存儲在倒排列表中。

2 倒排索引

2.1 正排與倒排索引

一般在我們閱讀圖書，我們會根據(jù)目錄快速定位想要閱讀的章節(jié)，過了一段時間，你想要的回顧之前某一個知識點，你發(fā)現(xiàn)從目錄難以查找到對應的地方，這時你可能就會從索引頁從去查找對應內(nèi)容索引，從而找到頁碼。

搜索引擎其實跟我們的使用圖書很相似，下面我來對圖書和搜索引擎進行一個簡單的類比，來看一下搜素引擎中正排和倒排索引。

圖書
- 正排索引-目錄頁
- 倒排索引-索引頁
搜索引擎
- 正排索引-文檔 Id 到文檔內(nèi)容和單詞的關聯(lián)
- 倒排索引-單詞到文檔 Id 的關系

2.2 倒排索引的核心組成

舉個例子，假設我們有 3 個文檔：

Doc 1:breakthrough drug for schizophrenia

Doc 2:new schizophrenia drug 

Doc 3:new approach for treatment of schizophrenia

經(jīng)過分析，文件中的術語如下

文檔	分詞結果
Doc 1	breakthrough,drug,for,schizophrenia
Doc 2	new,schizophrenia,drug
Doc 3	new,approach,for,treatment,of

倒排列表的元數(shù)據(jù)結構：

(DocID;TF;<POS>)

其中：

DocID：出現(xiàn)某單詞的文檔ID
TF(詞頻)：單詞在該文檔中出現(xiàn)的次數(shù)
POS：單詞在文檔中的位置

則它們生成的倒排索引

單詞	逆向文檔頻率	倒排列表(DocID;TF;))
breakthrough	1	(1;1;<1>)
drug	2	(1;1;<2>),(2;1;<3>)
for	2	(1;1;<3>),(3;1;<3>)
schizophrenia	2	(1;1;<4>),(2;1;<2>)
new	2	(2;1;<1>),(3;1;<1>)
approach	1	(3;1;<2>)
treatment	1	(3;1;<4>)
of	1	(3;1;<5>)

ES 倒排索引包含兩個部分
- 單詞詞典（Term Dictionary)，索引最小單位，記錄所有文檔的單詞，記錄單詞到倒排列表的關聯(lián)關系
  - 單詞詞典一般都會非常多，通過 B+ 樹或 Hash 表方式以滿足高性能的插入與查詢
- 倒排列表（Posting List)-由倒排索引項（Posting）組成
  - 文檔 ID
  - 詞頻 TF，該單詞在文檔中出現(xiàn)的次數(shù)，用于相關性評分
  - 位置（Position)，單詞在文檔中分詞的位置。用于語句搜索（phrase query)
  - 偏移（Offset)，記錄單詞的開始結束位置，實現(xiàn)高亮顯示