数据映射--B树
http://blog.sina.com.cn/s/blog_693f08470101n7hm.html
難得一篇文章能從較高的角度介紹B樹而不是陷入了實現細節
我們在之前介紹了很多有序的樹，什么平衡有序二叉樹,skiplist，有序數組。不過，這些樹都有個共有的特性，就是不適合于ssd與磁盤。
?
那么本周開始，我會開始介紹一些面向磁盤和ssd的存儲結構。
?
本周呢我們就來介紹面向磁盤結構一種最長見的數據結構 --?B樹。他應該是大家在日常接觸最多的數據結構之一了~?因為只要你在使用數據庫，你就是在用B樹。甚至當你在用hbase的時候，他其實也只是個分布式的大B樹而已。
?
我們一直都在強調，硬件是骨頭，軟件是肉。軟件的目標就是盡可能的發揮硬件的技術特性，并盡可能的繞開硬件的限制。
?
那么，作為骨頭的磁盤，具有什么樣的硬件特性呢？?
在之前的文章中，我們已經給大家介紹過了磁盤的一些具體的技術特性，下面我們用一句話概括一下，如果要發揮磁盤的全部特性，軟件需要滿足的技術特點：一次讀取或寫入固定大小的一塊數據，并盡可能減少隨機查找這個操作的次數（因為隨機查找意味著隨機尋道）。嗯?我是特意沒有寫順序讀寫這個操作的，因為我認為，只要能做到上面兩個條件，那么順序讀寫就能夠自然而然的做到。
?
而對于ssd來說，如果要發揮ssd的全部特性，那么軟件需要滿足的技術特點是：一次讀取或寫入固定大小的一塊數據，并盡可能的減少刪除這個操作的次數（因為ssd的擦除操作需要的代價比較大）
?
通過上面的兩個介紹，你一定會發現，無論ssd還是磁盤，他們都有一個共性的要求是，一次讀寫固定大小的一塊數據。
不知道這時候大家會不會立刻聯想到一個數據結構？對，就是數組。?數組的特性就是擁有固定的大小。
?
但是，回憶一下之前我們說過的：?有序數組有一個最大的難點就在于如何能夠讓數組以更便宜的方式來實現數組的自動擴展。
?
好，鋪墊了這么多，我們終于要開始進入正題了～
?
因為數組的大小是固定的，那么如果想擴展怎么辦呢？
一種能夠想到的方式是，每次滿了就創建一個新數組，然后數據全復制到新數組中?。但這樣做有個很大的問題，是每一次都需要做一次數據的全拷貝，代價相對比較大。
?
另外一種方式是，保持數組大小不變，但增加數組的個數，不是也可以增加整個數據結構承載數據的總量么？
?
這個思路就是b樹的核心思路，另外這里有個小八卦要給大家說一下，大家經?？吹降?/span>b樹，b－樹，其實是同一類結構，b－樹不是“b減樹”的意思哦～
那么b樹的核心是幾個關鍵詞
1.??????樹高:一般來說，樹的高度要比二叉平衡樹低很多
2.??????數組:每一個node，都是一個“數組”，數組是很關鍵的決定性因素，我們后面寫入和讀取分析的時候會講到。
?
然后我們進行一下讀取和寫入的模擬。
從讀取來說：如果我要查找28這個數據對應的value是多少，路徑大概是：首先走root節點，取出root node后，對該數組進行二分查找，發現35>28>17,所以進入branch節點中的第二個節點，取出該節點后再進行二分查找。發現30>28>26，所以進入branch節點的p2 value，取出該節點，對該三個值的數組進行二分查找，從而定位到28這個數據的對應value。
?
而寫入刪除則涉及到分裂和合并這兩個btree最重要的操作，比如，要寫入37，那么會先找到36所應該被插入的數組[36,60]這個數組，然后判斷其是否有空，如果有空，則對該數組進行重新排序。而如果沒有空，則必須要進行分裂。分裂的緣由是因為組成b-tree的每一個node,都是一個數組，數組最大的特性是，數組內元素個數是固定的。因此必須要把原有已經滿掉的數組里面的一半的數據拿出來，放到新的一個新建立的空數組中，然后把要寫入的數據寫入到老或新的這兩個數組里面的一個里面去。
?
【這里要留個問題給大家了，我想問一下，為什么b-tree要使用數組來存儲數據呢？為什么不選擇鏈表等結構呢？】
?
對于上面的這個小的b-tree sample里面呢，因為數組[35,60]，數組已經滿了，所以要進行分裂。于是數組在插入了新值以后，變成了兩個[35,36]?和[60]?，然后再改變父節點的指針并依次傳導上去即可。
?
當出現刪除的時候，會可能需要進行合并的工作，也就是寫入這個操作的反向過程。在一些場景中，因為不斷地插入新的id,刪除老的id，會造成b-tree的右傾，這時候需要有后臺進程對這種傾向進行不斷地調整。
?
基本上，這就是b-tree的運轉過程了。
?
B+tree
B+tree?其實就是在原有b-tree的基礎上。增加兩條新的規則
1.??????Branch節點不能直接查到數據后返回，所有數據必須讀穿或寫穿到leaf節點后才能返回成功
2.??????子葉節點的最后一個元素是到下一個leaf節點的指針。
這樣做的原因是，更方便做范圍查詢，在b+樹種，如果要查詢20~56.只需要找到20這個起始節點，然后順序遍歷，不再需要不斷重復的訪問branch和root節點了。
?
?
在了解了b樹的基本原理了以后，讓我們來做一個小結。
在面向磁盤/ssd的數據結構中，因為從這類介質中進行查找和寫入的代價遠遠的大于內存，并且一次必須讀取一個或幾個相鄰塊內的數據效率才會高，而隨機尋道次數則直接決定了磁盤的瓶頸。因此，面向磁盤類的結構一個最重要的理念，就是盡可能的減少磁盤尋道次數。而實現這個理念所依托的核心思路，就是讓每一個取出的塊都能擁有更大的價值。舉個例子，如果磁盤進行了一次隨機尋道，拿到了一批數據，而這個批內可以進行4次二分查找。那么如果要從2^8個數據內定位到我們所需要的數據，則只需要進行兩次隨機尋道，取出兩批數據，就可以定位到數據了。
這是針對這類整塊取出或寫入數據的硬件的一種通用的解決方法，后面我們介紹的其他面向磁盤的數據結構，也都擁有類似的結構，而不同點則主要是針對一些具體的硬件技術特性而做出的針對性的優化。這個到我們介紹LSM/SSTable的時候大家就會看到。
B樹是上世紀80年代的產物，設計上是比較簡單的，因為b樹采取的是原位更新的方式，所以對讀取是比較優化的，而代價是在寫入的時候也需要先通過隨機查找來找到數據要寫入的目標位置，這個操作會導致磁盤的隨機寫。因此對寫入而言，如果你使用的是磁盤，那么很可能在不斷地寫入刪除寫入刪除多次后，b樹會出現更多的隨機尋道，從而導致寫的性能下降。（B樹很適合讀，一般最多需要兩次磁盤隨機尋道就可以讀取數據，但是在長時間運行，經過多次插入，刪除之后，就像內存一樣，在磁盤上也出現了很多碎片，如果是寫入到原數組，就直接寫，但是，如果原數組已經寫滿了，就要對原數組進行分裂，這時就要在磁盤上找到一塊空閑塊，這就會出現較多的隨機尋道）
B樹另外的一個挑戰則是如何保持b樹元素的均衡，如果各位實際的觀察過數據庫，都會發現隨著用戶的使用，數據庫可能都會出現一定程度的向右的傾斜，這種現象產生的主要原因與我們使用b樹的方式有一定關系，因為我們往往會給數據增加一個唯一標識，寫入的時候則主要會以單調遞增的方式創建這個id。那么最后我們寫入數據庫的一個數據的序列就可能是：插入1,2,3，刪除3，插入4,5,7?，刪除4,5?插入8,9,10。。。一直這樣寫入下去，就會出現前面的節點數據相對的比較松散，而后面的數據則相對的比較致密，雖然前面的數據比較松散，但松散卻并不意味著空間節省，因為b樹必須保證全局有序，因此空間只能被空在那里，造成了較多的空間浪費。這個問題主要的解決方法就是做一個后臺線程，不斷的將前面的數據做一個數據整理，并寫到新的塊內。以騰出更多的空間。
?下面照例，我們使用一些通用的標準對b樹進行一下簡單的評價：
1.是否支持范圍查找
?
因為是有序結構，所以能夠很好的支持范圍查找。
?
2.集合是否能夠隨著數據的增長而自動擴展
?
可以，主要增長方式如下： 如果單個數組內還有空隙，那么數據可以直接放入數組內，而如果數組沒有空隙，則進行分裂，從而可以支持數據的自動擴展。
?
3.讀寫性能如何
?
因為從宏觀上可以做到一次排除一半的數據，并且在寫入時也沒有進行其他額外的數據查找性工作，所以對于b樹來說，其讀寫的時間復雜度都是O(log2n)。
?
4.是否面向磁盤結構
一般來說，在有內存的情況下，root層和branch里面的一部分都會被緩存在內存中，所以如果樹的高度是三層，那么前兩層一般都會被緩存在內存中，所以查詢基本上只需要一次隨機尋道時間， 這比二叉樹系列和skiplist系列都要強不少。
?
5.并行指標
b樹也是一個并行度比較不錯的數據結構，相比較skiplist而言，他很難使用compare and set的方式來進行數據的寫入，而必須使用lock來保證讀寫訪問的同步。不過因為可以盡可能的將鎖下推，所以鎖的顆粒度可以維持在比較小的級別，從而可以提供比較高的并行度。同時，因為b樹主要使用的目標場景是磁盤，對于磁盤讀寫來說，Compare and set 帶來的性能提升幾乎可以忽略。因此我們可以認為，b樹的并行度比skiplist要差，但比其他樹的要好
?
6.內存占用
這是b樹的一個短板，在最壞的情況下，b樹的所有塊都剛好做完分裂。那么整棵樹需要消耗兩倍的空間才能存儲下所有的數據，空間相對的有些浪費。所以一般會通過重新平衡的方式加以部分的糾正
總結
- 上一篇： lsm-tree
- 下一篇： 数据映射--平衡二叉有序树