一. B樹的定義

1.1. B樹概念與使用場景

B樹（B-tree，所以很多人又稱為B-樹）
是一種自平衡的樹，一個(gè)節(jié)點(diǎn)可以擁有2個(gè)以上的子節(jié)點(diǎn)，能夠保持?jǐn)?shù)據(jù)有序。這種數(shù)據(jù)結(jié)構(gòu)能夠讓查找數(shù)據(jù)、順序訪問、插入數(shù)據(jù)及刪除的動(dòng)作，都在對(duì)數(shù)時(shí)間內(nèi)完成。

與自平衡二叉查找樹不同，B樹的每個(gè)節(jié)點(diǎn)可以包含大量的關(guān)鍵字信息和分支，便于降低自己的高度，讓自己更胖更矮，更加適用于讀寫相對(duì)大的數(shù)據(jù)塊的存儲(chǔ)系統(tǒng)，例如磁盤，可以減少定位記錄時(shí)所經(jīng)歷的中間過程，從而加快存取速度。B樹這種數(shù)據(jù)結(jié)構(gòu)可以用來描述外部存儲(chǔ)。這種數(shù)據(jù)結(jié)構(gòu)常被應(yīng)用在數(shù)據(jù)庫和文件系統(tǒng)的實(shí)現(xiàn)上。

在B樹中，內(nèi)部（非葉子）節(jié)點(diǎn)可以擁有可變數(shù)量的子節(jié)點(diǎn)（數(shù)量范圍預(yù)先定義好）。當(dāng)數(shù)據(jù)被插入或從一個(gè)節(jié)點(diǎn)中移除，它的子節(jié)點(diǎn)數(shù)量發(fā)生變化。為了維持在預(yù)先設(shè)定的數(shù)量范圍內(nèi)，內(nèi)部節(jié)點(diǎn)可能會(huì)被合并或者分離。因?yàn)樽庸?jié)點(diǎn)數(shù)量有一定的允許范圍，所以B樹不需要像其他自平衡查找樹那樣頻繁地重新保持平衡，在這點(diǎn)名批評(píng)紅黑樹，但是由于節(jié)點(diǎn)沒有被完全填充，可能浪費(fèi)了一些空間。

B樹的優(yōu)勢(shì)如下：

• 使關(guān)鍵字保持排序順序以進(jìn)行順序遍歷
• 使用分層索引來最大程度地減少磁盤讀取次數(shù)
• 使用部分完整的塊來加快插入和刪除
• 使用遞歸算法使索引保持平衡

總之，B樹操作不是很復(fù)雜，用途很廣泛，正道的光，照在了數(shù)據(jù)結(jié)構(gòu)的路上

1.2. B樹定義

根據(jù) Knuth 的定義，一個(gè) m 階的B樹是一個(gè)有以下屬性的樹：

• 每一個(gè)節(jié)點(diǎn)最多有 m 個(gè)子節(jié)點(diǎn)
• 每一個(gè)非葉子節(jié)點(diǎn)（除根節(jié)點(diǎn)）最少有 ?m/2? （向上取整）個(gè)子節(jié)點(diǎn)
• 如果根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，那么它至少有兩個(gè)子節(jié)點(diǎn)
• 有 k 個(gè)子節(jié)點(diǎn)的非葉子節(jié)點(diǎn)擁有 k ? 1 個(gè)鍵
• 所有的葉子節(jié)點(diǎn)都在同一層，葉子節(jié)點(diǎn)不包含任何關(guān)鍵字信息

但是其實(shí)文獻(xiàn)中B樹的術(shù)語并不統(tǒng)一
歐美在術(shù)語統(tǒng)一這方面一直都可以的 : )

術(shù)語階的定義不一致。

• Bayer & McCreightComer等人將B樹的階定義為非根節(jié)點(diǎn)擁有鍵的最小數(shù)量。Folk & Zoellick指出這一術(shù)語是模糊不清的。一個(gè) 3 階B樹鍵的最大數(shù)量可能為 6 或 7。 Knuth 通過將階定義為最大數(shù)量的子節(jié)點(diǎn)（鍵值數(shù)的最大值+1） 來避免了這一問題。

