簡(jiǎn)介

B 樹是為了磁盤或其它存儲(chǔ)設(shè)備而設(shè)計(jì)的一種多叉平衡查找樹寞宫。（相對(duì)于二叉缎罢，B樹每個(gè)內(nèi)結(jié)點(diǎn)有多個(gè)分支少梁，即多叉）
B樹又可以寫成B-樹/B-Tree，并不是B“減”樹稚照，橫杠為連接符蹂空，容易被誤導(dǎo)
首先我們介紹一下一棵 m 階B-tree的特性

m 階的定義：一個(gè)節(jié)點(diǎn)能擁有的最大子節(jié)點(diǎn)數(shù)來(lái)表示這顆樹的階數(shù)
舉個(gè)例子：
如果一個(gè)節(jié)點(diǎn)最多有 n 個(gè)key俯萌，那么這個(gè)節(jié)點(diǎn)最多就會(huì)有 n+1 個(gè)子節(jié)點(diǎn)，這棵樹就叫做 n+1（m=n+1）階樹

包括以下5條特性

1.每個(gè)結(jié)點(diǎn)x(假設(shè)為x)有如下屬性:
  - x.n上枕，表示當(dāng)前存儲(chǔ)在結(jié)點(diǎn)x中的關(guān)鍵字個(gè)數(shù)绳瘟。
  - x.n的各個(gè)關(guān)鍵字本身：x.key1, x.key2, … 以非降序存放(升序)，使得 x.key1 ≤ x.key2 ≤ …
  - x.leaf姿骏，是一個(gè)布爾值糖声，如果x是葉子結(jié)點(diǎn)，則為TRUE, 如果x為內(nèi)部結(jié)點(diǎn)分瘦，則為FALSE蘸泻。

2.每個(gè)'內(nèi)部結(jié)點(diǎn)x'還包含x.n+1個(gè)指向它的孩子的指針x.c1, x.c2, … 。 葉子結(jié)點(diǎn)沒有孩子結(jié)點(diǎn)嘲玫，所以他的ci屬性沒有定義悦施。
 - key和指針互相間隔，節(jié)點(diǎn)兩端是指針去团，所以節(jié)點(diǎn)中指針比key多一個(gè)抡诞。
 - 每個(gè)指針要么為null，要么指向另外一個(gè)節(jié)點(diǎn)土陪。

3.關(guān)鍵字x.keyi對(duì)存儲(chǔ)在各子樹中的關(guān)鍵字進(jìn)行分割：如果ki為任意一個(gè)存儲(chǔ)在以x.ci為根的子樹中的關(guān)鍵字昼汗，那么：
k1 ≤ x.key1 ≤ k2 x.key2 ≤ … ≤ x.keyx.n ≤ kx.n+1
難理解可以這么說(shuō)：
> 如果某個(gè)指針在節(jié)點(diǎn)node最左邊且不為null，則其指向節(jié)點(diǎn)的所有key小于(key1)鬼雀，其中(key1)為node的第一個(gè)key的值顷窒。

> 如果某個(gè)指針在節(jié)點(diǎn)node最右邊且不為null，則其指向節(jié)點(diǎn)的所有key大于(keym)源哩，其中(keym)為node的最后一個(gè)key的值鞋吉。

> 如果某個(gè)指針在節(jié)點(diǎn)node的左右相鄰key分別是keyi和keyi+1且不為null，則其指向節(jié)點(diǎn)的所有key小于(keyi+1)且大于(keyi)励烦。

4.每個(gè)葉子結(jié)點(diǎn)具有相同的深度谓着，即樹的高度h

5.每個(gè)結(jié)點(diǎn)所包含的的關(guān)鍵字個(gè)數(shù)有上界和下界。用一個(gè)被稱作B樹的最小度數(shù)的估計(jì)整數(shù)t(t ≥ 2)來(lái)表示這些界：
除了根結(jié)點(diǎn)以外的每個(gè)結(jié)點(diǎn)必須**至少**有t-1個(gè)關(guān)鍵字坛掠。因此赊锚，除了根節(jié)點(diǎn)以外的每個(gè)內(nèi)部結(jié)點(diǎn)**至少**有t個(gè)孩子。（因?yàn)樯厦嬲f(shuō)了右x.n+1個(gè)指向它的孩子的指針）
如果樹非空却音，根結(jié)點(diǎn)至少有一個(gè)關(guān)鍵字狈究。
每個(gè)結(jié)點(diǎn)**最多**包含2t-1個(gè)關(guān)鍵字挤巡。因此，一個(gè)內(nèi)部節(jié)點(diǎn)至多可有2t個(gè)孩子揖闸。當(dāng)一個(gè)結(jié)點(diǎn)恰好有2t-1個(gè)關(guān)鍵字時(shí)句灌，稱該結(jié)點(diǎn)是滿的(full)夷陋。

