由于數(shù)據(jù)結(jié)構(gòu)的東西涉及到許多的圖片啊蝉绷，流程啊什么的田度。所以會參考許多網(wǎng)上存在的資料加以總結(jié)默怨，我會將參考鏈接放在文章后面幕庐。
B樹
B樹基本概念
網(wǎng)上的許多資料在講述數(shù)據(jù)結(jié)構(gòu)之前都會講相關(guān)的一些符合久锥、說明以及特性什么的都交代清除。在閱讀網(wǎng)上資料的時候我發(fā)現(xiàn)許多知識點說的都非常的官方异剥，簡單來說就是賊難看懂瑟由。所以我在記錄的時候會將那些難懂的官方內(nèi)容用通俗的話解釋一下，方便我自己的理解届吁。
首先來說错妖，為什么我們要引入B樹呢？有二叉樹不是很好嗎疚沐？
存在即合理暂氯。所以還是有存在的理由的。B樹的時間復(fù)雜度與二叉樹一樣亮蛔，均為O(logN)痴施。然而Ｂ樹出現(xiàn)是因為磁盤ＩＯ。ＩＯ操作的效率很低究流，那么辣吃，當(dāng)在大量數(shù)據(jù)存儲中，查詢時我們不能一下子將所有數(shù)據(jù)加載到內(nèi)存中芬探，只能逐一加載磁盤頁神得，每個磁盤頁對應(yīng)樹的節(jié)點。造成大量磁盤ＩＯ操作（最壞情況下為樹的高度）偷仿。平衡二叉樹由于樹深度過大而造成磁盤IO讀寫過于頻繁哩簿，進而導(dǎo)致效率低下宵蕉。
所以，我們?yōu)榱藴p少磁盤ＩＯ的次數(shù)节榜，就你必須降低樹的深度羡玛，將“瘦高”的樹變得“矮胖”。
PS：這里我找到了一個講述很好的二叉樹與B樹的比較鏈接宗苍。大家可以閱讀以下稼稿。
http://m.elecfans.com/article/662237.html
比如下面的圖片：
二叉樹以2為最大基準(zhǔn)向下延伸，而B樹則沒有標(biāo)準(zhǔn)讳窟，所以它可以變得矮矮胖胖的让歼。
B 樹又叫平衡多路查找樹。一棵m階的B 樹 (m叉樹)的特性如下：
B樹中所有節(jié)點的孩子節(jié)點數(shù)中的最大值稱為B樹的階挪钓，記為M（重點）
樹中的每個節(jié)點至多有M棵子樹 ---即：如果定了M是越，則這個B樹中任何節(jié)點的子節(jié)點數(shù)量都不能超過M
若根節(jié)點不是終端節(jié)點，則至少有兩棵子樹
除根節(jié)點和葉節(jié)點外碌上，所有點至少有m/2棵子樹（上溢）
所有的葉子結(jié)點都位于同一層。（比如上面的圖片中我沒有了11 13 15浦徊，那么我12就沒有存在的意義了馏予，就需要調(diào)整整個樹的布局）
下面是我在百科中找到的性質(zhì)：
B樹的查找操作
查找操作的理解不難。我直接用幾張圖來闡述一下盔性。
在B樹上進行查找和二叉樹的查找很相似霞丧，二叉樹是每個節(jié)點上有一個關(guān)鍵子和兩個分支。B樹上每個節(jié)點有K個關(guān)鍵字和K+1個分支冕香。二叉樹的查找只考慮向左還是向右走蛹尝，而B樹中需要由多個分支決定。
B樹的查找分兩步悉尾，首先查找節(jié)點突那，由于B樹通常是在磁盤上存儲的所以這步需要進行磁盤IO操作。第二步是查找關(guān)鍵字构眯，當(dāng)找到某個節(jié)點后將該節(jié)點讀入內(nèi)存中然后通過順序或者折半查找來查找關(guān)鍵字愕难。若沒有找到關(guān)鍵字，則需要判斷大小來找到合適的分支繼續(xù)查找惫霸。
如下有一個3階的B樹猫缭，觀察查找元素21的過程：
第一次磁盤IO：
第二次磁盤IO：
這里有一次內(nèi)存比對：分別跟3與12比對。
第三次磁盤IO:
這里有一次內(nèi)存比對壹店，分別跟14與21比對
PS：此處參考：http://m.elecfans.com/article/662237.html
由于B樹相對于二叉樹來說矮胖了許多猜丹，所以它所涉及的IO操作也相對少了許多。不過根據(jù)我們上面的分析硅卢，其在查找數(shù)據(jù)的時候并沒有減少比較次數(shù)射窒。但是我們知道藏杖，我們在比較數(shù)據(jù)的時候是在內(nèi)存中進行的，所以相對來說時間上會更加迅速轮洋，幾乎可以忽略制市。
而相同數(shù)量的key在B樹中生成的節(jié)點要遠遠少于二叉樹中的節(jié)點，相差的節(jié)點數(shù)量就等同于磁盤IO的次數(shù)弊予。這樣到達一定數(shù)量后祥楣，性能的差異就顯現(xiàn)出來了。
這里先放下一個問題汉柒，既然我的介數(shù)M是自行設(shè)定的误褪。那么我們的M如果很小那么會變成類似于二叉樹，那么當(dāng)M很大的時候呢碾褂？
我認為當(dāng)M很大會導(dǎo)致比較次數(shù)過多兽间，在當(dāng)前磁盤空間能容納的范圍下也有可能導(dǎo)致比較次數(shù)過多而導(dǎo)致效率降低的情況。
B樹的插入
對高度為ｋ的m階B樹正塌，新結(jié)點一般是插在葉子層嘀略。通過檢索可以確定關(guān)鍵碼應(yīng)插入的結(jié)點位置。然后分兩種情況討論：
1乓诽、 若該結(jié)點中關(guān)鍵碼個數(shù)小于m-1帜羊，則直接插入即可。
2鸠天、 若該結(jié)點中關(guān)鍵碼個數(shù)等于m-1讼育，則將引起結(jié)點的分裂。以中間關(guān)鍵碼為界將結(jié)點一分為二稠集，產(chǎn)生一個新結(jié)點奶段，并把中間關(guān)鍵碼插入到父結(jié)點(ｋ-1層)中
重復(fù)上述工作，最壞情況一直分裂到根結(jié)點剥纷，建立一個新的根結(jié)點痹籍，整個B樹增加一層。
例如：在下面的B樹中插入key：4
第一步：檢索key插入的節(jié)點位置如上圖所示筷畦，在3,5之間词裤；
第二步：判斷節(jié)點中的關(guān)鍵碼個數(shù)：
節(jié)點3，5已經(jīng)是兩元素節(jié)點鳖宾，無法再增加（已經(jīng) = 3-1）吼砂。父親節(jié)點 2， 6 也是兩元素節(jié)點鼎文，也無法再增加渔肩。根節(jié)點9是單元素節(jié)點，可以升級為兩元素節(jié)點拇惋。周偎；
第三步：結(jié)點分裂：
拆分節(jié)點3抹剩，5與節(jié)點2，6蓉坎，讓根節(jié)點9升級為兩元素節(jié)點4澳眷，9。節(jié)點6獨立為根節(jié)點的第二個孩子蛉艾。
最終結(jié)果如下圖：雖然插入比較麻煩钳踊，但是這也能確保Ｂ樹是一個自平衡的樹。
另一個例子：
當(dāng)插入一個關(guān)鍵字60后,節(jié)點內(nèi)的關(guān)鍵字個數(shù)超過出了m-1=2勿侯，此時必須進行節(jié)點分裂拓瞪，分裂的過程如上圖所示。
資源來源參考于：https://blog.csdn.net/z_ryan/article/details/79685072
B樹的刪除
B樹的刪除操作相對較為復(fù)雜助琐，我看許多文檔解釋的都十分官方且難懂祭埂。所以我準(zhǔn)備用更為簡單的圖來對刪除操作的不同情況進行解釋。希望大家看完后能夠理解兵钮。
- 首先蛆橡，根據(jù)key刪除記錄，如果B樹中的記錄中不存對應(yīng)key的記錄掘譬，則刪除失敗航罗。
之后我們需要分一下四種情況來考慮。（下面的例子中以5階B樹為例屁药，介紹B樹的刪除操作，5階B樹中柏锄，結(jié)點最多有4個key,最少有2個key）對于刪除key的過程來說酿箭，對于葉結(jié)點和非葉結(jié)點其實差別在一個地方，那就是如果當(dāng)前我們操作的是非葉結(jié)點趾娃，那么后繼key（這里的后繼key指最接近當(dāng)前刪除值缭嫡，且大于當(dāng)前刪除值的值）覆蓋要刪除的key，然后在后繼key所在的子支中刪除該后繼key抬闷。
例如：
a）原始狀態(tài)
b）在上述情況下接著刪除27妇蛀。從上圖可知27位于非葉子結(jié)點中，所以用27的后繼替換它笤成。從圖中可以看出评架，27的后繼為28，我們用28替換27炕泳，然后在28（原27）的右孩子結(jié)點中刪除28纵诞。刪除后的結(jié)果如下圖所示。
之后我們就把非葉結(jié)點的情況轉(zhuǎn)換為了處理葉結(jié)點的情況培遵。
此時我們就要分一下幾種情況來考慮如何處理葉結(jié)點浙芙。
- ①該結(jié)點key個數(shù)>=Ceil(m/2)-1（上界登刺，例如m=5，那么最后為2）嗡呼，結(jié)束刪除操作纸俭，否則執(zhí)行下一步。
- ②該結(jié)點key的個數(shù)<Ceil(m/2)-1南窗，且兄弟結(jié)點key個數(shù)>Ceil(m/2)-1揍很，則父結(jié)點中的key下移到該結(jié)點，兄弟結(jié)點中的一個key上移矾瘾，刪除操作結(jié)束女轿。
a）緊接上面的例子。
b）刪除后發(fā)現(xiàn)壕翩，當(dāng)前葉子結(jié)點的記錄的個數(shù)小于2（<Ceil(m/2)-1）蛉迹，而它的兄弟結(jié)點中有3個記錄（>Ceil(m/2)-1 當(dāng)前結(jié)點還有一個右兄弟，選擇右兄弟就會出現(xiàn)合并結(jié)點的情況放妈，不論選哪一個都行北救，只是最后B樹的形態(tài)會不一樣而已），我們可以從兄弟結(jié)點中借取一個key芜抒。所以父結(jié)點中的28下移珍策，兄弟結(jié)點中的26上移，刪除結(jié)束宅倒。結(jié)果如下圖所示攘宙。
- ③如果該結(jié)點key的個數(shù)<Ceil(m/2)-1，且兄弟結(jié)點key個數(shù)<=Ceil(m/2)-1拐迁，那么將父結(jié)點中的key下移與當(dāng)前結(jié)點及它的兄弟結(jié)點中的key合并蹭劈，形成一個新的結(jié)點。原父結(jié)點中的key的兩個孩子指針就變成了一個孩子指針线召，指向這個新結(jié)點铺韧。
例如：
a）原圖為
b）在上述情況下刪除32。
當(dāng)刪除后缓淹，當(dāng)前結(jié)點中只有一個key（個數(shù)<Ceil(m/2)-1）哈打，而兄弟結(jié)點中也僅有2個key（<=Ceil(m/2)-1）。所以只能讓父結(jié)點中的30下移和這個兩個孩子結(jié)點中的key合并讯壶，成為一個新的結(jié)點料仗，當(dāng)前結(jié)點的指針指向父結(jié)點。結(jié)果如下圖所示鹏溯。
由于我們移動了父結(jié)點中的數(shù)據(jù)罢维，所以其key值減少，那么我們就要對當(dāng)前父結(jié)點進行考慮。
下面看一個考慮父結(jié)點的例子肺孵。
a）原圖
b）上述情況下匀借，我們接著刪除key為40的記錄，刪除后結(jié)果如下圖所示平窘。
同理吓肋，當(dāng)前結(jié)點的記錄數(shù)小于2（根據(jù)情況③），兄弟結(jié)點中沒有多余key瑰艘，所以父結(jié)點中的key下移是鬼，和兄弟（這里我們選擇左兄弟，選擇右兄弟也可以）結(jié)點合并紫新，合并后的指向當(dāng)前結(jié)點的指針就指向了父結(jié)點均蜜。
同理，對于當(dāng)前結(jié)點而言只能繼續(xù)合并了芒率，最后結(jié)果如下所示囤耳。（根據(jù)情況③）
合并后結(jié)點當(dāng)前結(jié)點滿足條件，刪除結(jié)束偶芍。
此處參考了部分：https://www.cnblogs.com/nullzx/p/8729425.html的內(nèi)容充择。
