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

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

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

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

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

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

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

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

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

6、Insert只會發生在葉子節點。

7、B樹的Search、Insert和Remove，都是從root節點出發的。

8、所有的葉子節點都在同一level。

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