HBASE-LSM樹

HBASE-LSM樹

關于B樹、B+樹、B樹的了解參考：*

<a href="https://link.jianshu.com?t=http%3A%2F%2Fblog.csdn.net%2Fv_july_v%2Farticle%2Fdetails%2F6530142" target="_blank">http://blog.csdn.net/v_july_v/article/details/6530142</a>

優點：

走進搜尋引擎的作者梁斌老師針對B樹、B+樹給出了他的意見（為了真實性，特引用其原話，未作任何改動）： “B+樹還有一個最大的好處，友善掃庫，B樹必須用中序周遊的方法按序掃庫，而B+樹直接從葉子結點挨個掃一遍就完了，B+樹支援range-query非常友善，而B樹不支援。這是資料庫選用B+樹的最主要原因。“

為什麼說B+tree比B樹更适合實際應用中作業系統的檔案索引和資料庫索引？

（1) B+tree的磁盤讀寫代價更低 B+tree的内部結點并沒有指向關鍵字具體資訊的指針。是以其内部結點相對B樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。 舉個例子，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體資訊指針2bytes。一棵9階B-tree(一個結點最多8個關鍵字)的内部結點需要2個盤快。而B+ 樹内部結點隻需要1個盤快。當需要把内部結點讀入記憶體中的時候，B 樹就比B+ 樹多一次盤塊查找時間(在磁盤中就是盤片旋轉的時間)。 （2）B+tree的查詢效率更加穩定 由于非葉子結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。 （3）B樹在提高了磁盤IO性能的同時并沒有解決元素周遊的效率低下的問題。正是為了解決這個問題，B+樹應運而生。B+樹隻要周遊葉子節點就可以實作整棵樹的周遊。而且在資料庫中基于範圍的查詢是非常頻繁的，而B樹不支援這樣的操作（或者說效率太低）。

缺點：

B+樹最大的性能問題是會産生大量的随機IO，随着新資料的插入，葉子節點會慢慢分裂，邏輯上連續的葉子節點在實體上往往不連續，甚至分離的很遠，但做範圍查詢時，會産生大量讀随機IO。對于大量的随機寫也一樣，舉一個插入key跨度很大的例子，如7-&gt;1000-&gt;3-&gt;2000 ... 新插入的資料存儲在磁盤上相隔很遠，會産生大量的随機寫IO. 從上面可以看出，低下的磁盤尋道速度嚴重影響性能（近些年來，磁盤尋道速度的發展幾乎處于停滞的狀态）

存儲引擎和B樹存儲引擎一樣，同樣支援增、删、讀、改、順序掃描操作。而且通過批量存儲技術規避磁盤随機寫入問題

原理：

把一棵大樹拆分成N棵小樹，它首先寫入記憶體中，随着小樹越來越大，記憶體中的小樹會flush到磁盤中，磁盤中的樹定期可以做merge操作，合并成一棵大樹，以優化讀性能。

讀寫性能：

LSM樹與B樹相比，犧牲了部分的讀性能，大幅提高寫性能。 LSM Tree，對于最簡單的二層LSM Tree而言，記憶體中的資料和磁盤你中的資料merge操作，如下圖： 281219493293115.png

資料會先寫到記憶體中，為了防止記憶體資料丢失，寫記憶體的同時需要持久化到磁盤，對應了HBase的MemStore和HLog； MemStore中的資料達到一定的門檻值之後，需要将資料刷寫到磁盤，即生成HFile（也是一顆小的B+樹）檔案； hbase中的minor（少量HFile小檔案合并）major（一個region的所有HFile檔案合并）執行compact操作，同時删除無效資料（過期及删除的資料），多棵小樹在這個時機合并成大樹，來增強讀性能。

針對LSM樹讀性能hbase的優化：

Bloom-filter:就是個帶随機機率的bitmap,可以快速的告訴你，某一個小的有序結構裡有沒有指定資料的。于是就可以不用二分查找，而隻需簡單的計算幾次就能知道資料是否在某個小集合裡啦。效率得到了提升，但付出的是空間代價。 compact:小樹合并為大樹:因為小樹性能有問題，是以要有個程序不斷地将小樹合并到大樹上，這樣大部分的老資料查詢也可以直接使用log2N的方式找到，不需要再進行(N/m)*log2n的查詢了。

20135106-a1e5fd079a51484085065d3b29f2d331.png