當前位置:成語大全網 - 新華字典 - Elasticsearch:ES 倒排索引為什麽查詢速度會這麽快

Elasticsearch:ES 倒排索引為什麽查詢速度會這麽快

Elasticsearch 是壹個分布式可擴展的實時搜索和分析引擎,它建立在全文搜索引擎 Apache Lucene? 的基礎上。Elasticsearch 之所以可以實現近乎實時的檢索,依靠的技術手段是非常多的,本文將從 反向索引、Term Index 兩塊知識點入手,分析 Elasticsearch 之所以那麽快的原因。

在上表所展示的 “文檔-關鍵詞” 矩陣索引中,如果用戶使用搜索引擎查找目標關鍵字(比如 火星 ),搜索引擎就會從索引庫中所有的關鍵字包含 火星 的文檔,也就是 web_x_1、web_x_2 ,並根據網頁文件自身的價值評分高低(比如關鍵詞出現的次數)按順序展示給用戶,用戶得到的就是 按順序 展示的 web_x_2 web_x_1 兩個網頁。這就是正向索引實現的大致流程。

在這個矩陣中, 火星 關鍵詞對應的所有網頁都被提前找到,甚至網頁文檔的權重都被提前計算好並排序,當用戶輸入 火星 關鍵詞時,就會立刻到 web_x_2, web_x_1 的反饋結果。

這裏有些人會有疑問,關鍵詞數量會不會太多,以至於超過網頁問的數量,這樣效率不會反而變低了麽,其實不然,人類的語言詞匯數量是相對有限、且固定的,但網頁數量卻沒有上限。比如漢語中,漢字30000個、詞匯大概40萬,但漢語網站數量卻遠遠不止這麽些。

需要註意的是,由於每個字或詞對應的文檔數量在動態變化,所以倒排表的建立和維護都較為復雜,但是在查詢的時候由於可以壹次得到查詢關鍵字所對應的所有文檔,所以效率高於正排表。

針對這個表,Elasticsearch 會創建如下的索引:

索引壹: Name

索引二: Color

索引三: Rate

在這個索引中,Name、Color、Rate 這些字段被稱為 filed , iphone 666 plus、blue、middle 這些被稱作 Term ,而 Term 對應的所有商品的 id 比如 [1, 3] 就是 Posting List

當用戶要查找 Color=blue 的商品時,通過索引三的 Term 和 Posting List 很快就可以找到,目標是 id 為 2 的商品,進而通過索引壹找到商品 Name 為 華為 mate 98k。

上面簡單解釋了 Term 和 Posting List,但實際生產中 Elasticsearch 需要面對的是數以億計的數據記錄,數據的 Term 的數量是驚人的,這樣往往需要花費大量時間才能命中,而且多數時候查找是多條件查找,這就需要多次進行重復查找,效率仍然不高。

這時就需要對 Term 進行優化排序,即使用 二分查找 查找 Term,這種查找方法類似於通過字典查找,被稱為 Term Dictionary 。

同樣是上面的例子,Name、Color、Rate 三個索引下所有的 Term,按照 首字母在英語字母表中位置 排序後如下:

當用戶想要查找 rate 為 high 的商品時,通過二分法很快就可以查到,查找過程的時間復雜度為 log N,這樣就大大提高了查找的速度。關於二分查找,細節這裏就不做贅述了,如果不清楚的朋友們可以自行百度,或點擊 二分查找 獲取更多信息。

到這裏很多人會有疑問,那這和傳統的 B-tree 有什麽區別呢,這就需要引入另壹個概念 Term Index。

Term Index 其實也可以理解為壹個樹形結構,從 Term 的第壹個字母開始進行第壹層排序,如果有多個 Term 首字母相同,則從該字母為起始點進行第二層排序,如果以該字母為首的只有壹個 Term,則不再進行第二次排序。

同樣是上面的例子,其 Term Index 如下圖所示:

在上圖中,字母 b 為首的 Term 有兩個,分別為 blue 和 black,這時就需要進行第二層排序,即對第二位字母進行排序,這時我們發現兩個 Term 的第二位字母都為 l,於是進行第三層排序,第三層排序的結果是 bla、blu ,分別對應 black、blue 兩個 Term,並對應 [1, 3]、2 兩個 Posting List。對應關系如下圖所示:

在 Term Index 中需要保存的是 Term 的前面部分字段,以及與 Term Dictionary 之間的映射關系,這使得存儲的信息量減少。再結合 FST(Finite State Transducer)壓縮技術,Term Iindex 可以被壓縮到足夠小,以至於可以被緩存進服務器內存中。這樣,在用戶查找的時候,先在內存裏從 Term Index 找到 Term Dictionary 中的位置映射關系,然後再去磁盤上找對應的 Term,進而查找對應的 Posting List,這就大大減少了磁盤的讀取次數,也就提高了效率和速度。

關於 FST 壓縮技術,請參考這篇文章: /blog/2018/12/04/lucene-fst/ ,英語好的可以看下這篇論文 https://cs.nyu.edu/~mohri/pub/fla.pdf ,裏面對FST有詳細的解釋。

這裏先埋壹個坑,將來有時間再來填。