前言

索引可能大家都不陌生，在用關系型資料庫時，一些頻繁用作查詢條件的欄位我們都會去建立索引來提升查詢效率，在關系型資料庫中，我們一般都采用 B 樹索引進行存盤，所以 B 樹索引也是我們接觸比較多的一種索引資料結構，然而在 es 中，進行全文搜索的時候卻并沒有選擇使用 B 樹 索引，而是采用的倒排索引，本文就讓我們來看看 es 中的倒排索引是如何存盤和檢索的吧，

為什么全文索引不使用 B+ 樹進行存盤

關系型資料庫，如 MySQL，其選擇的是 B+ 樹索引，如下圖就是一顆簡單的的 B+ 樹示例：

上圖中藍色的表示索引值，白色的表示指標，最底層葉子節點除了存盤索引值還會存盤整條資料（InnoDB 引擎），而根節點和枝節點不會存盤資料，B+ 樹之所以這么設計就是為了使得根節點和枝節點能夠存盤更多的節點，因為搜索的時候從根節點開始搜索，每查詢一個節點就是一次 IO 操作，所以一個節點能存盤更多的索引值能減少磁盤 IO 次數，

如果有想更詳細了解 B+ 樹的，可以點擊這里，

那么到這里我們就可以思考這個問題了，假如索引值本身就很大，那么 B+ 樹是不是性能會急劇下降呢？答案是肯定的，因為當索引值很大的話，一個節點能存盤的資料會大大減少（一個節點默認是 16kb 大小），B+ 樹就會變得更深，每次查詢資料所需要的 IO 次數也會更多，而且全文索引就是需要支持對大文本進行索引的，從空間上來說 B+ 樹不適合作為全文索引，同時 B+ 樹因為每次搜索都是從根節點開始往下搜索，所以會遵循最左匹配原則，而我們使用全文搜索時，往往不會遵循最左匹配原則，所以可能會導致索引失效，

總結起來 B+ 樹不適合作為全文搜索索引主要有以下兩個原因：

• 全文索引的文本欄位通常會比較長，索引值本身會占用較大空間，從而會加大 B+ 樹的深度，影響查詢效率，
• 全文索引往往需要全文搜索，不遵循最左匹配原則，使用 B+ 樹可能導致索引失效，

全文檢索

在全文檢索當中，我們需要對檔案進行切詞處理，切好之后再將切出來的詞和檔案進行關聯，并進行索引，那么這時候我們應該如何存盤關鍵字和檔案的對應關系呢？

正排索引

可能大家都知道，在全文檢索中（比如：Elasticsearch）用的是倒排索引，那么既然有倒排索引，自然就有正排索引，

正排索引又稱之為前向索引（forward index），我們以一篇檔案為例，那么正排索引可以理解成他是用檔案 id 作為索引關鍵字，同時記錄了這篇檔案中有哪些詞（經過分詞器處理），每個詞出現的次數已經每個詞在檔案中的位置，

但是我們平常在搜索的時候，都是輸入一個詞然后要得到檔案，所以很顯然，正排索引并不適合于做這種查詢，所以一般我們的全文檢索用的都是倒排索引，但是倒排索引卻并不適合用于聚合運算，所以其實在 es 中的聚合運算用的是正排索引，

倒排索引

倒排索引又稱之為反向索引（inverted index），和正排索引相反，倒排索引使用的是詞來作為索引關鍵字，并同時記錄了哪些檔案中有這個詞，

在這里我們以一個英文檔案為例子，之所以選擇用英文檔案是因為英文分詞比較簡單，直接以空格進行分詞即可，而中文分詞相對比較復雜，

我們以 Elasticsearch 官網中下面兩句話作為兩位檔案來分析：

Elasticsearch is the distributed search and analytics engine at the heart of the Elastic Stack.
Elasticsearch provides near real-time search and analytics for all types of data.

根據上面兩句話，假設我們可以得到下面這樣的一個索引結構：

其中：

• term index：顧名思議，這個是為 term（經過分詞后的每個詞） 建立的索引，也就是通過這個索引可以快速找到當前 term 的位置，從而找到對應的 Posting list，因為在 es 中，會為每個欄位都建立索引（默認存盤在記憶體中），所以當我們的資料量非常大的時候，就需要能快速定位到這個詞對應的索引所在的記憶體位置，所以就單獨為每個 term 建立了索引，這個索引一般可以選擇哈希表或者 B+ 樹進行索引存盤，
• term dictionary：記錄了檔案中去重后的所有詞（經過分詞器處理），
• Posting list TF：記錄了含有當前詞的檔案以及當前詞出現在檔案的位置（偏移量），該項資訊是一個陣列，上面表格中為了簡單只列舉了檔案 id，實際上這里會存盤很多資訊，

