前言

相信大家之前都瞭解過很多種資料結構，我之前總是兩兩的，也就是從區域性上去進行比較，沒有從整體上進行這些樹的發展脈絡進行梳理，因此經常看完沒多久就忘了。看來確實是需要從本源出發，不僅要知其然還要知其所以然，瞭解清楚前因後果，不僅可以方便我們記憶，更有利於增加我們的理解深度。實際上任何事物的出現都是有他出現的必要性，當某個事物達到瓶頸之後，必然會出現新的事務來彌補它的不足。好的，廢話不多說了，今天我們就從一個小的BST開始，一起見證一下它的升級打怪之路吧。

開場之前，先來兩顆開胃小樹

完全二元樹：

金無足赤，人無完人，但是二元樹是可以有完美的，所有葉子都位於相同的水平的二元樹就是完全二元樹。

平衡二元樹：

樹也是有等級之分的，不是所有的樹都是完美的，相比完美二元樹，稍微低一等級的叫平衡二元樹。每個節點的平衡因子在-1到1之間的，雖然不是完全平衡的，但是也還能接受。

二元搜尋樹(BST)：

二元搜尋樹（balance search tree），這是一棵有組織有紀律的樹，滿足左子樹中所有節點的值小於根的值，右子樹中所有節點的值大於或等於根的值。簡單說就是有序的，所以在查詢的時候就可以使用二分法，因此具有很高的查詢效率，最佳的時間複雜度是o(log n)，最差是O(n)。當一顆二元搜尋樹是一組升序或者降序的數值時，二元搜尋樹就會退化為單連結串列，查詢時間複雜度變成了O(n)。

AVL樹

為什麼會有AVL樹

前邊提到了，當向BST中插入一組有序的數值時，就會退化為單連結串列，效能會退化到o(n)，究其根源是因為小時候父母管的比較鬆，任由她自由發展，導致BST偏科了，能力沒有得到均衡發展，所以怎麼辦呢？嗯，沒錯，是得請個家教，而且一個不夠，得兩個，制定個規則去約束她，即使不能像完美二元樹那樣科科滿分，至少也得平衡一些是吧，要不都嫁不出去啦。請了家教之後，BST直接鳥槍換炮，搖身一變成為了我們接下來要介紹的AVL樹。

什麼是AVL樹

AVL樹指的是平衡二元搜尋樹，沒錯它就是二元搜尋樹和平衡二元樹雜交育種的結果，結合了雙親的優良特性，有序且平衡，直接走向樹生巔峰。

為什麼叫AVL樹？這可不是取的平衡二元搜尋樹首字母的縮寫，而是因為是BST的兩個家教的name是G. M. Adelson-Velsky和Evgenii Landis。

AVL樹的查詢，插入和刪除的時間複雜度都固定是o(log n)，但是增加和刪除操作會使樹失去平衡，因此需要通過一次或多次樹旋轉來重新平衡這棵樹。

旋轉分為LL，LR，RR，RL4種方式，具體的插入和刪除的情況比較多，在這就不詳細展開了，說一下關鍵的一點，是可能需要多次旋轉來維持平衡，因此維護樹保持平衡的成本還是蠻高的嘞，這也正是AVL樹的弊端。

紅黑樹

為什麼會出現紅黑樹

AVL樹的左右子樹高度差不能超過1，每次進行插入/刪除操作時，幾乎都需要通過旋轉操作保持平衡，在頻繁進行插入/刪除的場景中，頻繁的旋轉操作使得AVL的效能大打折扣，所以就有了紅黑樹的出現。

什麼是紅黑樹

紅黑樹是一種自平衡的二元搜尋樹，和AVL樹十分類似，紅黑樹的查詢，插入和刪除的時間複雜度都是o(log n)。但是紅黑樹不是一顆嚴格的平衡二元樹，它不像AVL樹那樣嚴格維持平衡因子為1來保持平衡，而是通過左旋，右旋和變色3種操作，維持自身的5大特性，保證了最長路徑不超過最短路徑的兩倍，從而實現近似的平衡。