3階B-tree示意圖

拿中間一層最左邊舉例說(shuō)明：

1.  x.n = 2 有倆個(gè)關(guān)鍵字
    分別為 x.key1 = 8  x.key2 = 12 且 8<12
    x.leaf = false為內(nèi)部節(jié)點(diǎn)
2.  含有3個(gè)指向它孩子的指針P1 P2 P3
3.  關(guān)鍵字x.key1=8 它的左邊指針P1 對(duì) 子樹 3 5 分割 滿足 3和5都小于8
    關(guān)鍵字x.key1=8 它的右邊指針P2 對(duì) 子樹 9 10 分割 滿足 9和10都大于8（同為12的左指針）
    關(guān)鍵字x.key2=12 它的右邊指針P3 對(duì) 子樹 13 15 分割 滿足 13和15都大于12

實(shí)際磁盤舉例：

關(guān)鍵字插入操作

生成從空樹開始碌冶，逐個(gè)插入關(guān)鍵字棺耍。但是由于B_樹節(jié)點(diǎn)關(guān)鍵字必須大于等于[ceil(m/2)-1],（其中ceil(x)是一個(gè)取上限的函數(shù)）所以每次插入一個(gè)關(guān)鍵字；首先在最底層（葉子節(jié)點(diǎn)那一層）的某個(gè)非終端節(jié)點(diǎn)中添加一個(gè)“關(guān)鍵字”种樱，該結(jié)點(diǎn)的關(guān)鍵字不超過(guò)m-1,則插入完成蒙袍；否則要產(chǎn)生結(jié)點(diǎn)的“分裂”，將一半數(shù)量的關(guān)鍵字分裂到新的其相鄰右結(jié)點(diǎn)中嫩挤，中間關(guān)鍵字上移到父結(jié)點(diǎn)中害幅。

下面一個(gè)實(shí)例：我們需要用C N G A H E K Q M F W L T Z D P R X Y S來(lái)構(gòu)造5階B樹
這設(shè)計(jì)一個(gè) B樹的階數(shù)的最優(yōu)選取

• 首先，根結(jié)點(diǎn)空間足夠岂昭，4個(gè)字母插入相同的結(jié)點(diǎn)中以现，如下圖：

  
  
  記住排序哦

• 當(dāng)咱們?cè)囍迦際時(shí)，結(jié)點(diǎn)發(fā)現(xiàn)空間不夠约啊，以致將其分裂成2個(gè)結(jié)點(diǎn)邑遏，移動(dòng)中間關(guān)鍵字G上移到新的根結(jié)點(diǎn)中，在實(shí)現(xiàn)過(guò)程中恰矩，咱們把A和C留在當(dāng)前結(jié)點(diǎn)中记盒，而H和N放置新的其右鄰居結(jié)點(diǎn)中。如下圖：

  
  

• 插入E,K,Q時(shí)外傅，不需要任何分裂操作

  
  

• 插入M需要一次分裂纪吮，注意M恰好是中間關(guān)鍵字俩檬，以致向上移到父節(jié)點(diǎn)中

  
  

• 插入F,W,L,T不需要任何分裂操作

  
  

• 插入Z時(shí)，最右的葉子結(jié)點(diǎn)空間滿了碾盟，需要進(jìn)行分裂操作棚辽，中間關(guān)鍵字T上移到父節(jié)點(diǎn)中，注意通過(guò)上移中間關(guān)鍵字冰肴，樹最終還是保持平衡屈藐，分裂結(jié)果的結(jié)點(diǎn)存在2個(gè)關(guān)鍵字。

  
  

• 插入D時(shí)熙尉，導(dǎo)致最左邊的葉子結(jié)點(diǎn)被分裂估盘，D恰好也是中間關(guān)鍵字，上移到父節(jié)點(diǎn)中骡尽，然后字母P,R,X,Y陸續(xù)插入不需要任何分裂操作（別忘了遣妥，樹中至多5個(gè)孩子）。

  
  

