一. B樹
1.1 B樹的定義
B樹也稱B-樹,它是一顆多路平衡查找樹眯停。我們描述一顆B樹時需要指定它的階數临扮，階數表示了一個結點最多有多少個孩子結點诫惭，一般用字母m表示階數窃祝。當m取2時，就是我們常見的二叉搜索樹众旗。
一顆m階的B樹定義如下：
- 每個結點最多有m-1個關鍵字罢杉。
- 根結點最少可以只有1個關鍵字。
- 非根結點至少有Math.ceil(m/2)-1個關鍵字贡歧。
- 每個結點中的關鍵字都按照從小到大的順序排列滩租，每個關鍵字的左子樹中的所有關鍵字都小于它，而右子樹中的所有關鍵字都大于它利朵。
- 所有葉子結點都位于同一層律想，或者說根結點到每個葉子結點的長度都相同
上圖是一顆階數為4的B樹。在實際應用中的B樹的階數m都非常大（通常大于100）绍弟，所以即使存儲大量的數據技即，B樹的高度仍然比較小。每個結點中存儲了關鍵字（key）和關鍵字對應的數據（data）樟遣，以及孩子結點的指針而叼。我們將一個key和其對應的data稱為一個記錄。但為了方便描述豹悬，除非特別說明葵陵，后續(xù)文中就用key來代替（key, value）鍵值對這個整體。在數據庫中我們將B樹（和B+樹）作為索引結構瞻佛，可以加快查詢速速辖佣，此時B樹中的key就表示鍵雏门，而data表示了這個鍵對應的條目在硬盤上的邏輯地址璃岳。
1.2 B樹的插入操作
插入操作是指插入一條記錄趁冈，即（key, value）的鍵值對。如果B樹中已存在需要插入的鍵值對响迂，則用需要插入的value替換舊的value。若B樹不存在這個key,則一定是在葉子結點中進行插入操作细疚。
- 根據要插入的key的值蔗彤，找到葉子結點并插入川梅。
- 判斷當前結點key的個數是否小于等于m-1，若滿足則結束然遏，否則進行第3步贫途。
- 以結點中間的key為中心分裂成左右兩部分，然后將這個中間的key插入到父結點中待侵，這個key的左子樹指向分裂后的左半部分丢早，這個key的右子支指向分裂后的右半部分，然后將當前結點指向父結點秧倾，繼續(xù)進行第3步怨酝。
下面以5階B樹為例，介紹B樹的插入操作那先，在5階B樹中农猬，結點最多有4個key,最少有2個key
a.在空樹中插入39
根結點此時有4個key
c. 繼續(xù)插入53
插入后超過了最大允許的關鍵字個數4售淡，所以以key值為41為中心進行分裂斤葱，結果如下圖所示，分裂后當前結點指針指向父結點揖闸，滿足B樹條件揍堕，插入操作結束。當階數m為偶數時汤纸，需要分裂時就不存在排序恰好在中間的key鹤啡，那么我們選擇中間位置的前一個key或中間位置的后一個key為中心進行分裂即可。
d. 依次插入13蹲嚣，21递瑰，40，同樣會造成分裂隙畜，結果如下圖所示抖部。
e. 依次插入30，27, 33 议惰；36慎颗，35，34 言询；24俯萎，29，結果如下圖所示运杭。
f. 插入key值為26的記錄夫啊，插入后的結果如下圖所示。
當前結點需要以27為中心分裂辆憔，并向父結點進位27撇眯，然后當前結點指向父結點报嵌，結果如下圖所示。
進位后導致當前結點（即根結點）也需要分裂熊榛，分裂的結果如下圖所示锚国。
分裂后當前結點指向新的根，此時無需調整玄坦。
g. 最后再依次插入key為17,28,29,31,32的記錄血筑，結果如下圖所示。
在實現B樹的代碼中煎楣，為了使代碼編寫更加容易豺总，我們可以將結點中存儲記錄的數組長度定義為m而非m-1，這樣方便底層的結點由于分裂向上層插入一個記錄時转质，上層有多余的位置存儲這個記錄园欣。同時，每個結點還可以存儲它的父結點的引用休蟹，這樣就不必編寫遞歸程序沸枯。
一般來說，對于確定的m和確定類型的記錄赂弓，結點大小是固定的绑榴，無論它實際存儲了多少個記錄。但是分配固定結點大小的方法會存在浪費的情況盈魁，比如key為28,29所在的結點翔怎，還有2個key的位置沒有使用，但是已經不可能繼續(xù)在插入任何值了杨耙，因為這個結點的前序key是27,后繼key是30,所有整數值都用完了赤套。所以如果記錄先按key的大小排好序，再插入到B樹中珊膜，結點的使用率就會很低容握，最差情況下使用率僅為50%。
1.3 B樹的刪除操作
刪除操作是指车柠，根據key刪除記錄剔氏，如果B樹中的記錄中不存對應key的記錄，則刪除失敗竹祷。
如果當前需要刪除的key位于非葉子結點上谈跛，則用后繼key（這里的后繼key均指后繼記錄的意思）覆蓋要刪除的key，然后在后繼key所在的子支中刪除該后繼key塑陵。此時后繼key一定位于葉子結點上感憾，這個過程和二叉搜索樹刪除結點的方式類似。刪除這個記錄后執(zhí)行第2步
該結點key個數大于等于Math.ceil(m/2)-1猿妈，結束刪除操作吹菱，否則執(zhí)行第3步巍虫。
如果兄弟結點key個數大于Math.ceil(m/2)-1彭则，則父結點中的key下移到該結點鳍刷，兄弟結點中的一個key上移，刪除操作結束俯抖。
否則输瓜，將父結點中的key下移與當前結點及它的兄弟結點中的key合并，形成一個新的結點芬萍。原父結點中的key的兩個孩子指針就變成了一個孩子指針尤揣，指向這個新結點。然后當前結點的指針指向父結點柬祠，重復上第2步北戏。
有些結點它可能即有左兄弟，又有右兄弟漫蛔，那么我們任意選擇一個兄弟結點進行操作即可嗜愈。
下面以5階B樹為例，介紹B樹的刪除操作莽龟，5階B樹中蠕嫁，結點最多有4個key,最少有2個key
a. 原始狀態(tài)
b. 在上面的B樹中刪除21，刪除后結點中的關鍵字個數仍然大于等2毯盈，所以刪除結束剃毒。
c. 在上述情況下接著刪除27。從上圖可知27位于非葉子結點中搂赋，所以用27的后繼替換它赘阀。從圖中可以看出，27的后繼為28脑奠，我們用28替換27基公，然后在28（原27）的右孩子結點中刪除28。刪除后的結果如下圖所示捺信。
刪除后發(fā)現酌媒，當前葉子結點的記錄的個數小于2，而它的兄弟結點中有3個記錄（當前結點還有一個右兄弟迄靠，選擇右兄弟就會出現合并結點的情況秒咨，不論選哪一個都行，只是最后B樹的形態(tài)會不一樣而已）掌挚，我們可以從兄弟結點中借取一個key雨席。所以父結點中的28下移，兄弟結點中的26上移,刪除結束吠式。結果如下圖所示陡厘。
d. 在上述情況下接著32抽米，結果如下圖。
當刪除后糙置，當前結點中只key云茸，而兄弟結點中也僅有2個key。所以只能讓父結點中的30下移和這個兩個孩子結點中的key合并谤饭，成為一個新的結點标捺，當前結點的指針指向父結點。結果如下圖所示揉抵。
當前結點key的個數滿足條件亡容，故刪除結束。
e. 上述情況下冤今，我們接著刪除key為40的記錄闺兢，刪除后結果如下圖所示。
同理戏罢，當前結點的記錄數小于2屋谭，兄弟結點中沒有多余key，所以父結點中的key下移帖汞，和兄弟（這里我們選擇左兄弟戴而，選擇右兄弟也可以）結點合并，合并后的指向當前結點的指針就指向了父結點翩蘸。
同理所意，對于當前結點而言只能繼續(xù)合并了，最后結果如下所示催首。
合并后結點當前結點滿足條件扶踊，刪除結束。
2.B+樹
2.1 B+樹的定義
各種資料上B+樹的定義各有不同郎任，一種定義方式是關鍵字個數和孩子結點個數相同秧耗。這里我們采取維基百科上所定義的方式，即關鍵字個數比孩子結點個數小1舶治，這種方式是和B樹基本等價的分井。上圖就是一顆階數為4的B+樹。
除此之外B+樹還有以下的要求霉猛。
B+樹包含2種類型的結點：內部結點（也稱索引結點）和葉子結點尺锚。根結點本身即可以是內部結點，也可以是葉子結點惜浅。根結點的關鍵字個數最少可以只有1個瘫辩。
B+樹與B樹最大的不同是內部結點不保存數據，只用于索引，所有數據（或者說記錄）都保存在葉子結點中伐厌。
m階B+樹表示了內部結點最多有m-1個關鍵字（或者說內部結點最多有m個子樹）承绸，階數m同時限制了葉子結點最多存儲m-1個記錄。
內部結點中的key都按照從小到大的順序排列挣轨，對于內部結點中的一個key军熏，左樹中的所有key都小于它，右子樹中的key都大于等于它刃唐。葉子結點中的記錄也按照key的大小排列羞迷。
每個葉子結點都存有相鄰葉子結點的指針界轩，葉子結點本身依關鍵字的大小自小而大順序鏈接画饥。
2.2 B+樹的插入操作
若為空樹，創(chuàng)建一個葉子結點浊猾，然后將記錄插入其中抖甘，此時這個葉子結點也是根結點，插入操作結束葫慎。
針對葉子類型結點：根據key值找到葉子結點衔彻，向這個葉子結點插入記錄。插入后偷办，若當前結點key的個數小于等于m-1艰额，則插入結束。否則將這個葉子結點分裂成左右兩個葉子結點椒涯，左葉子結點包含前m/2個記錄柄沮，右結點包含剩下的記錄，將第m/2+1個記錄的key進位到父結點中（父結點一定是索引類型結點）废岂，進位到父結點的key左孩子指針向左結點,右孩子指針向右結點祖搓。將當前結點的指針指向父結點，然后執(zhí)行第3步湖苞。
針對索引類型結點：若當前結點key的個數小于等于m-1拯欧，則插入結束。否則财骨，將這個索引類型結點分裂成兩個索引結點镐作，左索引結點包含前(m-1)/2個key，右結點包含m-(m-1)/2個key隆箩，將第m/2個key進位到父結點中该贾，進位到父結點的key左孩子指向左結點, 進位到父結點的key右孩子指向右結點。將當前結點的指針指向父結點摘仅，然后重復第3步靶庙。
下面是一顆5階B樹的插入過程，5階B數的結點最少2個key，最多4個key六荒。
a. 空樹中插入5
b. 依次插入8护姆，10，15
c. 插入16
插入16后超過了關鍵字的個數限制掏击，所以要進行分裂卵皂。在葉子結點分裂時，分裂出來的左結點2個記錄砚亭，右邊3個記錄灯变，中間key成為索引結點中的key，分裂后當前結點指向了父結點（根結點）捅膘。結果如下圖所示添祸。
當然我們還有另一種分裂方式，給左結點3個記錄寻仗，右結點2個記錄刃泌，此時索引結點中的key就變?yōu)?5。
d .插入17
e. 插入18署尤，插入后如下圖所示
當前結點的關鍵字個數大于5耙替，進行分裂。分裂成兩個結點曹体，左結點2個記錄俗扇，右結點3個記錄，關鍵字16進位到父結點（索引類型）中箕别，將當前結點的指針指向父結點铜幽。
當前結點的關鍵字個數滿足條件，插入結束究孕。
f. 插入若干數據后
g. 在上圖中插入7啥酱，結果如下圖所示
當前結點的關鍵字個數超過4，需要分裂厨诸。左結點2個記錄镶殷，右結點3個記錄。分裂后關鍵字7進入到父結點中微酬，將當前結點的指針指向父結點绘趋，結果如下圖所示。
當前結點的關鍵字個數超過4颗管，需要繼續(xù)分裂陷遮。左結點2個關鍵字，右結點2個關鍵字垦江，關鍵字16進入到父結點中帽馋，將當前結點指向父結點，結果如下圖所示。
當前結點的關鍵字個數滿足條件绽族，插入結束姨涡。
2.3 B+樹的刪除操作
如果葉子結點中沒有相應的key，則刪除失敗吧慢。否則執(zhí)行下面的步驟
刪除葉子結點中對應的key涛漂。刪除后若結點的key的個數大于等于Math.ceil(m-1)/2 – 1，刪除操作結束,否則執(zhí)行第2步检诗。
若兄弟結點key有富余（大于Math.ceil(m-1)/2 – 1）匈仗，向兄弟結點借一個記錄，同時用借到的key替換父結（指當前結點和兄弟結點共同的父結點）點中的key逢慌，刪除結束悠轩。否則執(zhí)行第3步。
若兄弟結點中沒有富余的key,則當前結點和兄弟結點合并成一個新的葉子結點涕癣，并刪除父結點中的key（父結點中的這個key兩邊的孩子指針就變成了一個指針哗蜈，正好指向這個新的葉子結點），將當前結點指向父結點（必為索引結點）坠韩，執(zhí)行第4步（第4步以后的操作和B樹就完全一樣了，主要是為了更新索引結點）炼列。
若索引結點的key的個數大于等于Math.ceil(m-1)/2 – 1只搁，則刪除操作結束。否則執(zhí)行第5步
若兄弟結點有富余俭尖，父結點key下移氢惋，兄弟結點key上移，刪除結束稽犁。否則執(zhí)行第6步
當前結點和兄弟結點及父結點下移key合并成一個新的結點焰望。將當前結點指向父結點，重復第4步已亥。
注意熊赖，通過B+樹的刪除操作后，索引結點中存在的key虑椎，不一定在葉子結點中存在對應的記錄震鹉。
下面是一顆5階B樹的刪除過程，5階B數的結點最少2個key捆姜，最多4個key传趾。
a.初始狀態(tài)
b. 刪除22,刪除后結果如下圖
刪除后葉子結點中key的個數大于等于2，刪除結束
c.刪除15泥技，刪除后的結果如下圖所示
刪除后當前結點只有一個key,不滿足條件浆兰，而兄弟結點有三個key，可以從兄弟結點借一個關鍵字為9的記錄,同時更新將父結點中的關鍵字由10也變?yōu)?，刪除結束簸呈。
d. 刪除7宽涌，刪除后的結果如下圖所示
當前結點關鍵字個數小于2，（左）兄弟結點中的也沒有富余的關鍵字（當前結點還有個右兄弟蝶棋，不過選擇任意一個進行分析就可以了卸亮，這里我們選擇了左邊的），所以當前結點和兄弟結點合并玩裙，并刪除父結點中的key兼贸，當前結點指向父結點。
此時當前結點的關鍵字個數小于2吃溅，兄弟結點的關鍵字也沒有富余溶诞，所以父結點中的關鍵字下移，和兩個孩子結點合并决侈，結果如下圖所示螺垢。