紅黑樹和AVL樹的對比：

查詢，插入和刪除的時間複雜度都是o(log n)，相比於AVL樹，紅黑樹犧牲了部分的平衡性，來換取了在插入和刪除時更少的旋轉的操作，因為整體效能上要優於AVL樹，所以在查詢場景多，插入和刪除稍作少的場景，AVL樹的效能更好，當插入和刪除場景很多的時候，紅黑樹的效能更佳。

B樹

為什麼會出現B樹

傳統用來搜尋的平衡二元樹有很多，如 AVL 樹，紅黑樹等。這些樹在一般情況下查詢效能非常好，但當資料非常大的時候它們就無能為力了。原因當資料量非常大時，記憶體不夠用，大部分資料只能存放在磁碟上，只有需要的資料才載入到記憶體中。一般而言記憶體存取的時間約為 50 ns，而磁碟在 10 ms 左右。速度相差了近 5 個數量級，磁碟讀取時間遠遠超過了資料在記憶體中比較的時間。這說明程式大部分時間會阻塞在磁碟 IO 上。那麼我們如何提高程式效能？減少磁碟 IO 次數，像 AVL 樹，紅黑樹這類平衡二元樹從設計上無法「迎合」磁碟。

平衡二元樹是通過旋轉來保持平衡的，而旋轉是對整棵樹的操作，若部分載入到記憶體中則無法完成旋轉操作。其次平衡二元樹的高度相對較大為 log n（底數為2），這樣邏輯上很近的節點實際可能非常遠，無法很好的利用磁碟預讀（區域性性原理），所以這類平衡二元樹在資料庫和檔案系統上的選擇就被 pass 了。

什麼是B樹

B樹是一種多路平衡查詢樹，相對於二元樹而言，B樹可以認為是一顆多叉樹，m階B樹表示一個節點最多有m個子節點。

下面我們來看看B樹的定義。

每個節點最多有m-1個關鍵字（可以存有的鍵值對）。
根節點最少可以只有1個關鍵字。
非根節點至少有m/2個關鍵字。
每個節點中的關鍵字都按照從小到大的順序排列，每個關鍵字的左子樹中的所有關鍵字都小於它，而右子樹中的所有關鍵字都大於它。
所有葉子節點都位於同一層，或者說根節點到每個葉子節點的長度都相同。
每個節點都存有索引和資料，也就是對應的key和value。

所以，根節點的關鍵字數量範圍：1 <= k <= m-1，非根節點的關鍵字數量範圍：m/2 <= k <= m-1。

B樹和AVL樹、紅黑樹一樣，也是一顆自平衡的查詢樹，當新插入的節點不滿足要求時，也會進行維權運動，只不過B樹不會去旋轉了，而是分裂，核心臨界條件是每個節點關鍵字的數量，如果數量超出要求，那她就會進行分裂。

簡單說一下分裂的過程，假如一顆4階B樹，當新插入元素後，某個節點的關鍵字數量達到4個，因為每個節點最多有m-1個關鍵字，也就是最多隻能有3個節點，這時候就需要進行分裂。假設key的值為5，6，7，8，那會以m/2為界分為3個部分，5---6---7，8，分裂會將6放入父節點，5和7，8兩個節點分別指向父節點。

這也就是說B樹的分裂只會影響父節點和當前節點。

B+樹

什麼是B+樹

特性：

B+樹包含2種型別的節點：內部節點（也稱索引節點）和葉子節點。根節點本身即可以是內部節點，也可以是葉子節點。根節點的關鍵字key個數最少可以只有1個；
B+樹與B樹最大的不同是內部節點不儲存資料，只用於索引，所有資料（或者說記錄）都儲存在葉子節點中；
m階B+樹表示了內部節點最多有m-1個關鍵字（或者說內部節點最多有m個子樹，和B樹相同），階數m同時限制了葉子節點最多儲存m-1個記錄；
內部節點中的key都按照從小到大的順序排列，對於內部節點中的一個key，左樹中的所有key都小於它，右子樹中的key都大於等於它。葉子節點中的記錄也按照key的大小排列；
每個葉子節點都存有相鄰葉子節點的指標，葉子節點本身依關鍵字的大小自小而大順序連結；