這時候假如我們搜索 Elasticsearch Elastic 這樣的關鍵字，那么會經過以下步驟：

1. 對輸入的關鍵字進行分詞處理，得到兩個詞：elasticsearch 和 elastic（經過分詞器之后大寫字母都會轉化成小寫字母），
   
2. 然后分別用這兩個詞進行搜索，搜索之后，發現 elasticsearch 在兩個檔案中都有出現，而 elastic 只在檔案一中出現，
3. 最終的搜索結果就是檔案一和檔案二都回傳，但是因為檔案一兩個詞都命中了，所以相關度（分數）更高，于是檔案一會排在檔案二前面，這就是算分的程序，不過需要注意的是，實際的這種相關度分數演算法不會這么簡單，而是有專門的演算法來計算，命中詞多的并不一定會出現在前面，

倒排索引如何存盤資料

知道了倒排索引的搜索程序，那么倒排索引的資料又是如何存盤的呢？

回答這個問題之前我們先來看另一個問題，那就是建立索引的目的是什么？最直接的目的肯定是為了加快檢索速度，而為了達到這個目的，那么在不考慮其他因素的情況下，必然是需要占用的空間越少越好，而為了減少占用空間，可能就需要壓縮之后再進行存盤，而壓縮之后又涉及到解壓縮，所以采用的壓縮演算法也需要能達到快速壓縮和解壓的目的，

FOR 壓縮

FOR 壓縮演算法即 Frame Of Reference，這種演算法比較簡單，也有一定的局限性，因為其對存盤的檔案 id 有一定要求，

假設現在有一億個檔案，對應的檔案 id 就是從 1 開始自增，假設現在關鍵字 elasticsearch 存在于 1000W 個檔案中，而這 1000W 個檔案恰好就是從 1 到 1000W，那么假如不采用任何壓縮演算法，直接進行存盤需要占用多少空間？

int 型別占用了 4 個位元組，而 1000W 這個數量級需要 2 的 24 次方，也就是說如果用二進制來存盤，在不考慮符號位的情況下也需要 24 個 bit 才能存盤，而因為 Posting list TF 是一個陣列，所以為了能決議出資料，檔案 id=1 的資料也需要用 24 個 bit 來進行存盤，這樣就會極大的浪費了空間，

為了解決這個問題，我們就需要使用 FOR 演算法，FOR 演算法并不直接存盤檔案 id，而是存盤差值，像這種這么規律的檔案 id，差值都是 1，而 1 轉成二進制就可以只使用 1 個 bit 進行存盤，這樣就只需要 1000W 個 bit 的空間來進行存盤就夠了，相比較直接存盤原始檔案 id 的情況下，這種場景采用 FOR 演算法大大減少了空間，

上面舉的這個例子是比較理想的情況，然而實際上這種概率是比較小的，那我們再來看下面這一組檔案 id：

1,9,15,45,68,323,457

這個陣列計算差值后得到下面這個陣列：

8,6,30,23,255,134

這個時候如果還是直接用普通差值的演算法，雖然也能節省空間，但是卻并不是最優的一種解決方案，那么這個時候有沒有一種更高效的方法來進行存盤呢？

我們觀察下這個差值陣列，發現這個陣列可以進一步拆分成兩組：

• [8,6,30,23]：這一組最大值為 30，只需要 5 個位元就能進行存盤，
• [255,134]：這一組最大值為 255，需要 8 個位元就能存盤，

這么拆分之后，原始資料需要用 32*7=224 個位元（原始資料直接用 int 存盤），普通差值需要 8*6=48 個位元，而經過分組差值拆分之后只需要 5*4+8*2=36 個位元，進一步壓縮了空間，這種優勢隨著資料量的增加會更加明顯，

但是不管采用哪種方案都有一個問題，那就是進行差值或者拆分之后，怎么還原資料，解壓的時候怎么知道差值陣列內的元素占用空間大小？

所以對每一個資料，還需要一塊一個位元組的空間大小來存盤當前陣列內元素占用的位元數，所以分組并不是越細越好，假如對每一個差值元素都單獨存盤，那么反而會比不分組更浪費空間，反之，如果每個分組內的元素足夠多，那么存盤占用空間的這一個位元組反帶來的影響就會更小或者忽略不計，

RBM 壓縮

上面例子中介紹的差值都不會大相徑庭，那么假如我們差值計算之后得到的陣列，其每個元素差別都很大呢？比如說下面這個檔案 id 陣列：

1000,62101,131385,132052,191173,196658

這個陣列大家可以去計算一下差值，計算之后會發現一個大一個小，兩個差值之間差距很大，所以這種方式就不適合于用 FOR 壓縮，所以我們就需要有另外的壓縮演算法來提升效率，這就是 RBM 壓縮，

