1 B樹

在介紹B+樹之前， 先簡(jiǎn)單的介紹一下B樹，這兩種數(shù)據(jù)結(jié)構(gòu)既有相似之處，也有他們的區(qū)別，最后，我們也會(huì)對(duì)比一下這兩種數(shù)據(jù)結(jié)構(gòu)的區(qū)別。

[[277235]]

1.1 B樹概念

B樹也稱B-樹,它是一顆多路平衡查找樹。二叉樹我想大家都不陌生，其實(shí)，B樹和后面講到的B+樹也是從最簡(jiǎn)單的二叉樹變換而來的，并沒有什么神秘的地方，下面我們來看看B樹的定義。

• 每個(gè)節(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字(可以存有的鍵值對(duì))。
• 根節(jié)點(diǎn)最少可以只有1個(gè)關(guān)鍵字。
• 非根節(jié)點(diǎn)至少有m/2個(gè)關(guān)鍵字。
• 每個(gè)節(jié)點(diǎn)中的關(guān)鍵字都按照從小到大的順序排列，每個(gè)關(guān)鍵字的左子樹中的所有關(guān)鍵字都小于它，而右子樹中的所有關(guān)鍵字都大于它。
• 所有葉子節(jié)點(diǎn)都位于同一層，或者說根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的長(zhǎng)度都相同。
• 每個(gè)節(jié)點(diǎn)都存有索引和數(shù)據(jù)，也就是對(duì)應(yīng)的key和value。

所以，根節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量范圍：1 <= k <= m-1，非根節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量范圍：m/2 <= k <= m-1。

另外，我們需要注意一個(gè)概念，描述一顆B樹時(shí)需要指定它的階數(shù)，階數(shù)表示了一個(gè)節(jié)點(diǎn)最多有多少個(gè)孩子節(jié)點(diǎn)，一般用字母m表示階數(shù)。

我們?cè)倥e個(gè)例子來說明一下上面的概念，比如這里有一個(gè)5階的B樹，根節(jié)點(diǎn)數(shù)量范圍：1 <= k <= 4，非根節(jié)點(diǎn)數(shù)量范圍：2 <= k <= 4。

下面，我們通過一個(gè)插入的例子，講解一下B樹的插入過程，接著，再講解一下刪除關(guān)鍵字的過程。

1.2 B樹插入

插入的時(shí)候，我們需要記住一個(gè)規(guī)則：判斷當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)是否小于等于m-1，如果滿足，直接插入即可，如果不滿足，將節(jié)點(diǎn)的中間的key將這個(gè)節(jié)點(diǎn)分為左右兩部分，中間的節(jié)點(diǎn)放到父節(jié)點(diǎn)中即可。

例子：在5階B樹中，結(jié)點(diǎn)最多有4個(gè)key,最少有2個(gè)key(注意：下面的節(jié)點(diǎn)統(tǒng)一用一個(gè)節(jié)點(diǎn)表示key和value)。

插入18，70，50,40

插入22

插入22時(shí)，發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)的關(guān)鍵字已經(jīng)大于4了，所以需要進(jìn)行分裂，分裂的規(guī)則在上面已經(jīng)講了，分裂之后，如下。

接著插入23，25，39

分裂，得到下面的。

更過的插入的過程就不多介紹了，相信有這個(gè)例子你已經(jīng)知道怎么進(jìn)行插入操作了。

1.3 B樹的刪除操作

B樹的刪除操作相對(duì)于插入操作是相對(duì)復(fù)雜一些的，但是，你知道記住幾種情況，一樣可以很輕松的掌握的。

現(xiàn)在有一個(gè)初始狀態(tài)是下面這樣的B樹，然后進(jìn)行刪除操作。

刪除15，這種情況是刪除葉子節(jié)點(diǎn)的元素，如果刪除之后，節(jié)點(diǎn)數(shù)還是大于m/2，這種情況只要直接刪除即可。

接著，我們把22刪除，這種情況的規(guī)則：22是非葉子節(jié)點(diǎn)，對(duì)于非葉子節(jié)點(diǎn)的刪除，我們需要用后繼key(元素)覆蓋要?jiǎng)h除的key，然后在后繼key所在的子支中刪除該后繼key。對(duì)于刪除22，需要將后繼元素24移到被刪除的22所在的節(jié)點(diǎn)。

此時(shí)發(fā)現(xiàn)26所在的節(jié)點(diǎn)只有一個(gè)元素，小于2個(gè)(m/2)，這個(gè)節(jié)點(diǎn)不符合要求，這時(shí)候的規(guī)則(向兄弟節(jié)點(diǎn)借元素)：如果刪除葉子節(jié)點(diǎn)，如果刪除元素后元素個(gè)數(shù)少于(m/2)，并且它的兄弟節(jié)點(diǎn)的元素大于(m/2)，也就是說兄弟節(jié)點(diǎn)的元素比最少值m/2還多，將先將父節(jié)點(diǎn)的元素移到該節(jié)點(diǎn)，然后將兄弟節(jié)點(diǎn)的元素再移動(dòng)到父節(jié)點(diǎn)。這樣就滿足要求了。

我們看看操作過程就更加明白了。

