LSM思想

LSM (Log Merge Tree)，最早是谷歌的 “” 提出來的，目標是保證寫入性能，同時又能支持較高效率的檢索，在很多 NoSQL 中都有使用，也是使用 LSM 思想來寫入。

普通的B+樹增加記錄可能需要執行 seek+ 操作搜索引擎優化，這需要大量磁盤尋道移動磁頭。而 LSM 采用記錄在文件末尾，順序寫入減少移動磁頭/尋道，執行效率高于 B+樹。具體 LSM 的原理是什么呢？

為了保持磁盤的IO效率，避免對索引文件的直接修改，所有的索引文件一旦生成，就是只讀，不能被改變的。其操作過程如下：

在內存中保存新增的索引, 內存緩存（也就是）;內存中的索引數量達到一定閾值時，觸發寫操作，將這部分數據批量寫入新文件搜索引擎優化，我們稱為；也就是 文件新增的生成后，不能被修改；操作和操作不會立即導致原有的數據被修改或者刪除，會以的方式存儲和標記;最終得到大量的 ，為了減少資源占用，也提高檢索效率，會定期的將這些小的 合并成大的 ，由于map中的數據都是排好序的，所以合并也不會有隨機寫操作；通過merge，還可以把和操作真正生效，刪除多余的數據，節省空間。

合并的過程：

Basic

每個文件固定N個數量，超過N，則新建一個；當數大于M，則合并一個大；當大的數量大于M，則合并一個更大的文件，依次類推。

但是，這會出現一個問題，就是大量的文件被創建，在最壞的情況下，所有的文件都要搜索。

像 和 解決這個問題的方法是：實現了一個分層的，而不是根據文件大小來執行合并操作。

每層維護指定數量的文件，保證不讓 key 重疊，查找一個 key 只會查找一個 key；每次文件只會被合并到上一層的一個文件。當一層的文件數滿足特定個數時，合并到上一層。

所以， LSM 是日志和傳統的單文件索引（B+ tree，Hash Index）的中立，他提供一個機制來管理更小的獨立的索引文件()。

通過管理一組索引文件而不是單一的索引文件，LSM 將B+樹等結構昂貴的隨機IO變的更快，而代價就是讀操作要處理大量的索引文件()而不是一個，另外還是一些IO被合并操作消耗。

的設計思想，與LSM類似但又有些不同，繼承了LSM中數據寫入的優點，但是在查詢上只能提供近實時而非實時查詢。

在被flush或之前，數據保存在內存中，是不可被搜索的，這也就是為什么被稱為提供近實時而非實時查詢的原因。讀了它的代碼后，發現它并不是不能實現數據寫入即可查，只是實現起來比較復雜。原因是中數據搜索依賴構建的索引（例如倒排依賴Term ），中對數據索引的構建會在 flush時，而非實時構建，目的是為了構建最高效索引。當然它可引入另外一套索引機制，在數據實時寫入時即構建，但這套索引實現會與當前內索引不同，需要引入額外的寫入時索引以及另外一套查詢機制，有一定復雜度。

FST

數據字典 Term ，通常要從數據字典找到指定的詞的方法是，將所有詞排序，用二分查找即可。這種方式的時間復雜度是 Log(N)，占用空間大小是 O(N*len(term))。缺點是消耗內存，存在完整的term，當 term 數達到上千萬時，占用內存非常大。

從4開始大量使用的數據結構是FST（ State ）。FST有兩個優點：

空間占用小，通過讀 term 拆分復用及前綴和后綴的重用，壓縮了存儲空間；查詢速度快，查詢僅有 O(len(term)) 時間復雜度

那么 FST 數據結構是什么原理呢？ 先來看看什么是 FSM ( State )， 有限狀態機，從“起始狀態”到“終止狀態”，可接受一個字符后，自循環或轉移到下一個狀態。

而FST呢，就是一種特殊的 FSM，在 中用來實現字典查找功能(NLP中還可以做轉換功能)，FST 可以表示成FST的形式

舉例：對“cat”、 “deep”、 “do”、 “dog” 、“dogs” 這5個單詞構建FST（注：必須已排序），結構如下：

當存在 value 為對應的 docId 時，如 cat/0 deep/1 do/2 dog/3 dogs/4， FST 結構圖如下：

FST 還有一個特點，就是在前綴公用的基礎上，還會做一個后綴公用，目標同樣是為了壓縮存儲空間。

其中紅色的弧線表 NEXT-，可以通過 畫圖工具 來測試。

為了能夠快速查找docid，采用了這一數據結構。有以下幾個特征：

元素排序的，對應到我們的倒排鏈，是按照docid進行排序，從小到大;跳躍有一個固定的間隔，這個是需要建立的時候指定好，例如下圖以間隔是;的層次，這個是指整個有幾層

在什么位置設置跳表指針？

? 設置較多的指針，較短的步長， 更多的跳躍機會

? 更多的指針比較次數和更多的存儲空間

? 設置較少的指針，較少的指針比較次數，但是需要設置較長的步長?較少的連續跳躍

如果倒排表的長度是L，那么在每隔一個步長S處均勻放置跳表指針。

BKD Tree

也叫 Block KD-tree，根據FST思路，如果查詢條件非常多，需要對每個條件根據 FST 查出結果，進行求并集操作。如果是數值類型，那么潛在的 Term 可能非常多，查詢銷量也會很低，為了支持高效的數值類或者多維度查詢，引入 BKD Tree。在一維下就是一棵二叉搜索樹，在二維下是如果要查詢一個區間，logN的復雜度就可以訪問到葉子節點對應的倒排鏈。

確定切分維度，這里維度的選取順序是數據在這個維度方法最大的維度優先。一個直接的理解就是，數據分散越開的維度，我們優先切分。切分點的選這個維度最中間的點。遞歸進行步驟1，2，我們可以設置一個閾值，點的數目少于多少后就不再切分，直到所有的點都切分好停止。

過濾

二進制處理，通過BKD-Tree查找到的docID是無序的，所以要么先轉成有序的docID數組，或者構造，然后再與其他結果合并。

是一種預排序，在ES6.0之后才有，與查詢時的Sort不同，是一種預排序，即數據預先按照某種方式進行排序，它是Index的一個設置，不可更改。

一個中的每個文檔，都會被分配一個docID，docID從0開始，順序分配。在沒有時，docID是按照文檔寫入的順序進行分配的，在設置了之后，docID的順序就與的順序一致。

舉個例子來說，假如文檔中有一列為，我們在中設置按照逆序排序，那么在一個內，docID越小，對應的文檔的越大，即按照從大到小的順序分配docID。

之所以可以優化性能，是因為可以提前中斷以及提高數據壓縮率，但是他并不能滿足所有的場景，比如使用非預排序字段排序，還會損耗寫入時的性能。

搜索引擎正是靠優秀的理論加極致的優化，做到查詢性能上的極致，后續會再結合源碼分析壓縮算法如何做到極致的性能優化的。

節選自：