術(shù)語葉子的定義也不一致。

• Bayer & McCreight認(rèn)為葉子層是最下面一層的鍵，此時(shí)這些葉子節(jié)點(diǎn)只包含鍵值，子節(jié)點(diǎn)指針都指向不含任何信息的空的記錄。
• Knuth 認(rèn)為葉子層是最下面一層鍵之下的一層。如同紅黑樹那般（紅黑樹將Null指針作為黑色葉子節(jié)點(diǎn)），將Null作為葉子節(jié)點(diǎn)，此時(shí)葉子節(jié)點(diǎn)不存儲(chǔ)鍵值等任何信息。
• 我們一般以按Knuth大佬的說法來，清華的嚴(yán)蔚敏老師的數(shù)據(jù)結(jié)構(gòu)一書中也是這么定義的。

內(nèi)部節(jié)點(diǎn)：

• 每個(gè)內(nèi)部節(jié)點(diǎn)都至少含有 ?m/2? 個(gè)子節(jié)點(diǎn)，所以至少都是半滿的
• 當(dāng)父節(jié)點(diǎn)還沒滿時(shí)，一個(gè)滿子節(jié)點(diǎn)可以被分為兩個(gè)合法子節(jié)點(diǎn)
• 每個(gè)內(nèi)部節(jié)點(diǎn)（除葉子節(jié)點(diǎn)和根節(jié)點(diǎn)之外的所有節(jié)點(diǎn)）包含以下信息
  • 指向父節(jié)點(diǎn)的指針Parent*
  • 鍵值的個(gè)數(shù)KeyNum
  • 鍵值Key
  • KeyNum+1個(gè)指向子節(jié)點(diǎn)的指針Ptr*

根節(jié)點(diǎn)：

• 根節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)的最大值和內(nèi)部節(jié)點(diǎn)一樣都是m
• 根節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)沒有限制，當(dāng)根節(jié)點(diǎn)儲(chǔ)存的鍵值數(shù)小于?m/2?時(shí)，根節(jié)點(diǎn)可以沒有子節(jié)點(diǎn)，此時(shí)根節(jié)點(diǎn)為葉子節(jié)點(diǎn)。

二. B樹的操作

在B樹中，內(nèi)部（非葉子）節(jié)點(diǎn)可以在某個(gè)預(yù)定義范圍內(nèi)具有可變數(shù)量的子節(jié)點(diǎn)。 從節(jié)點(diǎn)插入或刪除數(shù)據(jù)時(shí)，其子節(jié)點(diǎn)數(shù)會(huì)更改。 為了維持預(yù)定范圍，可以將內(nèi)部節(jié)點(diǎn)連接或拆分。

2.1. m階B樹的高度

對(duì)硬盤訪問的IO次數(shù)取決于B樹的高度，B樹的高度如何確定呢？

首先明確的是不帶任何信息的一層葉節(jié)點(diǎn)不算做B樹的高度，通常，設(shè)一個(gè)m階B樹非葉子節(jié)點(diǎn)內(nèi)部的關(guān)鍵字范圍在d~2d范圍內(nèi)，d = ?m/2?

$$\begin{gathered} 設(shè)h為樹的高度（h\ge 0），空樹的高度表示為0 \\ n為樹中鍵值的總個(gè)數(shù)（n\ge 0），空樹的總鍵值數(shù)為0 \end{gathered}$$

$當(dāng)內(nèi)部關(guān)鍵字為2d即m時(shí)，樹的高度有最小值$
$h=0時(shí)，有n_0=0$
$h=1時(shí)，有n_1=m?1$
$h=2時(shí)，有n_2=m(m?1)+n_1=(m+1)(m?1)=m^2?1$
$h=3時(shí)，有n_3=m^2(m?1)+n_2=(m^2+m+1)(m?1)=m^3?1$
$\dots$
$h=h時(shí)，有n=m^h?1$
$所以h_{min}=lo{g}_m(n+1)$