• 最后攀细，當(dāng)插入S時(shí)箫踩，含有N,P,Q,R的結(jié)點(diǎn)需要分裂，把中間關(guān)鍵字Q上移到父節(jié)點(diǎn)中谭贪，但是情況來(lái)了境钟，父節(jié)點(diǎn)中空間已經(jīng)滿了，所以也要進(jìn)行分裂俭识，將父節(jié)點(diǎn)中的中間關(guān)鍵字M上移到新形成的根結(jié)點(diǎn)中慨削，注意以前在父節(jié)點(diǎn)中的第三個(gè)指針在修改后包括D和G節(jié)點(diǎn)中。這樣具體插入操作的完成

  
  

關(guān)鍵字刪除操作

首先查找B樹中需刪除的關(guān)鍵字,如果該關(guān)鍵字在B樹中存在套媚，則將該關(guān)鍵字在其結(jié)點(diǎn)中進(jìn)行刪除缚态，如果刪除該關(guān)鍵字后，首先判斷其結(jié)點(diǎn)是否有左右孩子結(jié)點(diǎn)堤瘤，如果有玫芦，則上移孩子結(jié)點(diǎn)中的某相近關(guān)鍵字到父節(jié)點(diǎn)中，然后是判斷移動(dòng)之后的情況本辐；如果沒有桥帆，直接刪除后，判斷刪除之后的情況慎皱。
刪除元素老虫，移動(dòng)相近元素之后，如果某結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)小于ceil(m/2)-1,
（m為階數(shù)）則需要看其某相鄰兄弟結(jié)點(diǎn)是否豐滿
如果豐滿茫多，則向父節(jié)點(diǎn)借一個(gè)元素來(lái)滿足條件祈匙；如果其相鄰兄弟都剛脫貧，即借了之后其結(jié)點(diǎn)數(shù)目小于ceil(m/2)-1則該結(jié)點(diǎn)與其相鄰的某一兄弟結(jié)點(diǎn)進(jìn)行“合并”成一個(gè)結(jié)點(diǎn)地梨，以此來(lái)滿足條件菊卷。
(結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)大于ceil(m/2)-1除根結(jié)點(diǎn)之外的結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)n必須滿足： ceil(m / 2)-1）<= n <= m-1缔恳。m表示最多含有m個(gè)孩子宝剖，n表示關(guān)鍵字?jǐn)?shù).)

實(shí)例：
最初態(tài)5階B樹 實(shí)現(xiàn)依次刪除H,T,R,E
關(guān)鍵字?jǐn)?shù)最小為ceil(m / 2)-1=2洁闰。最多為m-1=4

• 首先刪除關(guān)鍵字H，當(dāng)然首先查找H万细，H在一個(gè)葉子結(jié)點(diǎn)中扑眉，且該葉子結(jié)點(diǎn)關(guān)鍵字數(shù)目3大于最小元關(guān)鍵字?jǐn)?shù)目2，則操作很簡(jiǎn)單赖钞，咱們只需要移動(dòng)K至原來(lái)H的位置腰素，移動(dòng)L至K的位置（也就是結(jié)點(diǎn)中刪除關(guān)鍵字后面的關(guān)鍵字向前移動(dòng)）
  

• 下一步，刪除T,因?yàn)門在中間結(jié)點(diǎn)中雪营，它有孩子弓千，且關(guān)鍵字?jǐn)?shù)目=2，所以需要向孩子借一個(gè)關(guān)鍵字W(一般借升序的下個(gè)關(guān)鍵字)献起，將W上移到T的位置洋访，然后將原包含W的孩子結(jié)點(diǎn)中的W進(jìn)行刪除，這里恰好刪除W后谴餐，該孩子結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目大于2姻政，無(wú)需進(jìn)行合并操作。
  

