目錄
前言：
什麼是反向索引?
FST原理簡析
如何聯合索引查詢？
前言：
Elasticsearch 是通過 Lucene 的反向索引技術實作比關系型資料庫更快的過濾。特别是它對多條件的過濾支援非常好，比如年齡在 18 和 30 之間，性别為女性這樣的組合查詢。但是其比關系型資料庫的 b-tree 索引快在哪裡？到底為什麼快呢？
籠統的來說，b-tree 索引是為寫入優化的索引結構。當我們不需要支援快速的更新的時候，可以用預先排序等方式換取更小的存儲空間，更快的檢索速度等好處，其代價就是更新慢。
什麼是B-Tree索引？
什麼是反向索引?
為了可以更清晰的表述，首先建立一個索引，并存儲若幹資料，建立的索引名稱為student，它有5個字段，分别是id,name,age,gender,address. 下面是建立索引和存儲資料的DSL語句：
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | |
将student索引轉換成關系型資料庫的一張表的話，大概是下面這個樣子:
下面介紹幾個在反向索引中比較重要的名詞:
Term（單詞）：一段文本經過分析器分析以後就會輸出一串單詞，這一個一個的就叫做Term.
Term Dictionary（單詞字典）：顧名思義，它裡面維護的是Term，可以了解為Term的集合. Elasticsearch為了能快速找到某個term，将所有的term排個序，二分法查找term，logN的查找效率，就像通過字典查找一樣。
Term Index（單詞索引）：為了更快的找到某個單詞，我們為單詞建立索引.
Posting List（倒排清單）：倒排清單記錄了出現過某個單詞的所有文檔的文檔清單及單詞在該文檔中出現的位置資訊，每條記錄稱為一個倒排項(Posting)。根據倒排清單，即可獲知哪些文檔包含某個單詞
實際的倒排清單中并不隻是存了文檔ID那麼簡單，還有一些其它的資訊，比如：詞頻（Term出現的次數）、偏移量（offset）等。
如果将反向索引類比成現代漢語詞典的話，那麼Term就相當于詞語，Term Dictionary相當于漢語詞典本身，Term Index相當于詞典的目錄索引。
每個文檔都有一個ID，如果插入的時候沒有指定ID的話，ElasticSearch會自動生成一個。
上面的例子，ElasticSearch建立的索引大緻如下：
ElasticSearch分别為上面的每個字段都建立了一個反向索引。比如，在上面“櫻木花道”、“男”、18這些都是Term，而[1,2]就是Posting List。Posting List就是一個數組，存儲了所有符合某個Term的文檔ID.
隻要知道文檔ID，就能快速找到文檔，可是要怎樣通過我們給定的關鍵詞快速找到這個Term呢？答案當然是：建立索引，也就是上文中所提到的Term Index（單詞索引）
在反向索引中，通過Term Index可以找到Term在Term Dictionary中的位置，進而找到Posting List，有了倒排清單就可以根據ID找到文檔了
其實我們前面分了三步，我們可以把Term Index 和 Term Dictionary看成一步，就是找Term。是以，可以這樣了解反向索引：通過單詞找到對應的倒排清單，根據倒排清單中的倒排項進而可以找到文檔記錄。
接下來我們詳細的介紹一下Term Index :
B-Tree通過減少磁盤尋道次數來提高查詢性能，Elasticsearch也是采用同樣的思路，直接通過記憶體查找term，不讀磁盤，但是如果term太多，term dictionary也會很大，放記憶體不現實，于是有了Term Index，就像字典裡的索引頁一樣，A開頭的有哪些Term,分别在哪頁，可以了解Term Index是一棵樹，如下圖所示：
注意：這棵樹不會包含所有的term，它包含的是term的一些字首
通過term index可以快速地定位到term dictionary的某個offset，然後從這個位置再往後順序查找。查找Term →Term Index → Term Dictionary → Posting List在ElasticSearch的過程如下圖所示:
是以Term Index 不需要存下所有的Term，而僅僅是他們的一些字首與Term Dictionary的block之間的映射關系，再結合FST(Finite State Transducers)的壓縮技術，可以使Term Index緩存到記憶體中。從Term Index查到對應的Term Dictionary的block位置之後，再去磁盤上找Term,大大減少了磁盤随機讀的次數。
現在我們可以回答“為什麼 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 次數。
FST原理簡析
FST有兩個優點：
1）空間占用小。通過對詞典中單詞字首和字尾的重複利用，壓縮了存儲空間；
2）查詢速度快。O(len(str))的查詢時間複雜度。
下面簡單描述下FST的構造過程。我們對“cat”、 “deep”、 “do”、 “dog” 、“dogs”這5個單詞進行插入建構FST（注：必須已排序）
1）插入“cat”
插入cat，每個字母形成一條邊，其中t邊指向終點。
2）插入“deep”
與前一個單詞“cat”進行最大字首比對，發現沒有比對則直接插入，P邊指向終點。
3）插入“do”
與前一個單詞“deep”進行最大字首比對，發現是d，則在d邊後增加新邊o，o邊指向終點。
4）插入“dog”
與前一個單詞“do”進行最大字首比對，發現是do，則在o邊後增加新邊g，g邊指向終點。
5）插入“dogs”
與前一個單詞“dog”進行最大字首比對，發現是dog，則在g後增加新邊s，s邊指向終點。
最終我們得到了如上一個有向無環圖。利用該結構可以很友善的進行查詢。
如給定一個term “dog”，我們可以通過上述結構很友善的查詢存不存在，甚至我們在建構過程中可以将單詞與某一數字、單詞進行關聯，進而實作key-value的映射。
如何聯合索引查詢？
是以給定查詢過濾條件 age=18 的過程就是先從 term index 找到 18 在 term dictionary 的大概位置，然後再從 term dictionary 裡精确地找到 18 這個 term，然後得到一個 posting list 或者一個指向 posting list 位置的指針。然後再查詢 gender= 女 的過程也是類似的。最後得出 age=18 AND gender= 女 就是把兩個 posting list 做一個“與”的合并。這個理論上的“與”合并的操作可不容易。對于 mysql 來說，如果你給 age 和 gender 兩個字段都建立了索引，查詢的時候隻會選擇其中最 selective 的來用，然後另外一個條件是在周遊行的過程中在記憶體中計算之後過濾掉。 那麼要如何才能聯合使用兩個索引呢？有兩種辦法：
1）使用 skip list 資料結構。同時周遊 gender 和 age 的 posting list，互相 skip。
2）使用 bitset 資料結構，對 gender 和 age 兩個 filter 分别求出 bitset，對兩個 bitset 做 AN 操作。
Elasticsearch 支援以上兩種的聯合索引方式，如果查詢的 filter 緩存到了記憶體中（以 bitset 的形式），那麼合并就是兩個 bitset 的 AND。如果查詢的 filter 沒有緩存，那麼就用 skip list 的方式去周遊兩個 on disk 的 posting list。
如何利用Skip List合并
以上是三個 posting list。我們現在需要把它們用 AND 的關系合并，得出 posting list 的交集。首先選擇最短的 posting list，然後從小到大周遊。周遊的過程可以跳過一些元素，比如我們周遊到綠色的 13 的時候，就可以跳過藍色的 3 了，因為 3 比 13 要小。
最後得出的交集是 [13,98]，所需的時間比完整周遊三個 posting list 要快得多。但是前提是每個 list 需要指出 Advance 這個操作，快速移動指向的位置。什麼樣的 list 可以這樣 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 編碼。
比如一個詞對應的文檔id清單為[73, 300, 302, 332,343, 372] ，id清單首先要從小到大排好序；第一步增量編碼就是從第二個數開始每個數存儲與前一個id的內插補點，即300-73=227，302-300=2。。。，一直到最後一個數；第二步就是将這些內插補點放到不同的區塊，Lucene使用256個區塊，下面示例為了友善展示使用了3個區塊，即每3個數一組；第三步位壓縮，計算每組3個數中最大的那個數需要占用bit位數，比如30、11、29中最大數30最小需要5個bit位存儲，這樣11、29也用5個bit位存儲，這樣才占用15個bit，不到2個位元組，壓縮效果很好，如下面原理圖所示：
考慮到頻繁出現的 term（所謂 low cardinality 的值），比如 gender 裡的男或者女。如果有 1 百萬個文檔，那麼性别為男的 posting list 裡就會有 50 萬個 int 值。用 Frame of Reference 編碼進行壓縮可以極大減少磁盤占用。這個優化對于減少索引尺寸有非常重要的意義。當然 mysql b-tree 裡也有一個類似的 posting list 的東西，是未經過這樣壓縮的。因為這個 Frame of Reference 的編碼是有解壓縮成本的。利用 skip list，除了跳過了周遊的成本，也跳過了解壓縮這些壓縮過的 block 的過程，進而節省了 cpu。
如何利用bitset合并
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 遍。