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

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

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

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

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

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。可見(jiàn)是個(gè)奇數(shù)。

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

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

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

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

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

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