RBM 壓縮演算法即 Roaring Bitmap，是在 2016 年由 S. Chambi、D. Lemire、O. Kaser 等人在論文《Better bitmap performance with Roaring bitmaps》與《Consistently faster and smaller compressed bitmaps with Roaring》中提出來的，

RBM 壓縮演算法的核心思想是：將 32 位無符號整數按照高 16 位進行劃分容器，即最多可能有 65536 個 container，因為 65536 實際上就是 2 的 16 次方，而一個無符號 int 型別正好是需要 32 位進行存盤，劃分為高低位正好兩邊都是 16 位，也就是最多 65536 個，

劃分之后根據高 16 位去找 container（比如高 16 位計算的結果是 1 就去找 container_1，2 就去找 container_2，依次類推），找到之后如果發現容器不存在，那么就會新建一個容器，并且把低 16 位存入容器內，如果容器存在，就直接將低 16 位存入容器，

這樣就會出現一個現象：那就是容器最多有 65536 個，而每個容器內的元素也恰好最多是 65536 個元素，

也就是上面的陣列經過計算就會得到以下容器（container_1 沒有元素）：

如果說大家覺得上面的高低 16 位不好理解，那么可以這么理解，我們把陣列中的元素全部除以 65536，對其取模，每得到一個模就創建一個容器，而其余數就放入對應的模所對應的容器中，因為一個 int 型別就是 2 的 32 次方，正好是 65536 的平方，

經過運算之后得到容器，那么容器中的元素又該如何進行存盤呢？可以選擇直接存盤，也可以選擇其他更高效的存盤方式，在 RBM 演算法中，總共有三種容器型別，分別采用不同的方法來存盤容器中的元素：

• ArrayContainer

ArrayContainer 采用 short 陣列來進行存盤，因為每個容器中的元素最大值就是 65535，采用 2 個位元組進行存盤，這種存盤方式的特點是隨著元素個數的增多，所需空間會一直增大，

• BitmapContainer

BitmapContainer 采用位圖的方式進行存盤，也就是固定創建一個 65536 長度的容器，容器中每個元素只用一個位元進行存盤，某一個位置有元素則存盤 1，沒有元素則存盤為 0，這種存盤方式的特點是空間固定就是占用 65536 個位元，也就是大小固定為 8kb，

• RunContainer

RunContainer 比較特殊，在特定場景下會使用，比如檔案 id 從 1-100 是連續的，那么采用這種容器就可以直接存 1,99，表示 1 后面有 99 個連續的數字，再比如 1,2,3,4,5,6,10,11,12,13 可以被壓縮為 1,5,10,3，表示 1 后面有 5 個連續數字，10 后面有 3 個連續數字，

至于每次存盤采用什么容器，需要進行一下判定，比如 ArrayContainer，當存盤的元素少于 4096 個時，他會比 BitmapContainer 占用更少空間，而當大于 4096 個元素時，采用 ArrayContainer 所需要的空間就會大于 8kb，那么采用 BitmapContainer 就會占用更少空間，

倒排索引如何存盤

前面我們講了 es 中的倒排索引采用的是什么壓縮演算法進行壓縮，那么壓縮之后的資料是如何落地到磁盤的呢？采用的是什么資料結構呢？

字典樹（Tria Tree）

字典樹又稱之為前綴樹（Prefix Tree），是一種哈希樹的變種，可以用于搜索時的自動補全、拼寫檢查、最長前綴匹配等，

字典樹有以下三個特點：

1. 根節點不包含字符，除根節點外的其余每個節點都只包含一個字符，
2. 從根節點到某一節點，將路徑上經過的所有字符連接起來，即為該節點對應的字串，
3. 每個節點的所有子節點包含的字符都不相同，

下圖所示就是在資料結構網站上依次輸入以下單詞（AFGCC、AFG、ABP、TAGCC）后生成的一顆字典樹：

上圖中可以發現根節點沒有字母，除了根節點之外其余節點有白色和綠色兩種顏色之分，這兩種顏色的節點有什么區別呢？

綠色的節點表示當前節點是一個 Final 節點，也就是說當前節點是某一個單詞的結束節點，搜索的時候當發現末尾節點是一個 Final 節點則表示當前字母存在，否則表示不存在，

比如我現在搜索 ABP，從根節點往下找的時候，最后發現 P 是一個 Final 節點，那就表示當前樹中存在字串 ABP，如果搜索 AFGC，雖然也能找到這些字母，但是 C 并不是一個 Final 節點，所以字串 AFGC 并不存在，

不過字典樹存在一個問題，上圖中就可以體現出來，比如第二列中的后綴 FGCC 和 第三列中的 GCC 其實最后三個字符是重復的，但是這些重復的字串都單獨存盤了，并沒有被復用，也就是說字典樹沒有解決后綴共用問題，只解決了前綴共用（這也是字典樹又被稱之為前綴樹的原因），當資料量達到一定級別的時候，只共享前綴不共享后綴也會帶來很多空間的浪費，那么如何來解決這個問題呢？

