總結：

1、B+樹將數據完全排序，讀數據時很快，但當要修改數據時，就需要將新入數據下面的數據重新排位，特別是當寫入的數據排在較高的位置時，需要大量的移位操作才能完成寫入。

2、SLM犧牲部分的讀性能，從而提高寫性能：將數據分散到多個有序列表中，每個列表保存一部分數據，這樣讀取數據時，就需要先查找在哪個有序列表，再從這個列表中讀取具體數據，但是寫的時候，受影響的數據就會減少，從而減少寫入時間。

有以下2種方法優化讀取時間：

（1）Bloom filter : 就是個帶隨即概率的bitmap,可以快速的告訴你，某一個小的有序結構里有沒有指定的那個數據的。于是我就可以不用二分查找，而只需簡單的計算幾次就能知道數據是否在某個小集合里啦。效率得到了提升，但付出的是空間代價。
（2）? 小樹合并為大樹： 也就是大家經常看到的compact的過程，因為小樹他性能有問題，所以要有個進程不斷地將小樹合并到大樹上，這樣大部分的老數據查詢也可以直接使用log2N的方式找到，不需要再進行(N/m)*log2n的查詢了。

首先來回答一個問題：為什么在磁盤中要使用b+樹來進行文件存儲呢？

原因還是因為樹的高度低得緣故，磁盤本身是一個順序讀寫快，隨機讀寫慢的系統，那么如果想高效的從磁盤中找到數據，勢必需要滿足一個最重要的條件：減少尋道次數。
我們以平衡樹為例進行對比，就會發現問題所在了：


先上個圖




?
這是個平衡樹，可以看到基本上一個元素下只有兩個子葉節點
?
?
抽象的來看，樹想要達成有效查找，勢必需要維持如下一種結構：
樹的子葉節點中，左子樹一定小于等于當前節點，而當前節點的右子樹則一定大于當前節點。只有這樣，才能夠維持全局有序，才能夠進行查詢。
?
這也就決定了只有取得某一個子葉節點后，才能夠根據這個節點知道他的子樹的具體的值情況。這點非常之重要，因為二叉平衡樹，只有兩個子葉節點，所以如果想找到某個數據，他必須重復更多次“拿到一個節點的兩個子節點，判斷大小，再從其中一個子節點取出他的兩個子節點，判斷大小。”這一過程。
?
這個過程重復的次數，就是樹的高度。那么既然每個子樹只有兩個節點，那么N個數據的樹的高度也就很容易可以算出了。
?
平衡二叉樹這種結構的好處是，沒有空間浪費，不會存在空余的空間，但壞處是需要取出多個節點，且無法預測下一個節點的位置。這種取出的操作，在內存內進行的時候，速度很快，但如果到磁盤，那么就意味著大量隨機尋道。基本磁盤就被查死了。
?
而b樹，因為其構建過程中引入了有序數組，從而有效的降低了樹的高度，一次取出一個連續的數組，這個操作在磁盤上比取出與數組相同數量的離散數據，要便宜的多。因此磁盤上基本都是b樹結構。
?
不過，b樹結構也不是完美的，與二叉樹相比，他會耗費更多的空間。在最惡劣的情況下，要有幾乎是元數據兩倍的格子才能裝得下整個數據集（當樹的所有節點都進行了分裂后）。
?
?
以上，我們就對二叉樹和b樹進行了簡要的分析，當然里面還有非常多的知識我這里沒有提到，我希望我的這個系列能夠成為讓大家入門的材料，如果感興趣可以知道從哪里著手即可。如果您通過我的文章發現對這些原來枯燥的數據結構有了興趣，那么我的目標就達到了: )
?
在這章中，我們還將對b數的問題進行一下剖析，然后給出幾個解決的方向


其實toku DB的網站上有個非常不錯的對b樹問題的說明，我在這里就再次侵權一下，將他們的圖作為說明b樹問題的圖譜吧，因為真的非常清晰。
http://tokutek.com/downloads/mysqluc-2010-fractal-trees.pdf


?
B樹在插入的時候，如果是最后一個node,那么速度非常快，因為是順序寫。


?
但如果有更新插入刪除等綜合寫入，最后因為需要循環利用磁盤塊，所以會出現較多的隨機io.大量時間消耗在磁盤尋道時間上。
?


