上一篇文章簡單地介紹過了ES的相關概念，還沒看的同學快去複習下： ES是什麼？看完這篇就不要再問這種低級問題了！文章的最後提到了倒排索引，不知道有沒有勾起大家的好奇心，ES的索引是怎麼做，為什麼他會被廣泛地叫做搜尋引擎而不是資料庫？根源在它的索引，所以這一篇帶你一探究竟。言歸正傳，說起索引肯定是繞不開經典的B-Tree，來看兩張圖簡單回顧下你們大學的課本內容。
B-Tree
B-Tree
B+Tree是B-Tree的優化，兩者的區別由圖應該是可以看得比較清楚的。
- 非葉子節點只存儲鍵值信息。
- 所有葉子節點之間都有一個鏈指針。
- 數據記錄都存放在葉子節點中。
籠統的來說，b-tree 索引是為寫入優化的索引結構。所以當我們不需要支持快速的更新的時候，可以用預先排序等方式換取更小的存儲空間，更快的檢索速度等好處，其代價就是更新慢。要進一步深入的化，還是要看一下 Lucene 的倒排索引是怎麼構成的。
看個具體的倒排索引實例，寫入如下三條數據；
ID是Elasticsearch自建的文檔id，那麼Elasticsearch建立的索引如下:
Name
Sex
問題來了，在Term量非常大的時候，怎麼快速找到目標Term的位置？來看看ES是怎麼做的。
Term Dictionary：把Term按字典序排列，然後用二分法查找Term （存在磁碟）
Term Index：是Term Dictionary的索引，存Term的前綴，和與該前綴對應的Term Dictionary中的第一個Term的block的位置，找到這個第一個Term後會再往後順序查找，直到找到目標Term。（存在內存）
Term Index的壓縮
所以，理論上Term Index的數據結構就是：Map
- 每條邊有兩條屬性，一個表示label（key的元素,上圖有點問題，應該是指向a的），另一個表示Value(out)。
- 每個節點有兩個屬性，Final=true/false（有key再這個節點結束則為true）；final為true時，還有個FinalOut，FinalOut=entry的value值-該路徑out值之和。
- 舉個例子：8號節點，對應的entry的key是do，value是15，而該路徑out值之和是2，所以FinalOut=15-2=13
- out值怎麼來的？
- 當只有一條數據寫入時如cat，則第一個位元組即「c」的out值就等於該entry的value值即「5」；
- 當deep寫入時因為後面d開頭的數據還沒寫，所以「d」的out值就是「10」；
- 當do寫入時，因為「d」=「10」，所以「o」=「15」-「10」=「5」
- 當dog寫入時，因為「d」=「10」，「o」=「5」，已經超過了dog的值「2」，此時，會把「d」設為「2」，「o」設為「0」，這樣才能滿足dog=「2」的情況。
- 但是，這樣deep和do的out值就要重新分配了
- deep的整條路徑和為「10」，已知「d」=「2」，所以「e」承包剩下的「8」。
- do的整條路徑和為「15」，已經「d」=「2」，「o」=「0」，沒有label了，所以FinalOut=15-2-0=13。
由上所述，不難得出，FST查詢的複雜度時O(1)，能快速定位到目的Term前綴的Block位置。
Posting List的壓縮關鍵在於：增量編碼壓縮，將大數變小數，按位元組存儲。原理就是通過增量，將原來的大數變成小數僅存儲增量值，再精打細算按bit排好隊，最後通過位元組存儲。
BitMaps
假設有某個posting list： [1,3,4,7,10]
對應的bitmap就是： [1,0,1,1,0,0,1,0,0,1]
用0/1表示某個值是否存在，比如10這個值就對應第10位，對應的bit值是1，這樣用一個位元組就可以代表8個文檔id，舊版本(5.0之前)的Lucene就是用這樣的方式來壓縮的，但這樣的壓縮方式仍然不夠高效，如果有1億個文檔，那麼需要12.5MB的存儲空間，這僅僅是對應一個索引欄位(我們往往會有很多個索引欄位)。Bitmap的缺點是存儲空間隨著文檔個數線性增長。
Roaring bitmaps
將posting list按照65535為界限分塊，比如第一塊所包含的文檔id範圍在065535之間，第二塊的id範圍是65536131071，以此類推。再用<商，餘數>的組合表示每一組id，這樣每組裡的id範圍都在0~65535內了，剩下的就好辦了，既然每組id不會變得無限大，那麼我們就可以通過最有效的方式對這裡的id存儲。short[] 占的空間：2bytes（65535 = 2^16-1 是2bytes 能表示的最大數）bitmap 占的空間: 65536/8 = 8192bytes當block塊里元素個數不超過4096，用short[]，因為4096個short[]才等於 8192bytes；而一個bitmap就等於8192bytes了，雖然它能存65536個元素。
聯合索引聯合索引通俗地說就是找到滿足多個搜索條件的文檔ID。那麼這種場景下，倒排索引如何滿足快速查詢的要求呢？
- 利用跳表(Skip list)的數據結構快速做「與」運算，或者
- 利用上面提到的bitset按位「與」
先看看跳表的數據結構：
將一個有序鍊表level0，挑出其中幾個元素到level1及level2，每個level越往上，選出來的指針元素越少，查找時依次從高level往低查找，比如55，先找到level2的31，再找到level1的47，最後找到55，一共3次查找，查找效率和2叉樹的效率相當，但也是用了一定的空間冗餘來換取的。假設有下面三個posting list需要聯合索引：
如果使用跳表，對最短的posting list中的每個id，逐個在另外兩個posting list中查找看是否存在，最後得到交集的結果。如果使用bitset，就很直觀了，直接按位與，得到的結果就是最後的交集。