$當(dāng)內(nèi)部關(guān)鍵字為d時(shí)即?m/2?時(shí)，樹的高度有最大值$
$h=0時(shí)，n_0=0$
$h=1時(shí)，非葉子根節(jié)點(diǎn)最少兩個(gè)子節(jié)點(diǎn)和一個(gè)關(guān)鍵字，所以有n_1=1$
$h=2時(shí)，有n_2=2(?m/2??1)+1=2?m/2??1$
$h=3時(shí)，有n_3=2?m/2?(?m/2??1)+n_2=2{?m/2?}^2?1$
$\dots$
$n=2{?m/2?}^{h?1}?1$
$h_{max}=lo{g}_{?m/2?}(\frac{n+1}{2})+1$

看上去很復(fù)雜，其實(shí)就是等差數(shù)列求和

2.2.插入

所有的插入都從根節(jié)點(diǎn)開始。要插入一個(gè)新的元素，首先搜索這棵樹找到新元素應(yīng)該被添加到的對(duì)應(yīng)節(jié)點(diǎn)。將新元素插入到這一節(jié)點(diǎn)中的步驟如下：

• 如果節(jié)點(diǎn)擁有的元素?cái)?shù)量小于最大值，那么有空間容納新的元素。將新元素插入到這一節(jié)點(diǎn)，且保持節(jié)點(diǎn)中元素有序。
• 否則的話這一節(jié)點(diǎn)已經(jīng)滿了，將它平均地分裂成兩個(gè)節(jié)點(diǎn)：
  • 從該節(jié)點(diǎn)的原有元素和新的元素中選擇出中位數(shù)，小于這一中位數(shù)的元素放入左邊節(jié)點(diǎn)，大于這一中位數(shù)的元素放入右邊節(jié)點(diǎn)，中位數(shù)作為分隔值。
  • 分隔值被插入到父節(jié)點(diǎn)中，這可能會(huì)造成父節(jié)點(diǎn)分裂，分裂父節(jié)點(diǎn)時(shí)可能又會(huì)使它的父節(jié)點(diǎn)分裂，以此類推。如果沒有父節(jié)點(diǎn)（這一節(jié)點(diǎn)是根節(jié)點(diǎn)），就創(chuàng)建一個(gè)新的根節(jié)點(diǎn)（增加了樹的高度）。如果分裂一直上升到根節(jié)點(diǎn)，那么一個(gè)新的根節(jié)點(diǎn)會(huì)被創(chuàng)建，它有一個(gè)分隔值和兩個(gè)子節(jié)點(diǎn)。這就是根節(jié)點(diǎn)并不像內(nèi)部節(jié)點(diǎn)一樣有最少子節(jié)點(diǎn)數(shù)量限制的原因。

例子，已有4階B樹如下

插入4，根據(jù)分層查找關(guān)鍵字，直接插入：

插入17，根據(jù)分層查找關(guān)鍵字，直接插入：

插入20，子節(jié)點(diǎn)中關(guān)鍵字達(dá)到m-1，故無法繼續(xù)插入，子節(jié)點(diǎn)分割，16分至父節(jié)點(diǎn)：

插入21、22，直到分裂出新的根節(jié)點(diǎn)

2.3.刪除

刪除葉子節(jié)點(diǎn)中的元素

• 搜索要?jiǎng)h除的元素
• 如果它在葉子節(jié)點(diǎn)，將它從中刪除
• 如果發(fā)生了下溢出，按照后面 “刪除后重新平衡”部分的描述重新調(diào)整樹

