這裏有篇 文章 講解的很形象：
這是集群cluster。
這是節點Node：就是個機器。
由壹個或者多個節點，多個綠色小方塊組合在壹起形成壹個ElasticSearch的索引。
在壹個索引下，分布在多個節點裏的綠色小方塊稱為分片：Shard。
壹個分片就是壹個Lucene Index。
在Lucene裏面有很多小的Segment，即為存儲的最小管理單元。
我們分別從Node維度、Shard維度、Segment維度來闡明為啥Elasticsearch這麽快。
多節點的集群方案，提高了整個系統的並發處理能力。
路由壹個文檔到壹個分片中：當索引壹個文檔的時候，文檔會被存儲到壹個主分片中。 Elasticsearch 如何知道壹個文檔應該存放到哪個分片中呢？實際上，這個過程是根據下面這個公式決定的：
routing 是壹個可變值，默認是文檔的 _id ，也可以設置成壹個自定義的值。這就解釋了為什麽我們要在創建索引的時候就確定好主分片的數量，並且永遠不會改變這個數量：因為如果數量變化了，那麽所有之前路由的值都會無效，文檔也再也找不到了。
確定了在哪個分片中，繼而可以判定其在哪個節點上。
那麽主分片數確定的情況下，如果做集群擴容呢？下圖是壹種主分片的擴容辦法，開始設置為5個分片，在單個節點上，後來擴容到5個節點，每個節點有壹個分片。也就是說單個分片的容量變大了，但是數量並不增加。
節點分為主節點 Master Node、數據節點 Data Node和客戶端節點 Client Node（單純為了做請求的分發和匯總）。每個節點都可以接受客戶端的請求，每個節點都知道集群中任壹文檔位置，所以可以直接將請求轉發到需要的節點上。當接受請求後，節點變為「協調節點」。從這個角度，整個系統可以接受更高的並發請求，當然搜索的就更快了。
以更新文檔為例：
Elasticsearch 中使用的這種方法假定沖突是不可能發生的，並且不會阻塞正在嘗試的操作。因為沒有阻塞，所以提升了索引的速度，同時可以通過 _version 字段來保證並發情況下的正確性：
控制在我們索引中的文檔只有現在的 _version 為 1 時，本次更新才能成功。
可以設置分片的副本數量來提升高並發場景下的搜索速度，但是同時會降低索引的效率。
在底層采用了分段的存儲模式，使它在讀寫時幾乎完全避免了鎖的出現，大大提升了讀寫性能。
怎樣在保留不變性的前提下實現倒排索引的更新？即用上文提到的 _version ，創建更多的索引文檔。實際上壹個 UPDATE 操作包含了壹次 DELETE 操作（僅記錄標誌待Segment Merge 的時候才真正刪除）和壹次 CREATE 操作。
為了提升寫索引速度，並且同時保證可靠性，Elasticsearch 在分段的基礎上，增加了壹個 translog ，或者叫事務日誌，在每壹次對 Elasticsearch 進行操作時均進行了日誌記錄。
Segment在被refresh之前，數據保存在內存中，是不可被搜索的，這也就是為什麽 Lucene 被稱為提供近實時而非實時查詢的原因。
但是如上這種機制避免了隨機寫，數據寫入都是 Batch 和 Append，能達到很高的吞吐量。同時為了提高寫入的效率，利用了文件緩存系統和內存來加速寫入時的性能，並使用日誌來防止數據的丟失。
LSM-Tree 示意圖如下，可見 Lucene 的寫入思想和 LSM-Tree 是壹致的：
終於說到倒排索引了，都說倒排索引提升了搜索的速度，那麽具體采用了哪些架構或者數據結構來達成這壹目標？
如上是Lucene中實際的索引結構。用例子來說明上述三個概念：
ID是文檔id，那麽建立的索引如下:
Name：
Age：
Sex：
可見為每個 field 都建立了壹個倒排索引。Posting list就是壹個int的數組，存儲了所有符合某個term的文檔id。實際上，除此之外還包含：文檔的數量、詞條在每個文檔中出現的次數、出現的位置、每個文檔的長度、所有文檔的平均長度等，在計算相關度時使用。
假設我們有很多個 term，比如：
如果按照這樣的順序排列，找出某個特定的 term 壹定很慢，因為 term 沒有排序，需要全部過濾壹遍才能找出特定的 term。排序之後就變成了：
這樣我們可以用二分查找的方式，比全遍歷更快地找出目標的 term。這個就是 term dictionary。有了 term dictionary 之後，可以用 logN 次磁盤查找得到目標。
但是磁盤的隨機讀操作仍然是非常昂貴的（壹次 random access 大概需要 10ms 的時間）。所以盡量少的讀磁盤，有必要把壹些數據緩存到內存裏。但是整個 term dictionary 本身又太大了，無法完整地放到內存裏。於是就有了 term index。term index 有點像壹本字典的大的章節表。比如：
A 開頭的 term ……………. Xxx 頁
C 開頭的 term ……………. Yyy 頁
E 開頭的 term ……………. Zzz 頁
如果所有的 term 都是英文字符的話，可能這個 term index 就真的是 26 個英文字符表構成的了。但是實際的情況是，term 未必都是英文字符，term 可以是任意的 byte 數組。而且 26 個英文字符也未必是每壹個字符都有均等的 term，比如 x 字符開頭的 term 可能壹個都沒有，而 s 開頭的 term 又特別多。實際的 term index 是壹棵 trie 樹：
例子是壹個包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 樹。這棵樹不會包含所有的 term，它包含的是 term 的壹些前綴。通過 term index 可以快速地定位到 term dictionary 的某個 offset，然後從這個位置再往後順序查找。
現在我們可以回答“為什麽 Elasticsearch/Lucene 檢索可以比 mysql 快了。Mysql 只有 term dictionary 這壹層，是以 b-tree 排序的方式存儲在磁盤上的。檢索壹個 term 需要若幹次的 random access 的磁盤操作。而 Lucene 在 term dictionary 的基礎上添加了 term index 來加速檢索，term index 以樹的形式緩存在內存中。從 term index 查到對應的 term dictionary 的 block 位置之後，再去磁盤上找 term，大大減少了磁盤的 random access 次數。
實際上，Lucene 內部的 Term Index 是用的「變種的」trie樹，即 FST 。FST 比 trie樹好在哪？trie樹只***享了前綴，而 FST 既***享前綴也***享後綴，更加的節省空間。
壹個FST是壹個6元組 (Q, I, O, S, E, f):
例如有下面壹組映射關系：
可以用下圖中的FST來表示：
這篇文章講的很好： 關於Lucene的詞典FST深入剖析
想想為啥不用 HashMap，HashMap 也能實現有序Map？耗內存啊！犧牲了壹點性能來節約內存，旨在把所有Term Index都放在內存裏面，最終的效果是提升了速度。如上可知，FST是壓縮字典樹後綴的圖結構，她擁有Trie高效搜索能力，同時還非常小。這樣的話我們的搜索時，能把整個FST加載到內存。
總結壹下，FST有更高的數據壓縮率和查詢效率，因為詞典是常駐內存的，而 FST 有很好的壓縮率，所以 FST 在 Lucene 的最新版本中有非常多的使用場景，也是默認的詞典數據結構。
Lucene 的tip文件即為 Term Index 結構，tim文件即為 Term Dictionary 結構。由圖可視，tip中存儲的就是多個FST，
FST中存儲的是<單詞前綴，以該前綴開頭的所有Term的壓縮塊在磁盤中的位置>。即為前文提到的從 term index 查到對應的 term dictionary 的 block 位置之後，再去磁盤上找 term，大大減少了磁盤的 random access 次數。
可以形象地理解為，Term Dictionary 就是新華字典的正文部分包含了所有的詞匯，Term Index 就是新華字典前面的索引頁，用於表明詞匯在哪壹頁。
但是 FST 即不能知道某個Term在Dictionary(.tim)文件上具體的位置，也不能僅通過FST就能確切的知道Term是否真實存在。它只能告訴妳，查詢的Term可能在這些Blocks上，到底存不存在FST並不能給出確切的答案，因為FST是通過Dictionary的每個Block的前綴構成，所以通過FST只可以直接找到這個Block在.tim文件上具體的File Pointer，並無法直接找到Terms。
回到上面的例子，給定查詢過濾條件 age=24 的過程就是先從 term index 找到 18 在 term dictionary 的大概位置，然後再從 term dictionary 裏精確地找到 18 這個 term，然後得到壹個 posting list 或者壹個指向 posting list 位置的指針。然後再查詢 sex=Female 的過程也是類似的。最後得出 age= 24 AND sex=Female 就是把兩個 posting list 做壹個“與”的合並。
這個理論上的“與”合並的操作可不容易。對於 mysql 來說，如果妳給 age 和 gender 兩個字段都建立了索引，查詢的時候只會選擇其中最 selective 的來用，然後另外壹個條件是在遍歷行的過程中在內存中計算之後過濾掉。那麽要如何才能聯合使用兩個索引呢？有兩種辦法：
Elasticsearch 支持以上兩種的聯合索引方式，如果查詢的 filter 緩存到了內存中（以 bitset 的形式），那麽合並就是兩個 bitset 的 AND。如果查詢的 filter 沒有緩存，那麽就用 skip list 的方式去遍歷兩個 on disk 的 posting list。
用壹個例子來說明如何使用 skip list 的思路來做合並（參考 Lucene學習總結之七：Lucene搜索過程解析(5) ）：
Advance操作是什麽？就是 skip list 提供的快速跳躍的特性。
另外壹方面，對於壹個很長的 posting list，比如：
[1,3,13,101,105,108,255,256,257]
我們可以把這個 list 分成三個 block：
[1,3,13] [101,105,108] [255,256,257]
然後可以構建出 skip list 的第二層：
[1,101,255]
1,101,255 分別指向自己對應的 block。這樣就可以很快地跨 block 的移動指向位置了。
Lucene 自然會對這個 block 再次進行壓縮。其壓縮方式叫做 Frame Of Reference 編碼。示例如下：
考慮到頻繁出現的 term（所謂 low cardinality 的值），比如 gender 裏的男或者女。如果有 1 百萬個文檔，那麽性別為男的 posting list 裏就會有 50 萬個 int 值。用 Frame of Reference 編碼進行壓縮可以極大減少磁盤占用。這個優化對於減少索引尺寸有非常重要的意義。當然 mysql b-tree 裏也有壹個類似的 posting list 的東西，是未經過這樣壓縮的。
因為這個 Frame of Reference 的編碼是有解壓縮成本的。利用 skip list，除了跳過了遍歷的成本，也跳過了解壓縮這些壓縮過的 block 的過程，從而節省了 cpu。
這也可以看到，Lucene 為了省內存真是做到了極致。
Bitset 是壹種很直觀的數據結構，對應 posting list 如：
[1,3,4,7,10]
對應的 bitset 就是：
[1,0,1,1,0,0,1,0,0,1]
每個文檔按照文檔 id 排序對應其中的壹個 bit。Bitset 自身就有壓縮的特點，其用壹個 byte 就可以代表 8 個文檔。所以 100 萬個文檔只需要 12.5 萬個 byte。但是考慮到文檔可能有數十億之多，在內存裏保存 bitset 仍然是很奢侈的事情。而且對於個每壹個 filter 都要消耗壹個 bitset，比如 age=18 緩存起來的話是壹個 bitset，18<=age<25 是另外壹個 filter 緩存起來也要壹個 bitset。
所以秘訣就在於需要有壹個數據結構：
可以很壓縮地保存上億個 bit 代表對應的文檔是否匹配 filter；
這個壓縮的 bitset 仍然可以很快地進行 AND 和 OR 的邏輯操作。
Lucene 使用的這個數據結構叫做 Roaring Bitmap。
其壓縮的思路其實很簡單。與其保存 100 個 0，占用 100 個 bit。還不如保存 0 壹次，然後聲明這個 0 重復了 100 遍。
為什麽是以65535為界限？程序員的世界裏除了1024外，65535也是壹個經典值，因為它=2^16-1，正好是用2個字節能表示的最大數，壹個short的存儲單位，註意到上圖裏的最後壹行“If a block has more than 4096 values, encode as a bit set, and otherwise as a simple array using 2 bytes per value”，如果是大塊，用節省點用bitset存，小塊就豪爽點，2個字節我也不計較了，用壹個short[]存著方便。
在 Lucene 7.0之後，Lucene 針對 bitset的稠稀性，采用不同的存儲方式：當 bitset比較稀疏時，直接存儲DocID；當 bitset 稠密時，則直接存儲 bitset 的Bits數據。根據數據的分布情況不同，采用適當的結構不僅可以提高空間的利用率，還能提高遍歷的效率。
Elasticsearch/Lucene 為了提升索引和搜索的效率，從上層到底層，使用了各種巧妙的數據結構和設計，靠優秀的理論加極致的優化，做到查詢性能上的極致。