接著刪除28，刪除葉子節(jié)點(diǎn)，刪除后不滿足要求，所以，我們需要考慮向兄弟節(jié)點(diǎn)借元素，但是，兄弟節(jié)點(diǎn)也沒有多的節(jié)點(diǎn)(2個(gè))，借不了，怎么辦呢?如果遇到這種情況，首先，還是將先將父節(jié)點(diǎn)的元素移到該節(jié)點(diǎn)，然后，將當(dāng)前節(jié)點(diǎn)及它的兄弟節(jié)點(diǎn)中的key合并，形成一個(gè)新的節(jié)點(diǎn)。

移動(dòng)之后，跟兄弟節(jié)點(diǎn)合并。

刪除就只有上面的幾種情況，根據(jù)不同的情況進(jìn)行刪除即可。

上面的這些介紹，相信對(duì)于B樹已經(jīng)有一定的了解了，接下來的一部分，我們接著講解B+樹，我相信加上B+樹的對(duì)比，就更加清晰明了了。

2 B+樹

2.1 B+樹概述

B+樹其實(shí)和B樹是非常相似的，我們首先看看相同點(diǎn)。

• 根節(jié)點(diǎn)至少一個(gè)元素
• 非根節(jié)點(diǎn)元素范圍：m/2 <= k <= m-1

不同點(diǎn)。

• B+樹有兩種類型的節(jié)點(diǎn)：內(nèi)部結(jié)點(diǎn)(也稱索引結(jié)點(diǎn))和葉子結(jié)點(diǎn)。內(nèi)部節(jié)點(diǎn)就是非葉子節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)索引，數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)。
• 內(nèi)部結(jié)點(diǎn)中的key都按照從小到大的順序排列，對(duì)于內(nèi)部結(jié)點(diǎn)中的一個(gè)key，左樹中的所有key都小于它，右子樹中的key都大于等于它。葉子結(jié)點(diǎn)中的記錄也按照key的大小排列。
• 每個(gè)葉子結(jié)點(diǎn)都存有相鄰葉子結(jié)點(diǎn)的指針，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
• 父節(jié)點(diǎn)存有右孩子的第一個(gè)元素的索引。

下面我們看一個(gè)B+樹的例子，感受感受它吧!

2.2 插入操作

對(duì)于插入操作很簡(jiǎn)單，只需要記住一個(gè)技巧即可：當(dāng)節(jié)點(diǎn)元素?cái)?shù)量大于m-1的時(shí)候，按中間元素分裂成左右兩部分，中間元素分裂到父節(jié)點(diǎn)當(dāng)做索引存儲(chǔ)，但是，本身中間元素還是分裂右邊這一部分的。

下面以一顆5階B+樹的插入過程為例，5階B+樹的節(jié)點(diǎn)最少2個(gè)元素，最多4個(gè)元素。

插入5，10，15，20

插入25，此時(shí)元素?cái)?shù)量大于4個(gè)了，分裂

接著插入26，30，繼續(xù)分裂

有了這幾個(gè)例子，相信插入操作沒什么問題了，下面接著看看刪除操作。

2.3 刪除操作

對(duì)于刪除操作是比B樹簡(jiǎn)單一些的，因?yàn)槿~子節(jié)點(diǎn)有指針的存在，向兄弟節(jié)點(diǎn)借元素時(shí)，不需要通過父節(jié)點(diǎn)了，而是可以直接通過兄弟節(jié)移動(dòng)即可(前提是兄弟節(jié)點(diǎn)的元素大于m/2)，然后更新父節(jié)點(diǎn)的索引;如果兄弟節(jié)點(diǎn)的元素不大于m/2(兄弟節(jié)點(diǎn)也沒有多余的元素)，則將當(dāng)前節(jié)點(diǎn)和兄弟節(jié)點(diǎn)合并，并且刪除父節(jié)點(diǎn)中的key，下面我們看看具體的實(shí)例。

初始狀態(tài)

刪除10，刪除后，不滿足要求，發(fā)現(xiàn)左邊兄弟節(jié)點(diǎn)有多余的元素，所以去借元素，最后，修改父節(jié)點(diǎn)索引

刪除元素5，發(fā)現(xiàn)不滿足要求，并且發(fā)現(xiàn)左右兄弟節(jié)點(diǎn)都沒有多余的元素，所以，可以選擇和兄弟節(jié)點(diǎn)合并，最后修改父節(jié)點(diǎn)索引

發(fā)現(xiàn)父節(jié)點(diǎn)索引也不滿足條件，所以，需要做跟上面一步一樣的操作

這樣，B+樹的刪除操作也就完成了，是不是看完之后，覺得非常簡(jiǎn)單!

3 B樹和B+樹總結(jié)

B+樹相對(duì)于B樹有一些自己的優(yōu)勢(shì)，可以歸結(jié)為下面幾點(diǎn)。

• 單一節(jié)點(diǎn)存儲(chǔ)的元素更多，使得查詢的IO次數(shù)更少，所以也就使得它更適合做為數(shù)據(jù)庫(kù)MySQL的底層數(shù)據(jù)結(jié)構(gòu)了。
• 所有的查詢都要查找到葉子節(jié)點(diǎn)，查詢性能是穩(wěn)定的，而B樹，每個(gè)節(jié)點(diǎn)都可以查找到數(shù)據(jù)，所以不穩(wěn)定。
• 所有的葉子節(jié)點(diǎn)形成了一個(gè)有序鏈表，更加便于查找。