刪除內(nèi)部節(jié)點(diǎn)中的元素
內(nèi)部節(jié)點(diǎn)中的每一個(gè)元素都作為分隔兩顆子樹的分隔值，因此我們需要重新劃分。值得注意的是左子樹中最大的元素仍然小于分隔值，右子樹中最小的元素仍然大于分隔值，這兩個(gè)元素都在葉子節(jié)點(diǎn)中，并且任何一個(gè)都可以作為兩顆子樹的新分隔值。算法的描述如下：

• 選擇一個(gè)新的分隔符（左子樹中最大的元素或右子樹中最小的元素），將它從子節(jié)點(diǎn)中移除，替換掉被刪除的元素作為新的分隔值。
• 前一步刪除了一個(gè)子節(jié)點(diǎn)中的元素。如果這個(gè)子節(jié)點(diǎn)擁有的元素?cái)?shù)量小于最低要求，那么從這一子節(jié)點(diǎn)開始重新進(jìn)行平衡。

刪除后的重新平衡
重新平衡從葉子節(jié)點(diǎn)開始向根節(jié)點(diǎn)進(jìn)行，直到樹重新平衡。如果刪除節(jié)點(diǎn)中的一個(gè)元素使該節(jié)點(diǎn)的元素?cái)?shù)量低于最小值，那么一些元素必須被重新分配。通常，移動(dòng)一個(gè)元素?cái)?shù)量大于最小值的兄弟節(jié)點(diǎn)中的元素。如果兄弟節(jié)點(diǎn)都沒有多余的元素，那么缺少元素的節(jié)點(diǎn)就必須要和他的兄弟節(jié)點(diǎn)合并。合并可能導(dǎo)致父節(jié)點(diǎn)失去了分隔值，所以父節(jié)點(diǎn)可能缺少元素并需要重新平衡。合并和重新平衡可能一直進(jìn)行到根節(jié)點(diǎn)，根節(jié)點(diǎn)變成惟一缺少元素的節(jié)點(diǎn)。重新平衡樹的遞歸算法如下：

• 如果缺少元素節(jié)點(diǎn)的右兄弟存在且擁有多余的元素，那么向左旋轉(zhuǎn)，這里的左旋轉(zhuǎn)與AVL中的左旋轉(zhuǎn)類似。
  • 將父節(jié)點(diǎn)的分隔值復(fù)制到缺少元素節(jié)點(diǎn)的最后（分隔值被移下來；缺少元素的節(jié)點(diǎn)現(xiàn)在有最小數(shù)量的元素）
  • 將父節(jié)點(diǎn)的分隔值替換為右兄弟的第一個(gè)元素（右兄弟失去了一個(gè)節(jié)點(diǎn)但仍然擁有最小數(shù)量的元素）
  • 樹又重新平衡
• 否則，如果缺少元素節(jié)點(diǎn)的左兄弟存在且擁有多余的元素，那么向右旋轉(zhuǎn)
  • 將父節(jié)點(diǎn)的分隔值復(fù)制到缺少元素節(jié)點(diǎn)的第一個(gè)節(jié)點(diǎn)（分隔值被移下來；缺少元素的節(jié)點(diǎn)現(xiàn)在有最小數(shù)量的元素）
  • 將父節(jié)點(diǎn)的分隔值替換為左兄弟的最后一個(gè)元素（左兄弟失去了一個(gè)節(jié)點(diǎn)但仍然擁有最小數(shù)量的元素）
  • 樹又重新平衡