• 下一步刪除R岂嗓，R在葉子結(jié)點(diǎn)中,但是該結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目為2汁展，刪除導(dǎo)致只有1個(gè)關(guān)鍵字，已經(jīng)小于最小關(guān)鍵字?jǐn)?shù)目ceil(5/2)-1=2,而由前面我們已經(jīng)知道：如果其某個(gè)相鄰兄弟結(jié)點(diǎn)中比較豐滿（關(guān)鍵字個(gè)數(shù)大于ceil(5/2)-1=2）厌殉，則可以向父結(jié)點(diǎn)借一個(gè)關(guān)鍵字食绿，然后將最豐滿的相鄰兄弟結(jié)點(diǎn)中上移最后或最前一個(gè)關(guān)鍵字到父節(jié)點(diǎn)中（有沒有看到[紅黑樹]中左旋操作的影子?），在這個(gè)實(shí)例中公罕，右相鄰兄弟結(jié)點(diǎn)中比較豐滿（3個(gè)關(guān)鍵字大于2）炫欺，所以先向父節(jié)點(diǎn)借一個(gè)關(guān)鍵字W下移到該葉子結(jié)點(diǎn)中，代替原來(lái)S的位置熏兄，S前移品洛；然后X在相鄰右兄弟結(jié)點(diǎn)中上移到父結(jié)點(diǎn)中，最后在相鄰右兄弟結(jié)點(diǎn)中刪除X摩桶，后面關(guān)鍵字前移桥状。
  

• 最后一步刪除E， 刪除后會(huì)導(dǎo)致很多問(wèn)題硝清，因?yàn)镋所在的結(jié)點(diǎn)數(shù)目剛好達(dá)標(biāo)辅斟，剛好滿足最小關(guān)鍵字個(gè)數(shù)（ceil(5/2)-1=2）,而相鄰的兄弟結(jié)點(diǎn)也是同樣的情況，刪除一個(gè)關(guān)鍵字都不能滿足條件芦拿，所以需要該節(jié)點(diǎn)與某相鄰兄弟結(jié)點(diǎn)進(jìn)行合并操作士飒；首先移動(dòng)父結(jié)點(diǎn)中的關(guān)鍵字（該關(guān)鍵字在兩個(gè)需要合并的兩個(gè)結(jié)點(diǎn)關(guān)鍵字之間）下移到其子結(jié)點(diǎn)中查邢，然后將這兩個(gè)結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)。所以在該實(shí)例中酵幕，咱們首先將父節(jié)點(diǎn)中的關(guān)鍵字D下移到已經(jīng)刪除E而只有F的結(jié)點(diǎn)中扰藕，然后將含有D和F的結(jié)點(diǎn)和含有A,C的相鄰兄弟結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)。
  

  還沒完哦

• 也許你認(rèn)為這樣刪除操作已經(jīng)結(jié)束了芳撒，其實(shí)不然邓深，在看看上圖，對(duì)于這種特殊情況笔刹，你立即會(huì)發(fā)現(xiàn)父節(jié)點(diǎn)只包含一個(gè)關(guān)鍵字G芥备，沒達(dá)標(biāo)
  （因?yàn)榉歉?jié)點(diǎn)包括葉子結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)n必須滿足于2=<n<=4，而此處的n=1）這是不能夠接受的舌菜。
  如果這個(gè)問(wèn)題結(jié)點(diǎn)的相鄰兄弟比較豐滿萌壳，則可以向父結(jié)點(diǎn)借一個(gè)關(guān)鍵字。然后父親再向孩子借一個(gè)關(guān)鍵字日月。但是它的兄弟也很貧窮袱瓮。所以這時(shí)只能與兄弟結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)，而根結(jié)點(diǎn)中的唯一關(guān)鍵字M下移到子結(jié)點(diǎn)山孔，這樣懂讯，樹的高度減少一層。
  

  
  至此完成刪除操作台颠。
  補(bǔ)充一下最后一個(gè)關(guān)鍵字刪除的另外一種情況：也是5階B樹
  

• 刪除關(guān)鍵字C后發(fā)現(xiàn)只剩下一個(gè)關(guān)鍵字F所以我們打算去借褐望，這個(gè)借首先想到孩子，然后再說(shuō)父親刪除關(guān)鍵字C后D關(guān)鍵字上移到C的位置串前，但是出現(xiàn)上移關(guān)鍵字D后瘫里，只有一個(gè)關(guān)鍵字E的結(jié)點(diǎn)的情況。且它相鄰兄弟結(jié)點(diǎn)才剛脫貧（最少關(guān)鍵字個(gè)數(shù)為2）荡碾，不可能向父節(jié)點(diǎn)借關(guān)鍵字谨读，所以只能進(jìn)行合并操作，合并操作就要向父結(jié)點(diǎn)借一個(gè)元素坛吁，所以又把D借下來(lái)劳殖。于是這里將含有A,B的左兄弟結(jié)點(diǎn)，加上D關(guān)鍵字和含有E的結(jié)點(diǎn)進(jìn)行合并成一個(gè)結(jié)點(diǎn)拨脉。
  

  刪除C向孩子借D
  
  
  孩子合并