B+樹和B樹的對比：

B+樹和B樹的核心區別是，B樹的每個節點都儲存索引和資料，而B+樹只有葉子節點儲存了索引和資料，非葉子節點只儲存索引，B+樹相對於B樹的優點，有如下3點：

磁碟IO次數少

因為B+樹只有葉子節點儲存了資料，其他非葉子節點只儲存和索引，所以B+樹單次磁碟IO的數量是要大於B樹的，這就意味著B+樹可以減少磁碟IO的次數，而我們都知道存取磁碟的速度比直接存取記憶體，要慢了不知道多少倍，所以磁碟IO的次數往往會成為效能的瓶頸點，因此磁碟IO次數少，可以大幅的提升插入和查詢效率。

適合範圍查詢

B+樹葉子節點形成有序連結串列，範圍查詢轉化為順序讀，效率高。相對而言B樹必須通過中序遍歷才能支援範圍查詢。

查詢效能穩定

因為B+樹的資料全都儲存在葉子節點上，因此每次必須要遍歷到葉子節點，因此查詢時間複雜度固定為O(log n)，而B樹的資料直接儲存在每個節點上，因此B樹的查詢時間複雜度在O(1)和O(log n)之間。

B+樹的缺點

B+樹的主要缺點有兩個：

如果寫入的資料比較離散，那麼尋找寫入位置時，子節點有很大可能性不會在記憶體中，最終會產生大量的隨機寫，效能下降。
如果B+樹已經執行了很長時間，寫入了很多資料，隨著葉子節點分裂，其對應的塊會不再順序儲存，而變得分散。這時執行範圍查詢也會變成隨機讀，效率降低了。

LSM樹

為什麼會出現LSM樹

B+樹作為mysql的索引結構，長期以來主流使用B+樹這種索引結構來實現快速資料查詢，具有很好的讀效能。當資料量不太大時，B+樹讀寫效能表現也非常好。但是在海量資料情況下，經常性的會有大量的資料的寫入和更新，B+樹越來越高，由於B+樹更新和刪除資料時需要沿著B+樹逐層進行頁分裂和頁合併，當有大量分裂時，會導致大量的磁碟隨機尋道，嚴重影響資料寫入效能。LSM-tree就是為了解決上述問題而生的一種儲存結構。

什麼是LSM樹

LSM Tree出現於谷歌的三駕馬車之一的《Bigtable: A Distributed Storage System for Structured Data》，全稱為Log-Structured Merge Tree，是一個分層、有序、針對塊儲存裝置（機械硬碟和SSD）特點而設計的資料儲存結構。

很多流行的資料庫都有它的身影，比如Cassandra、RocksDB、HBase、LevelDB等NoSQL資料庫，TiDB等newSQL資料庫，甚至像SQLite這種傳統的關係型資料庫和MongoDB這種傳統的檔案型資料庫，以及clickhouse都提供了基於LSM Tree的儲存引擎作為可選的儲存引擎。

它的核心理論基礎還是磁碟的順序寫速度比隨機寫速度快非常多，即使是SSD，由於塊擦除和垃圾回收的影響，順序寫速度還是比隨機寫速度快很多。

基本組成

WAL（write ahead log）

WAL的結構和作用跟其他資料庫一樣，是一個只能在尾部以Append Only方式追加記錄的紀錄檔結構檔案，它用來當系統崩潰重啟時重放操作，使MemTable和Immutable MemTable中未持久化到磁碟中的資料不會丟失。

MemTable

