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有詳細的解釋。
這裏先埋壹個坑，將來有時間再來填。