• 這樣又出現(xiàn)只含有一個(gè)關(guān)鍵字F結(jié)點(diǎn)的情況哆姻，這時(shí)，發(fā)現(xiàn)其相鄰的兄弟結(jié)點(diǎn)是豐滿的（關(guān)鍵字個(gè)數(shù)為3>最小關(guān)鍵字個(gè)數(shù)2）玫膀，這樣就可以想父結(jié)點(diǎn)借關(guān)鍵字矛缨，把父結(jié)點(diǎn)中的J下移到該結(jié)點(diǎn)中，相應(yīng)的如果結(jié)點(diǎn)中J后有元素則前移，然后相鄰兄弟結(jié)點(diǎn)中的第一個(gè)關(guān)鍵字（或者最后一個(gè)關(guān)鍵字）上移到父節(jié)點(diǎn)中箕昭，后面的關(guān)鍵字（或者前面的關(guān)鍵字）前移（或者后移）灵妨；注意含有K，L的結(jié)點(diǎn)以前依附在M的左邊落竹，現(xiàn)在變?yōu)橐栏皆贘的右邊泌霍。這樣每個(gè)結(jié)點(diǎn)都滿足B樹結(jié)構(gòu)性質(zhì)。

一顆m階的B+樹和m階的B樹的差異在于：

3階B+樹

1.非葉子結(jié)點(diǎn)的子樹指針與關(guān)鍵字個(gè)數(shù)相同筋量；
2.非葉子結(jié)點(diǎn)的子樹指針P[i]烹吵，指向關(guān)鍵字值屬于[K[i], K[i+1])的子樹（B-樹是開區(qū)間）
3.為所有葉子結(jié)點(diǎn)增加一個(gè)鏈指針碉熄。圖中Q是通過(guò)指針連在一起的桨武。
4.所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)。（5 8 9 10 15 18 20 26 ...等等）葉子結(jié)點(diǎn)相當(dāng)于是存儲(chǔ)（關(guān)鍵字）數(shù)據(jù)的數(shù)據(jù)層锈津；
5.B+樹只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在非葉子結(jié)點(diǎn)命中）
6.所有的非終端結(jié)點(diǎn)可以看成是索引部分呀酸，結(jié)點(diǎn)中的關(guān)鍵字是有其孩子指向的子樹中最大（或最小）關(guān)鍵字琼梆。比如第二層5 它的子樹為5 8 9 (而B 樹的非終節(jié)點(diǎn)也包含需要查找的有效信息)

B+樹在MyISAM索引實(shí)現(xiàn)

葉節(jié)點(diǎn)的data域存放的是數(shù)據(jù)記錄的地址

原理圖

B+樹在InnoDB索引實(shí)現(xiàn)

原理圖

• 第一個(gè)重大區(qū)別是InnoDB的數(shù)據(jù)文件本身就是索引文件茎杂。
  從上文知道错览，MyISAM索引文件和數(shù)據(jù)文件是分離的，索引文件僅保存數(shù)據(jù)記錄的地址煌往。
  而在InnoDB中倾哺，表數(shù)據(jù)文件本身就是按B+Tree組織的一個(gè)索引結(jié)構(gòu)，這棵樹的葉節(jié)點(diǎn)data域保存了完整的數(shù)據(jù)記錄刽脖。
  這個(gè)索引的key是數(shù)據(jù)表的主鍵羞海，因此InnoDB表數(shù)據(jù)文件本身就是主索引。

• 從示意圖曲管，可以看到葉節(jié)點(diǎn)包含了完整的數(shù)據(jù)記錄却邓。這種索引叫做聚集索引。因?yàn)镮nnoDB的數(shù)據(jù)文件本身要按主鍵聚集院水，所以InnoDB要求表必須有主鍵（MyISAM可以沒有）腊徙，如果沒有顯式指定，則MySQL系統(tǒng)會(huì)自動(dòng)選擇一個(gè)可以唯一標(biāo)識(shí)數(shù)據(jù)記錄的列作為主鍵檬某，如果不存在這種列撬腾，則MySQL自動(dòng)為InnoDB表生成一個(gè)隱含字段作為主鍵，這個(gè)字段長(zhǎng)度為6個(gè)字節(jié)橙喘，類型為長(zhǎng)整形时鸵。