MemTable是記憶體中的資料結構，用於寫入和讀取最近更新的資料，MemTable具體的資料結構，LSM並沒有強約束，可以是紅黑樹，也可以是跳錶結構。需要支援高效的動態插入資料，對資料進行排序，也支援高效的對資料進行精確查詢和範圍查詢。

Immutable MemTable

當MemTable達到閾值的大小後，會轉化為Immutable MemTable。Immutable MemTable不能寫資料，只能讀資料，定期會將Immutable MemTable的資料flush到磁碟中。

SSTable(Sorted String Table)

SSTable是一種擁有持久化，有序且不可變的的鍵值儲存結構，它的key和value都是任意的位元組陣列，並且了提供了按指定key查詢和指定範圍的key區間迭代遍歷的功能。SSTable內部包含了一系列可設定大小的Block塊，典型的大小是64KB，關於這些Block塊的index儲存在SSTable的尾部，用於幫助快速查詢特定的Block。當一個SSTable被開啟的時候，index會被載入到記憶體，然後根據key在記憶體index裡面進行一個二分查詢，查到該key對應的磁碟的offset之後，然後去磁碟把響應的塊資料讀取出來。當然如果記憶體足夠大的話，可以直接把SSTable直接通過MMap的技術對映到記憶體中，從而提供更快的查詢。

寫流程

LSM-tree寫入資料時，會先寫一條記錄到WAL中，然後會將資料寫入記憶體中的MemTable中，當然記憶體的大小肯定是有限制的，不可能一直往裡寫，當MemTable的大小達到設定的閾值後，MemTable會轉換為Immutable MemTable，顧名思義就是不可變的MemTable，然後會生成一個新的MemTable，用來寫入新的資料。所以說MemTable只會有一個，但是Immutable MemTable可能會有多個。會有單獨的執行緒定期的將Immutable MemTable的資料flush到磁碟中的SSTable中。

刪數資料的時候與寫入新資料一樣，都是寫入一條新的記錄，只是刪除資料時會新增一個刪除標記，只有再compact時才會對帶有刪除標記的資料進行物理刪除。

讀流程

先在記憶體MemTable中查詢，然後在記憶體中的Immutable MemTable中查詢，然後在level 0 SSTable中查詢，最後在level N SSTable中查詢。

查詢某個具體的SSTable時，一般先把SSTable的後設資料block讀到記憶體中，根據BloomFilter可以快速確定資料在當前SSTable中是否存在，如果存在，則採用二分法確定資料在哪個資料block，然後將相應資料block讀到記憶體中進行精確查詢。

從LSM Tree資料查詢過程我們可以看到，為了查詢到目標資料，我們需要讀取並查詢不包含目標資料的SSTable，如果目標資料在最底層level N的SSTable中，我們需要讀取和查詢所有的SSTable！LSM Tree把這種讀取和查詢了無關SSTable的現象叫做讀放大(read amplification)。

讀放大現象嚴重影響了LSM Tree資料查詢效能，論文《BigTable》提到了幾種提升資料查詢效能的方法，如壓縮，快取，索引(布隆過濾器)以及compact等操作，這裡就不詳細展開了。

LSM樹和B+樹的對比

LSM樹和B+樹的差異主要在於讀效能和寫效能進行權衡

當寫多讀少的場景，LSM樹相比於B樹有更好的效能。因為大量的插入操作，為了維護B+樹結構，節點分裂。讀磁碟的隨機讀寫概率會變大，效能會逐漸減弱。

當讀多寫少的場景，B+樹相比於LSM樹有更好的效能。LSM樹通過犧牲部分讀效能為代價，來大幅提升寫效能，並且通過一些優化手段，如布隆過濾器和compact策略，對讀效能有了很大的優化，時間複雜度也是O(log n)級別的。

參考檔案：

https://www.cnblogs.com/wxiaotong/p/14781753.html

https://www.jianshu.com/p/f911cb9e42de

作者：京東物流於建飛

來源：京東雲開發者社群自圓其說Tech 轉載請註明來源

從BST到LSM的進階之路

前言