什么是B-Tree

B-Tree就是我們常說(shuō)的B樹(shù)，一定不要讀成B減樹(shù)，否則就很丟人了。B樹(shù)這種數(shù)據(jù)結(jié)構(gòu)常常用于實(shí)現(xiàn)數(shù)據(jù)庫(kù)索引，因?yàn)樗牟檎倚时容^高。

磁盤(pán)IO與預(yù)讀

磁盤(pán)讀取依靠的是機(jī)械運(yùn)動(dòng)，分為尋道時(shí)間、旋轉(zhuǎn)延遲、傳輸時(shí)間三個(gè)部分，這三個(gè)部分耗時(shí)相加就是一次磁盤(pán)IO的時(shí)間，大概9ms左右。這個(gè)成本是訪問(wèn)內(nèi)存的十萬(wàn)倍左右；正是由于磁盤(pán)IO是非常昂貴的操作，所以計(jì)算機(jī)操作系統(tǒng)對(duì)此做了優(yōu)化：預(yù)讀；每一次IO時(shí)，不僅僅把當(dāng)前磁盤(pán)地址的數(shù)據(jù)加載到內(nèi)存，同時(shí)也把相鄰數(shù)據(jù)也加載到內(nèi)存緩沖區(qū)中。因?yàn)榫植款A(yù)讀原理說(shuō)明：當(dāng)訪問(wèn)一個(gè)地址數(shù)據(jù)的時(shí)候，與其相鄰的數(shù)據(jù)很快也會(huì)被訪問(wèn)到。每次磁盤(pán)IO讀取的數(shù)據(jù)我們稱(chēng)之為一頁(yè)（page）。一頁(yè)的大小與操作系統(tǒng)有關(guān)，一般為4k或者8k。這也就意味著讀取一頁(yè)內(nèi)數(shù)據(jù)的時(shí)候，實(shí)際上發(fā)生了一次磁盤(pán)IO。

B-Tree與二叉查找樹(shù)的對(duì)比

我們知道二叉查找樹(shù)查詢(xún)的時(shí)間復(fù)雜度是O（logN），查找速度最快和比較次數(shù)最少，既然性能已經(jīng)如此優(yōu)秀，但為什么實(shí)現(xiàn)索引是使用B-Tree而不是二叉查找樹(shù)，關(guān)鍵因素是磁盤(pán)IO的次數(shù)。

數(shù)據(jù)庫(kù)索引是存儲(chǔ)在磁盤(pán)上，當(dāng)表中的數(shù)據(jù)量比較大時(shí)，索引的大小也跟著增長(zhǎng)，達(dá)到幾個(gè)G甚至更多。當(dāng)我們利用索引進(jìn)行查詢(xún)的時(shí)候，不可能把索引全部加載到內(nèi)存中，只能逐一加載每個(gè)磁盤(pán)頁(yè)，這里的磁盤(pán)頁(yè)就對(duì)應(yīng)索引樹(shù)的節(jié)點(diǎn)。

一、 二叉樹(shù)

我們先來(lái)看二叉樹(shù)查找時(shí)磁盤(pán)IO的次：定義一個(gè)樹(shù)高為4的二叉樹(shù)，查找值為10：

第一次磁盤(pán)IO：

第二次磁盤(pán)IO

第三次磁盤(pán)IO:

第四次磁盤(pán)IO：

從二叉樹(shù)的查找過(guò)程了來(lái)看，樹(shù)的高度和磁盤(pán)IO的次數(shù)都是4，所以最壞的情況下磁盤(pán)IO的次數(shù)由樹(shù)的高度來(lái)決定。

從前面分析情況來(lái)看，減少磁盤(pán)IO的次數(shù)就必須要壓縮樹(shù)的高度，讓瘦高的樹(shù)盡量變成矮胖的樹(shù)，所以B-Tree就在這樣偉大的時(shí)代背景下誕生了。

二、B-Tree

m階B-Tree滿(mǎn)足以下條件：

1、每個(gè)節(jié)點(diǎn)最多擁有m個(gè)子樹(shù)

2、根節(jié)點(diǎn)至少有2個(gè)子樹(shù)

3、分支節(jié)點(diǎn)至少擁有m/2顆子樹(shù)（除根節(jié)點(diǎn)和葉子節(jié)點(diǎn)外都是分支節(jié)點(diǎn)）

4、所有葉子節(jié)點(diǎn)都在同一層、每個(gè)節(jié)點(diǎn)最多可以有m-1個(gè)key，并且以升序排列

如下有一個(gè)3階的B樹(shù)，觀察查找元素21的過(guò)程：

第一次磁盤(pán)IO：

第二次磁盤(pán)IO：

這里有一次內(nèi)存比對(duì)：分別跟3與12比對(duì)

第三次磁盤(pán)IO:

這里有一次內(nèi)存比對(duì)，分別跟14與21比對(duì)

從查找過(guò)程中發(fā)現(xiàn)，B樹(shù)的比對(duì)次數(shù)和磁盤(pán)IO的次數(shù)與二叉樹(shù)相差不了多少，所以這樣看來(lái)并沒(méi)有什么優(yōu)勢(shì)。

但是仔細(xì)一看會(huì)發(fā)現(xiàn)，比對(duì)是在內(nèi)存中完成中，不涉及到磁盤(pán)IO，耗時(shí)可以忽略不計(jì)。另外B樹(shù)種一個(gè)節(jié)點(diǎn)中可以存放很多的key（個(gè)數(shù)由樹(shù)階決定）。

相同數(shù)量的key在B樹(shù)中生成的節(jié)點(diǎn)要遠(yuǎn)遠(yuǎn)少于二叉樹(shù)中的節(jié)點(diǎn)，相差的節(jié)點(diǎn)數(shù)量就等同于磁盤(pán)IO的次數(shù)。這樣到達(dá)一定數(shù)量后，性能的差異就顯現(xiàn)出來(lái)了。

三、B樹(shù)的新增

在剛才的基礎(chǔ)上新增元素4，它應(yīng)該在3與9之間：

四、B樹(shù)的刪除

刪除元素9：

五、總結(jié)

插入或者刪除元素都會(huì)導(dǎo)致節(jié)點(diǎn)發(fā)生裂變反應(yīng)，有時(shí)候會(huì)非常麻煩，但正因?yàn)槿绱瞬抛孊樹(shù)能夠始終保持多路平衡，這也是B樹(shù)自身的一個(gè)優(yōu)勢(shì)：自平衡；B樹(shù)主要應(yīng)用于文件系統(tǒng)以及部分?jǐn)?shù)據(jù)庫(kù)索引，如MongoDB，大部分關(guān)系型數(shù)據(jù)庫(kù)索引則是使用B+樹(shù)實(shí)現(xiàn)。