FST

要解決上面字典樹的缺陷其實思路也很簡單，就是除了利用字串的前綴，同時也將相同的后綴進行利用，這就是 FST，在了解 FST 之前，我們先了解另一個概念，那就是 FSM，即：Finite State Transducer，

FSM

FSM，即 Finite State Machine，翻譯為：有限狀態機，如果大家有了解過設計模式中的狀態模式的話，那么應該會對狀態機有一定了解，有限狀態機顧明思議就是狀態可以全部被列舉出來，然后隨著不同的操作在不同的狀態之間流程，

如下圖所示就是一個簡易的有限狀態機（假設一個人一天做的事就是下面的所有狀態，那么狀態之間可以切換流轉，下圖中的數字表示狀態的轉換條件）：

有限狀態機主要有以下兩個特點：

1. 狀態是有限的，可以被全部列舉出來，
2. 狀態與狀態之間可以流轉，

而我們今天所需要學習的 FST，其實就是通過 FSM 演化而來，

繼續回到我們上面的那顆字典樹，那么假如現在我們換成 FST 來存盤，會得到如下的資料結構：

上面這幅圖是怎么得到的呢？字母后的數字又代表了什么含義呢？有些節點有數字，有些是空白又有什么區別呢？這幅圖又是如何區分 Final 節點呢？接下來我們就一步步來來構建一個 FST，

構建 FST

首先我們知道，既然現在講的是存盤索引，所以除了 key 之外自然得有 value，否則是沒有意義的，所以上圖中其實字母就代表了索引關鍵字，也就是 key，而后面的數字代表了存盤的檔案 id（最侄訓轉換成二進制存盤），然而這個 每個數字代表的 id 又可能是不完整的，這個我們下面會解釋原因，

1. 首先我們收到第一個存盤索引的的鍵值對 AFGCC/5，得到如下圖：

上圖中紅色代表開始節點，深灰色代表結束節點，加粗的線條代表其后面的節點是一個 Final 節點，這里有一個問題，那就是 5 為什么要存盤在第一條線（沒有存盤數字的線上實際上是一個 null 值），實際上我存盤在后面的任意一條線都可以，因為最終搜索的時候會把整條線路上所有的數字加起來得到最終的 value，這也就是上面我為什么說每一條線上的 value 可能是不完整的，因為一個 value 可能會被拆成好幾個數字相加，并且存盤在不同的線上，

首先這個 5 為什么要存盤在第一段其實是為了提高復用率，因為越往前復用的機會可能就會越大，

2. 繼續存盤第二個索引鍵值對 AFG/10，這時候得到下圖：
   
   這時候我們發現，G 后面的節點存盤了一個 5，其他線段上并沒有存盤數字，這是為什么呢？因為 10=5+5，而前面第一段已經存盤了一個 5，后面一個 5 存盤在任何一段線上都會影響到我們的第一個鍵值對 AFGCC/5，所以這時候就只能把他存盤在當前索引 key 所對應的 Final 節點上（原始碼中有一個屬性 output），因為搜索的時候，如果路過不屬于自己的 Final 節點上的 value，是不會相加的，所以當我們搜索第一個索引值 AFGCC 的時候，是不會把 G 后面的 Final 節點中的 value 取出來相加的，

3. 接下來繼續存盤第三個索引鍵值對 ABP/2，這時候得到下圖：

這時候因為 ABP 字串和前面共用了 A，而 A 對應的 value 是 5，已經比 2 大了，所以只要共用 A，那么是無論如何也無法存盤成功的，所以就只能把第一個節點 5 拆成 2+3，原先 A 的位置存盤 2，那么后面的 3 遵循前面的原則，越靠前存盤復用的概率越大，所以存在第二段線也就是字符 F 對應的位置，這時候就都滿足條件了，

4. 最后我們來存盤最后一個索引鍵值對 TAGCC/6，最終得到如下圖：
   

這時候因為 GCC 這個后綴和前面是共用的，而恰好 GCC 之后的線上都沒有存盤 value，所以直接把這個 6 存盤在第一段線即可，注意，如果這里再次發生沖突，那么就需要再次重新分配每一段 value，到這里我們就得到和上圖中網站內生成的一樣的 FST 了，

總結

本文主要講解了在 Elasticsearch 中是如何利用倒排索引來進行資料檢索的，并講述了倒排索引中的 FOR 和 RBM 兩種壓縮演算法的原理以及使用場景，最后對比了字典樹（前綴樹）和 FST 兩種資料結構存盤的區別，并最終得出了為什么 es 中選擇 FST 而不是選擇字典樹來進行存盤索引資料的原因，