• 第二個(gè)與MyISAM索引的不同是InnoDB的輔助索引data域存儲(chǔ)相應(yīng)記錄主鍵的值而不是地址。換句話說(shuō)，InnoDB的所有輔助索引都引用主鍵作為data域饰潜。例如
  

  
  聚集索引這種實(shí)現(xiàn)方式使得按主鍵的搜索十分高效初坠，但是輔助索引搜索需要檢索兩遍索引：首先檢索輔助索引獲得主鍵，然后用主鍵到主索引中檢索獲得記錄彭雾。

所以應(yīng)該注意的地方

• 為什么不建議使用過(guò)長(zhǎng)的字段作為主鍵碟刺？
  因?yàn)樗休o助索引都引用主索引，過(guò)長(zhǎng)的主索引會(huì)令輔助索引變得過(guò)大薯酝。
• 在InnoDB中不要用非單調(diào)的字段作為主鍵半沽。
  因?yàn)镮nnoDB數(shù)據(jù)文件本身是一顆B+Tree，非單調(diào)的主鍵會(huì)造成在插入新記錄時(shí)數(shù)據(jù)文件為了維持B+Tree的特性而頻繁的分裂調(diào)整吴菠，十分低效者填，而使用自增字段作為主鍵則是一個(gè)很好的選擇。

B樹JAVA代碼實(shí)現(xiàn)例子

七做葵、為什么說(shuō)B+樹比B樹更適合數(shù)據(jù)庫(kù)索引占哟？

1、 B+樹的磁盤讀寫代價(jià)更低：B+樹的內(nèi)部節(jié)點(diǎn)并沒有指向關(guān)鍵字具體信息的指針酿矢，因此其內(nèi)部節(jié)點(diǎn)相對(duì)B樹更小榨乎，如果把所有同一內(nèi)部節(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也越多瘫筐，一次性讀入內(nèi)存的需要查找的關(guān)鍵字也就越多蜜暑，相對(duì)IO讀寫次數(shù)就降低了。

2策肝、B+樹的查詢效率更加穩(wěn)定：由于非終結(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)肛捍，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路驳糯。所有關(guān)鍵字查詢的路徑長(zhǎng)度相同篇梭，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)。

3酝枢、由于B+樹的數(shù)據(jù)都存儲(chǔ)在葉子結(jié)點(diǎn)中恬偷，分支結(jié)點(diǎn)均為索引，方便掃庫(kù)帘睦，只需要掃一遍葉子結(jié)點(diǎn)即可袍患，但是B樹因?yàn)槠浞种ЫY(jié)點(diǎn)同樣存儲(chǔ)著數(shù)據(jù)，我們要找到具體的數(shù)據(jù)竣付，需要進(jìn)行一次中序遍歷按序來(lái)掃诡延，所以B+樹更加適合在區(qū)間查詢的情況，所以通常B+樹用于數(shù)據(jù)庫(kù)索引古胆。

B+樹比B樹更適合數(shù)據(jù)庫(kù)索引的原因主要有以下幾點(diǎn)：

B+樹的葉子節(jié)點(diǎn)存儲(chǔ)了所有的數(shù)據(jù)記錄肆良，而B樹的葉子節(jié)點(diǎn)只存儲(chǔ)部分?jǐn)?shù)據(jù)記錄筛璧，需要通過(guò)非葉子節(jié)點(diǎn)再查找。因此惹恃，在范圍查詢時(shí)夭谤，B+樹可以很快地找到需要的數(shù)據(jù)，而B樹需要多次IO操作巫糙，效率較低朗儒。

B+樹的葉子節(jié)點(diǎn)形成了一個(gè)有序鏈表，可以方便地進(jìn)行范圍查詢和遍歷参淹。而B樹的葉子節(jié)點(diǎn)不一定有序醉锄，需要進(jìn)行排序操作，難以實(shí)現(xiàn)高效的范圍查詢浙值。

B+樹的非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)記錄恳不，只存儲(chǔ)索引，因此可以存儲(chǔ)更多的索引信息亥鸠。這在數(shù)據(jù)庫(kù)中非常重要妆够，因?yàn)樗饕畔⒃蕉嗍独玻樵冃试礁摺?/p>

