B-Tree該如何理解

今天就跟大家聊聊有關(guān)B-Tree該如何理解，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

B-Tree就是我們常說的B樹，一定不要讀成B減樹，否則就很丟人了。B樹這種數(shù)據(jù)結(jié)構(gòu)常常用于實現(xiàn)數(shù)據(jù)庫索引，因為它的查找效率比較高。

磁盤IO與預(yù)讀

磁盤讀取依靠的是機械運動，分為尋道時間、旋轉(zhuǎn)延遲、傳輸時間三個部分，這三個部分耗時相加就是一次磁盤IO的時間，大概9ms左右。這個成本是訪問內(nèi)存的十萬倍左右；正是由于磁盤IO是非常昂貴的操作，所以計算機操作系統(tǒng)對此做了優(yōu)化：預(yù)讀；每一次IO時，不僅僅把當前磁盤地址的數(shù)據(jù)加載到內(nèi)存，同時也把相鄰數(shù)據(jù)也加載到內(nèi)存緩沖區(qū)中。

因為局部預(yù)讀原理說明：當訪問一個地址數(shù)據(jù)的時候，與其相鄰的數(shù)據(jù)很快也會被訪問到。每次磁盤IO讀取的數(shù)據(jù)我們稱之為一頁（page）。一頁的大小與操作系統(tǒng)有關(guān)，一般為4k或者8k。這也就意味著讀取一頁內(nèi)數(shù)據(jù)的時候，實際上發(fā)生了一次磁盤IO。

B-Tree與二叉查找樹的對比

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

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

一、 二叉樹

我們先來看二叉樹查找時磁盤IO的次：定義一個樹高為4的二叉樹，查找值為10：

第一次磁盤IO：

 第二次磁盤IO

第三次磁盤IO:

第四次磁盤IO：

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

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

二、B-Tree

m階B-Tree滿足以下條件：

1、每個節(jié)點最多擁有m個子樹

2、根節(jié)點至少有2個子樹

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

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

如下有一個3階的B樹，觀察查找元素21的過程：

第一次磁盤IO：     

第二次磁盤IO：

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

第三次磁盤IO:

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

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

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

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

 三、B樹的新增

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

四、B樹的刪除

 刪除元素9：

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

看完上述內(nèi)容，你們對B-Tree該如何理解有進一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。