• 否則，如果它的兩個(gè)直接兄弟節(jié)點(diǎn)都只有最小數(shù)量的元素，那么將它與一個(gè)直接兄弟節(jié)點(diǎn)以及父節(jié)點(diǎn)中它們的分隔值合并
  • 將分隔值復(fù)制到左邊的節(jié)點(diǎn)（左邊的節(jié)點(diǎn)可以是缺少元素的節(jié)點(diǎn)或者擁有最小數(shù)量元素的兄弟節(jié)點(diǎn)）
  • 將右邊節(jié)點(diǎn)中所有的元素移動(dòng)到左邊節(jié)點(diǎn)（左邊節(jié)點(diǎn)現(xiàn)在擁有最大數(shù)量的元素，右邊節(jié)點(diǎn)為空）
  • 將父節(jié)點(diǎn)中的分隔值和空的右子樹移除（父節(jié)點(diǎn)失去了一個(gè)元素）
  • 如果父節(jié)點(diǎn)是根節(jié)點(diǎn)并且沒有元素了，那么釋放它并且讓合并之后的節(jié)點(diǎn)成為新的根節(jié)點(diǎn)（樹的深度減小）
  • 否則，如果父節(jié)點(diǎn)的元素?cái)?shù)量小于最小值，重新平衡父節(jié)點(diǎn)

先有4階B樹：

刪除22，分層查詢鍵值后，在葉子節(jié)點(diǎn)中直接刪除：

刪除3，父節(jié)點(diǎn)從右兒子那選擇最小值（或左兒子那選擇最大值），為新的鍵值（分隔值）：

刪除5，此時(shí)左兄弟只有一個(gè)鍵值1，沒有多余鍵值，借不了，所以需要合并，將父節(jié)點(diǎn)中的分隔值4加入到左兒子節(jié)點(diǎn)，右兒子剩下的所有元素合并到左兒子中，合并后父節(jié)點(diǎn)為鍵值數(shù)為0，小于規(guī)定的最小鍵值數(shù)1（?m/2?-1），對(duì)父節(jié)點(diǎn)遞歸算法

在新一輪的算法中，對(duì)剛才失衡的父節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn)：

三. B+樹的定義

3.1.B+樹的定義

B+樹可以視為B樹的一個(gè)變種，不同的是B+樹內(nèi)部節(jié)點(diǎn)不保存數(shù)據(jù)，非葉結(jié)點(diǎn)中的每個(gè)引索項(xiàng)只含有對(duì)應(yīng)子樹的最大關(guān)鍵字和指向子樹的指針，不含有該關(guān)鍵字對(duì)應(yīng)記錄的存儲(chǔ)地址，例如關(guān)系型數(shù)據(jù)庫Mysql。
一顆m階的B+樹需要滿足下列條件：

• 每個(gè)分支結(jié)點(diǎn)最多包含m棵子樹
• 非根結(jié)點(diǎn)至少有兩棵子樹，其他每個(gè)分支結(jié)點(diǎn)至少含有$?m/2?$棵子樹
• 如果根節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，那么它至少有兩個(gè)子節(jié)點(diǎn)
• 結(jié)點(diǎn)的子樹個(gè)數(shù)與關(guān)鍵字個(gè)數(shù)相同，所有分支結(jié)點(diǎn)中僅包含它的子結(jié)點(diǎn)中關(guān)鍵字最大值以及指向該子結(jié)點(diǎn)的指針
• 所有葉結(jié)點(diǎn)包含全部關(guān)鍵字以及指向相應(yīng)記錄的指針，葉結(jié)點(diǎn)中將關(guān)鍵字按大小順序排列，并且相鄰葉結(jié)點(diǎn)按大小順序相互鏈接起來
  

3.2.B+樹 VS B樹

B+樹相對(duì)于B樹的優(yōu)勢(shì)有：

• 內(nèi)部節(jié)點(diǎn)不保存數(shù)據(jù)，占用空間小，所以每個(gè)節(jié)點(diǎn)可以存儲(chǔ)的索引更多，即每個(gè)磁盤頁存儲(chǔ)的索引更多，樹的高度更低，IO次數(shù)更低，磁盤查詢效率更高
• 每次查詢都要到達(dá)最下面的葉子層才能拿到數(shù)據(jù)，性能更加穩(wěn)定
• 所有數(shù)據(jù)都保存在葉子節(jié)點(diǎn)，所有葉子節(jié)點(diǎn)都順次連接，有利于遍歷操作

現(xiàn)在你知道為什么數(shù)據(jù)庫用B+樹而不用B樹了吧。

四. B+樹的操作

