這次準備出一個關于B樹的合集。在第一部分，先來介紹下B樹的基本概念。

B樹與bst等二叉樹不同，B樹是多叉樹，而且B樹是自平衡樹。B樹的Search、Insert、Remove算法時間復雜度都是O(log N)。

B樹常常用于數據庫。數據庫常常數據量巨大，因此不可能光放到內存中，需要放到硬盤中進行存儲。而硬盤是塊設備，就是一次讀取一塊區(qū)域，而B樹是多叉樹，因此有多個key，所以一塊區(qū)域就可以包含多個key。另外硬盤相比內存比較慢，B樹因為是多叉樹相對于二叉樹更矮，所以能更多的減少硬盤交互的次數。

B樹有一些屬性，我更愿意稱這些屬性為規(guī)約或者說規(guī)約形成的結果：

1、B樹用來衡量每個節(jié)點(node)的大小的度量衡被稱為度(degree，簡寫為t)和秩(order，簡寫為m)。度和秩是不同的兩個角度，度是說B樹的任意節(jié)點(除了root節(jié)點)至少有t個分叉(至多2t個分叉)，秩是說B樹的任意節(jié)點(除了root節(jié)點)至多有m個分叉。后續(xù)將以度為度量衡進行解釋B樹。

2、因為任意節(jié)點(除了root節(jié)點)至少有t個分叉，所以任意節(jié)點(除了root節(jié)點)至少有t-1個key。

3、與2同理，任意節(jié)點(除了root節(jié)點)至多有2t-1個key。可見是個奇數。

4、任意節(jié)點中的key都是按升序排列的。所以可以在節(jié)點上方便的使用二分查找。

5、任意兩個key k1和k2中間的子樹的key都在k1到k2的范圍內。如上面的圖中所示。

6、Insert只會發(fā)生在葉子節(jié)點。

7、B樹的Search、Insert和Remove，都是從root節(jié)點出發(fā)的。

8、所有的葉子節(jié)點都在同一level。

9、與其他自平衡樹一樣，B樹的Search、Insert、Remove算法時間復雜度都是O(log N)。