首先來回答一個問題：為什麼在磁盤中要使用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