?
如果是一個運行時間很長的b樹，那么幾乎所有的請求，都是隨機io。因為磁盤塊本身已經不再連續，很難保證可以順序讀取。
?
以上就是b樹在磁盤結構中最大的問題了。
?
那么如何能夠解決這個問題呢？
目前主流的思路有以下幾種
1. ? ? ?放棄部分讀性能，使用更加面向順序寫的樹的結構來提升寫性能。
這個類別里面，從數據結構來說，就我所知并比較流行的是兩類，
一類是COLA（Cache-Oblivious Look ahead Array）（代表應用自然是tokuDB）。
一類是LSM tree(Log-structured merge Tree)或SSTABLE
(代表的數據集是cassandra,hbase,bdb java editon,levelDB etc.).
2. ? ? ?使用ssd，讓尋道成為往事。
?
我們在這個系列里，主要還是講LSM tree吧，因為這個東西幾乎要一桶漿糊了。幾乎所有的nosql都在使用，然后利用這個宣稱自己比mysql的innodb快多少多少倍。。我對此表示比較無語。因為nosql本身似乎應該是以省去解析和事務鎖的方式來提升效能。怎么最后卻改了底層數據結構，然后宣稱這是nosql比mysql快的原因呢？
畢竟Mysql又不是不能掛接LSM tree的引擎。。。
?
好吧，牢騷我不多說，畢竟還是要感謝nosql運動，讓數據庫團隊都重新審視了一下數據庫這個產品的本身。
?
那么下面，我們就來介紹一下LSM Tree的核心思想吧。
?
首先來分析一下為什么b+樹會慢。
?
從原理來說，b+樹在查詢過程中應該是不會慢的，但如果數據插入比較無序的時候，比如先插入5 然后10000然后3然后800 這樣跨度很大的數據的時候，就需要先“找到這個數據應該被插入的位置”，然后插入數據。這個查找到位置的過程，如果非常離散，那么就意味著每次查找的時候，他的子葉節點都不在內存中，這時候就必須使用磁盤尋道時間來進行查找了。更新基本與插入是相同的
?


?
那么，LSM Tree采取了什么樣的方式來優化這個問題呢？
簡單來說，就是放棄磁盤讀性能來換取寫的順序性。
乍一看，似乎會認為讀應該是大部分系統最應該保證的特性，所以用讀換寫似乎不是個好買賣。但別急，聽我分析之。
1. ? ? ?內存的速度遠超磁盤，1000倍以上。而讀取的性能提升，主要還是依靠內存命中率而非磁盤讀的次數
2. ? ? ?寫入不占用磁盤的io，讀取就能獲取更長時間的磁盤io使用權，從而也可以提升讀取效率。
因此，雖然SSTable降低了了讀的性能，但如果數據的讀取命中率有保障的前提下，因為讀取能夠獲得更多的磁盤io機會，因此讀取性能基本沒有降低，甚至還會有提升。
而寫入的性能則會獲得較大幅度的提升，基本上是5~10倍左右。
?
下面來看一下細節
其實從本質來說，k-v存儲要解決的問題就是這么一個：盡可能快得寫入，以及盡可能快的讀取。
讓我從寫入最快的極端開始說起，闡述一下k-v存儲的核心之一—樹這個組件吧。
?
我們假設要寫入一個1000個節點的key是隨機數的數據。
?
對磁盤來說，最快的寫入方式一定是順序的將每一次寫入都直接寫入到磁盤中即可。
但這樣帶來的問題是，我沒辦法查詢，因為每次查詢一個值都需要遍歷整個數據才能找到，這個讀性能就太悲劇了。。
?
那么如果我想獲取磁盤讀性能最高，應該怎么做呢？把數據全部排序就行了，b樹就是這樣的結構。
?
那么，b樹的寫太爛了，我需要提升寫，可以放棄部分磁盤讀性能，怎么辦呢？
?
簡單，那就弄很多個小的有序結構，比如每m個數據，在內存里排序一次，下面100個數據，再排序一次……這樣依次做下去，我就可以獲得N/m個有序的小的有序結構。
?
在查詢的時候，因為不知道這個數據到底是在哪里，所以就從最新的一個小的有序結構里做二分查找，找得到就返回，找不到就繼續找下一個小有序結構，一直到找到為止。
?
很容易可以看出，這樣的模式，讀取的時間復雜度是(N/m)*log2N 。讀取效率是會下降的。
這就是最本來意義上的LSM tree的思路。
那么這樣做，性能還是比較慢的，于是需要再做些事情來提升，怎么做才好呢？
?
于是引入了以下的幾個東西來改進它
1. ? ? ?Bloom filter : 就是個帶隨即概率的bitmap,可以快速的告訴你，某一個小的有序結構里有沒有指定的那個數據的。于是我就可以不用二分查找，而只需簡單的計算幾次就能知道數據是否在某個小集合里啦。效率得到了提升，但付出的是空間代價。
2. ? ? ?小樹合并為大樹： 也就是大家經常看到的compact的過程，因為小樹他性能有問題，所以要有個進程不斷地將小樹合并到大樹上，這樣大部分的老數據查詢也可以直接使用log2N的方式找到，不需要再進行(N/m)*log2n的查詢了。
?
這就是LSMTree的核心思路和優化方式。
不過，LSMTree也有個隱含的條件，就是他實現數據庫的insert語義時性能不會很高，原因是，insert的含義是： 事務中，先查找該插入的數據，如果存在，則拋出異常，如果不存在則寫入。這個“查找”的過程，會拖慢整個寫入。
?
?

這樣，我們就又介紹了一種k-v寫入的模型啦。

轉自：http://qing.weibo.com/1765738567/693f0847330008ii.html

總結

以上是生活随笔為你收集整理的NoSql中的B-tree、B+tree和LSM-tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。