這次準(zhǔn)備出一個(gè)關(guān)于B樹的合集。在第一部分，先來(lái)介紹下B樹的基本概念。

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

B樹常常用于數(shù)據(jù)庫(kù)。數(shù)據(jù)庫(kù)常常數(shù)據(jù)量巨大，因此不可能光放到內(nèi)存中，需要放到硬盤中進(jìn)行存儲(chǔ)。而硬盤是塊設(shè)備，就是一次讀取一塊區(qū)域，而B樹是多叉樹，因此有多個(gè)key，所以一塊區(qū)域就可以包含多個(gè)key。另外硬盤相比內(nèi)存比較慢，B樹因?yàn)槭嵌嗖鏄湎鄬?duì)于二叉樹更矮，所以能更多的減少硬盤交互的次數(shù)。

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

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

2、因?yàn)槿我夤?jié)點(diǎn)(除了root節(jié)點(diǎn))至少有t個(gè)分叉，所以任意節(jié)點(diǎn)(除了root節(jié)點(diǎn))至少有t-1個(gè)key。

3、與2同理，任意節(jié)點(diǎn)(除了root節(jié)點(diǎn))至多有2t-1個(gè)key?？梢娛莻€(gè)奇數(shù)。

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

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

6、Insert只會(huì)發(fā)生在葉子節(jié)點(diǎn)。

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

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

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