看圖輕鬆理解資料結構與算法系列(NoSQL儲存-LSM樹)
推出一個新系列，《看圖輕鬆理解資料結構和演算法》，主要使用圖片來描述常見的資料結構和演算法，輕鬆閱讀並理解掌握。本系列包括各種堆、各種佇列、各種列表、各種樹、各種圖、各種排序等等幾十篇的樣子。
關於LSM樹
LSM樹，即日誌結構合併樹(Log-Structured Merge-Tree)。其實它並不屬於一個具體的資料結構，它更多是一種資料結構的設計思想。大多NoSQL資料庫核心思想都是基於LSM來做的，只是具體的實現不同。所以本來不打算列入該系列，但是有朋友留言了好幾次讓我講LSM樹，那麼就說一下LSM樹。
LSM樹誕生背景
傳統關係型資料庫使用btree或一些變體作為儲存結構，能高效進行查詢。但儲存在磁碟中時它也有一個明顯的缺陷，那就是邏輯上相離很近但物理卻可能相隔很遠，這就可能造成大量的磁碟隨機讀寫。隨機讀寫比順序讀寫慢很多，為了提升IO效能，我們需要一種能將隨機操作變為順序操作的機制，於是便有了LSM樹。LSM樹能讓我們進行順序寫磁碟，從而大幅提升寫操作，作為代價的是犧牲了一些讀效能。
關於磁碟IO
磁碟讀寫時涉及到磁碟上資料查詢，地址一般由柱面號、盤面號和塊號三者構成。也就是說移動臂先根據柱面號移動到指定柱面，然後根據盤面號確定盤面的磁軌，最後根據塊號將指定的磁軌段移動到磁頭下，便可開始讀寫。
整個過程主要有三部分時間消耗，查詢時間(seek time) +等待時間(latency time)+傳輸時間(transmission time) 。分別表示定位柱面的耗時、將塊號指定磁軌段移到磁頭的耗時、將資料傳到記憶體的耗時。整個磁碟IO最耗時的地方在查詢時間，所以減少查詢時間能大幅提升效能。
LSM樹原理
LSM樹由兩個或以上的儲存結構組成，比如在論文中為了方便說明使用了最簡單的兩個儲存結構。一個儲存結構常駐記憶體中，稱為C0 tree，具體可以是任何方便健值查詢的資料結構，比如紅黑樹、map之類，甚至可以是跳錶。另外一個儲存結構常駐在硬碟中，稱為C1 tree，具體結構類似B樹。C1所有節點都是100%滿的，節點的大小為磁碟塊大小。
插入步驟
大體思路是：插入一條新紀錄時，首先在日誌檔案中插入操作日誌，以便後面恢復使用，日誌是以append形式插入，所以速度非常快；將新紀錄的索引插入到C0中，這裡在記憶體中完成，不涉及磁碟IO操作；當C0大小達到某一閾值時或者每隔一段時間，將C0中記錄滾動合併到磁碟C1中；對於多個儲存結構的情況，當C1體量越來越大就向C2合併，以此類推，一直往上合併Ck。
合併步驟
合併過程中會使用兩個塊：emptying block和filling block。
- 從C1中讀取未合併葉子節點，放置記憶體中的emptying block中。
- 從小到大找C0中的節點，與emptying block進行合併排序，合併結果儲存到filling block中，並將C0對應的節點刪除。
- 不斷執行第2步操作，合併排序結果不斷填入filling block中，當其滿了則將其追加到磁碟的新位置上，注意是追加而不是改變原來的節點。合併期間如故宮emptying block使用完了則再從C1中讀取未合併的葉子節點。
- C0和C1所有葉子節點都按以上合併完成後即完成一次合併。
關於優化措施
本文用圖闡述LSM的基本原理，但實際專案中其實有很多優化策略，而且有很多針對LSM樹優化的paper。比如使用布隆過濾器快速判斷key是否存在，還有做一些額外的索引以幫助更快找到記錄等等。
插入操作
向LSM樹中插入 A E L R U ，首先會插入到記憶體中的C0樹上，這裡使用AVL樹，插入“A”，先項磁碟日誌檔案追加記錄，然後再插入C0，
插入“E”，同樣先追加日誌再寫記憶體，
繼續插入“L”，旋轉後如下，
插入“R”“U”，旋轉後最終如下。
假設此時觸發合併，則因為C1還沒有樹，所以emptying block為空，直接從C0樹中依次找最小的節點。filling block長度為4，這裡假設磁碟塊大小為4。
開始找最小的節點，並放到filling block中，
繼續找第二個節點，
以此類推，填滿filling block，
開始寫入磁碟，C1樹，
繼續插入 B F N T ，先分別寫日誌，然後插入到記憶體的C0樹中，
假如此時進行合併，先載入C1的最左邊葉子節點到emptying block，
接著對C0樹的節點和emptying block進行合併排序，首先是“A”進入filling block，
然後是“B”，
合併排序最終結果為，
將filling block追加到磁碟的新位置，將原來的節點刪除掉，
繼續合併排序，再次填滿filling block，
將filling block追加到磁碟的新位置，上一層的節點也要以磁碟塊（或多個磁碟塊）大小寫入，儘量避開隨機寫。另外由於合併過程可能會導致上層節點的更新，可以暫時儲存在記憶體，後面在適當時機寫入。
查詢操作
查詢總體思想是先找記憶體的C0樹，找不到則找磁碟的C1樹，然後是C2樹，以此類推。
假如要找“B”，先找C0樹，沒找到。
接著找C1樹，從根節點開始，
找到“B”。
刪除操作
刪除操作為了能快速執行，主要是通過標記來實現，在記憶體中將要刪除的記錄標記一下，後面非同步執行合併時將相應記錄刪除。
比如要刪除“U”，假設標為#的表示刪除，則C0樹的“U”節點變為，
而如果C0樹不存在的記錄，則在C0樹中生成一個節點，並標為#，查詢時就能再記憶體中得知該記錄已被刪除，無需去磁碟找了。比如要刪除“B”，那麼沒有必要去磁碟執行刪除操作，直接在C0樹中插入一個“B”節點，並標為#。
-------------推薦閱讀------------
ofollow,noindex">我的開源專案彙總(機器&深度學習、NLP、網路IO、AIML、mysql協議、chatbot)
我的2017文章彙總——Java及中介軟體
我的2017文章彙總——JDK原始碼篇
跟我交流，向我提問：
Line"/>
歡迎關注：