4.1.插入

如果節(jié)點(diǎn)超過節(jié)點(diǎn)中鍵值數(shù)的規(guī)定范圍則處于違規(guī)狀態(tài)

• 首先，查找要插入其中的節(jié)點(diǎn)的位置。接著把值插入這個(gè)節(jié)點(diǎn)中。
• 如果沒有節(jié)點(diǎn)處于違規(guī)狀態(tài)則處理結(jié)束。
• 如果某個(gè)節(jié)點(diǎn)有過多元素，則把它分裂為兩個(gè)節(jié)點(diǎn)，每個(gè)都有最小數(shù)目的元素，同時(shí)將分隔值復(fù)制到父節(jié)點(diǎn)中作為索引。
  • 在樹上遞歸向上繼續(xù)這個(gè)處理直到到達(dá)根節(jié)點(diǎn)，如果根節(jié)點(diǎn)被分裂，則創(chuàng)建一個(gè)新根節(jié)點(diǎn)。

現(xiàn)有一個(gè)4階B+樹

插入2，分層遍歷索引，直接插入：

插入8，分層遍歷索引，節(jié)點(diǎn)已滿，于是分裂，將新的間隔值6復(fù)制到父節(jié)點(diǎn)中作為索引，產(chǎn)生兩個(gè)新的子節(jié)點(diǎn)：

4.2.刪除刪除

• 首先，在葉子節(jié)點(diǎn)中查找要?jiǎng)h除的值。接著從包含它的節(jié)點(diǎn)中刪除這個(gè)值。
• 如果沒有節(jié)點(diǎn)處于違規(guī)狀態(tài)則處理結(jié)束。
• 如果節(jié)點(diǎn)處于違規(guī)狀態(tài)則有兩種可能情況：
  • 它的兄弟節(jié)點(diǎn)，就是同一個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)，可以把一個(gè)或多個(gè)它的子節(jié)點(diǎn)轉(zhuǎn)移到當(dāng)前節(jié)點(diǎn)，而把它返回為合法狀態(tài)，最后再使用從兄弟那借到的鍵值替代父節(jié)點(diǎn)中的分隔鍵值之后處理結(jié)束。
  • 它的兄弟節(jié)點(diǎn)由于處在低邊界上而沒有額外的子節(jié)點(diǎn)。在這種情況下把兩個(gè)兄弟節(jié)點(diǎn)合并到一個(gè)單一的節(jié)點(diǎn)中，并刪除父節(jié)點(diǎn)中的分隔鍵值
  • 如果刪除后的父節(jié)點(diǎn)鍵值數(shù)量不足，進(jìn)行與B樹完全相同的刪除平衡操作

現(xiàn)有一4階B+樹：

刪除8，分層遍歷索引，直接刪除：

刪除2，找左兄弟借一個(gè)數(shù)據(jù)2，用借來的鍵值2替代父節(jié)點(diǎn)中初始的索引2：

刪除4，兄弟節(jié)點(diǎn)沒有數(shù)據(jù)可以借，于是與左兄弟節(jié)點(diǎn)合并，刪除父節(jié)點(diǎn)的索引4：

刪除5、6，刪除5時(shí)可以向右兄弟借到6，刪除6時(shí)就完全借不到了，只能合并，再刪除父節(jié)點(diǎn)中的索引

刪除7，兄弟節(jié)點(diǎn)借不到，合并后刪除父節(jié)點(diǎn)中的索引，父節(jié)點(diǎn)不符合規(guī)則，對(duì)父節(jié)點(diǎn)進(jìn)行刪除后的平衡操作，父親節(jié)點(diǎn)的兄弟節(jié)點(diǎn)只有一個(gè)鍵值2，于是父節(jié)點(diǎn)與兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)的索引3進(jìn)行合并

紅黑樹傳遞門，沖沖沖

總結(jié)

以上是生活随笔為你收集整理的B树、B+树其实很简单，看不懂你找我的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。