B+樹的非葉子節(jié)點(diǎn)比B樹的非葉子節(jié)點(diǎn)更少负蚊，因此在查詢時(shí)需要讀取的磁盤塊更少，查詢效率更高颓哮。

綜上所述家妆，B+樹的結(jié)構(gòu)和特點(diǎn)非常適合數(shù)據(jù)庫(kù)索引的需求，因此被廣泛應(yīng)用于數(shù)據(jù)庫(kù)中冕茅。

B+樹是一種多叉樹伤极，它的特點(diǎn)如下：

所有數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)中，葉子節(jié)點(diǎn)之間通過(guò)指針串聯(lián)起來(lái)形成一個(gè)鏈表姨伤，方便范圍查詢和遍歷哨坪。

非葉子節(jié)點(diǎn)只存儲(chǔ)索引信息，不存儲(chǔ)數(shù)據(jù)乍楚，可以存儲(chǔ)更多的索引信息当编，從而提高查詢效率。

非葉子節(jié)點(diǎn)比葉子節(jié)點(diǎn)少徒溪，因此在查詢時(shí)需要讀取的磁盤塊更少忿偷，查詢效率更高。

葉子節(jié)點(diǎn)之間通過(guò)指針串聯(lián)起來(lái)形成一個(gè)有序鏈表臊泌，因此可以方便地進(jìn)行范圍查詢和遍歷鲤桥。

所有葉子節(jié)點(diǎn)的深度相同，因此查詢效率穩(wěn)定渠概，不會(huì)出現(xiàn)數(shù)據(jù)分布不均導(dǎo)致查詢效率不穩(wěn)定的情況茶凳。

插入和刪除操作需要更新索引和葉子節(jié)點(diǎn)，因此比B樹的插入和刪除操作復(fù)雜，但是由于非葉子節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)贮喧，因此更新的數(shù)據(jù)量比B樹少顷牌，更新效率高。

綜上所述塞淹，B+樹的結(jié)構(gòu)和特點(diǎn)非常適合數(shù)據(jù)庫(kù)索引的需求窟蓝，因此被廣泛應(yīng)用于數(shù)據(jù)庫(kù)中。

B+樹和紅黑樹都是常用的平衡樹饱普，它們的主要區(qū)別在于應(yīng)用場(chǎng)景和特點(diǎn)运挫。

B+樹適用于在磁盤中存儲(chǔ)大量數(shù)據(jù)并進(jìn)行范圍查詢的情況，因?yàn)樗乃袛?shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)中套耕，并且葉子節(jié)點(diǎn)之間通過(guò)指針串聯(lián)起來(lái)形成一個(gè)有序鏈表谁帕，因此可以方便地進(jìn)行范圍查詢和遍歷。B+樹的非葉子節(jié)點(diǎn)只存儲(chǔ)索引信息冯袍，不存儲(chǔ)數(shù)據(jù)匈挖，可以存儲(chǔ)更多的索引信息，從而提高查詢效率康愤。但是儡循，由于B+樹的葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)不存儲(chǔ)指針，因此每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)量比較大征冷，在內(nèi)存中的效率不如紅黑樹择膝。

紅黑樹適用于在內(nèi)存中進(jìn)行快速查找、插入和刪除的情況检激，因?yàn)樗幕静僮鲿r(shí)間復(fù)雜度均為O(log N)肴捉，并且每個(gè)節(jié)點(diǎn)只需要存儲(chǔ)一個(gè)指針和一個(gè)顏色標(biāo)記，占用空間較小叔收。紅黑樹的特點(diǎn)是具有較好的平衡性齿穗，可以保證樹的高度始終為O(log N)，因此查詢饺律、插入窃页、刪除等操作的效率比較穩(wěn)定。但是蓝晒，由于紅黑樹的數(shù)據(jù)存儲(chǔ)比較分散腮出，因此不適合在磁盤中存儲(chǔ)數(shù)據(jù)，會(huì)導(dǎo)致磁盤的頻繁讀寫芝薇，影響效率胚嘲。

綜上所述，B+樹和紅黑樹都有各自適用的場(chǎng)景和特點(diǎn)洛二，需要根據(jù)具體情況選擇合適的數(shù)據(jù)結(jié)構(gòu)馋劈。
文章參考：
http://lday.me/2018/02/21/0020_b_tree_summary/
https://blog.csdn.net/endlu/article/details/51720299
http://blog.codinglabs.org/articles/theory-of-mysql-index.html