前言
首先，為什麼要總結B樹、B+樹的知識呢？最近在學習資料庫索引調優相關知識，資料庫系統普遍采用B-/+Tree作為索引結構（例如mysql的InnoDB引擎使用的B+樹），了解不透徹B樹，則無法了解資料庫的索引機制；接下來将用最簡潔直白的内容來了解B樹、B+樹的資料結構
另外，B-樹，即為B樹。因為B樹的原英文名稱為B-tree，而國内很多人喜歡把B-tree譯作B-樹，其實，這是個非常不好的直譯，很容易讓人産生誤解。如人們可能會以為B-樹是一種樹，而B樹又是一種樹。而事實上是，B-tree就是指的B樹，目前了解B的意思為平衡
B樹的出現是為了彌合不同的存儲級别之間的通路速度上的巨大差異，實作高效的 I/O。平衡二叉樹的查找效率是非常高的，并可以通過降低樹的深度來提高查找的效率。但是當資料量非常大，樹的存儲的元素數量是有限的，這樣會導緻二叉查找樹結構由于樹的深度過大而造成磁盤I/O讀寫過于頻繁，進而導緻查詢效率低下。另外資料量過大會導緻記憶體空間不夠容納平衡二叉樹所有結點的情況。B樹是解決這個問題的很好的結構
概念
首先，B樹不要和二叉樹混淆，在計算機科學中，B樹是一種自平衡樹資料結構，它維護有序資料并允許以對數時間進行搜尋，順序通路，插入和删除。B樹是二叉搜尋樹的一般化，因為節點可以有兩個以上的子節點。[1]與其他自平衡二進制搜尋樹不同，B樹非常适合讀取和寫入相對較大的資料塊（如CD光牒）的存儲系統。它通常用于資料庫和檔案系統。
定義
B樹是一種平衡的多分樹，通常我們說m階的B樹，它必須滿足如下條件：
每個節點最多隻有m個子節點。
每個非葉子節點（除了根）具有至少⌈ m/2⌉子節點。
如果根不是葉節點，則根至少有兩個子節點。
具有k個子節點的非葉節點包含k -1個鍵。
所有葉子都出現在同一水準，沒有任何資訊（高度一緻）。
第一次看到這個定義的時候，在想什麼鬼？。。。。什麼是階？子節點、飛葉子點、根？？？啥意思！少年别慌。。。
什麼是B樹的階 ？
B樹中一個節點的子節點數目的最大值，用m表示，假如最大值為10，則為10階，如圖
所有節點中，節點【13,16,19】擁有的子節點數目最多，四個子節點（灰色節點），是以可以定義上面的圖檔為4階B樹，現在懂什麼是階了吧
什麼是根節點 ？
節點【10】即為根節點，特征：根節點擁有的子節點數量的上限和内部節點相同，如果根節點不是樹中唯一節點的話，至少有倆個子節點（不然就變成單支了）。在m階B樹中（根節點非樹中唯一節點），那麼有關系式2<= M <=m，M為子節點數量；包含的元素數量 1<= K <=m-1,K為元素數量。
什麼是内部節點 ？
節點【13,16,19】、節點【3,6】都為内部節點，特征：内部節點是除葉子節點和根節點之外的所有節點，擁有父節點和子節點。假定m階B樹的内部節點的子節點數量為M，則一定要符合（m/2）<= M <=m關系式，包含元素數量M-1；包含的元素數量 （m/2）-1<= K <=m-1,K為元素數量。m/2向上取整。
什麼是葉子節點？
節點【1,2】、節點【11,12】等最後一層都為葉子節點，葉子節點對元素的數量有相同的限制，但是沒有子節點，也沒有指向子節點的指針。特征：在m階B樹中葉子節點的元素符合（m/2）-1<= K <=m-1。
好了，概念已經清楚，不用着急背公式， 接着往下看
插入
針對m階高度h的B樹，插入一個元素時，首先在B樹中是否存在，如果不存在，即在葉子結點處結束，然後在葉子結點中插入該新的元素。
若該節點元素個數小于m-1，直接插入；
若該節點元素個數等于m-1，引起節點分裂；以該節點中間元素為分界，取中間元素（偶數個數，中間兩個随機選取）插入到父節點中；
重複上面動作，直到所有節點符合B樹的規則；最壞的情況一直分裂到根節點，生成新的根節點，高度增加1；
上面三段話為插入動作的核心，接下來以5階B樹為例，詳細講解插入的動作；
5階B樹關鍵點:
2<=根節點子節點個數<=5
3<=内節點子節點個數<=5
1<=根節點元素個數<=4
2<=非根節點元素個數<=4
插入8
圖（1）插入元素【8】後變為圖（2），此時根節點元素個數為5，不符合 1<=根節點元素個數<=4，進行分裂（真實情況是先分裂，然後插入元素，這裡是為了直覺而先插入元素，下面的操作都一樣，不再贅述），取節點中間元素【7】，加入到父節點，左右分裂為2個節點，如圖（3）
接着插入元素【5】，【11】，【17】時，不需要任何分裂操作，如圖（4）
插入元素【13】
節點元素超出最大數量，進行分裂，提取中間元素【13】，插入到父節點當中，如圖（6）
接着插入元素【6】，【12】，【20】，【23】時，不需要任何分裂操作，如圖（7）
插入【26】時，最右的葉子結點空間滿了，需要進行分裂操作，中間元素【20】上移到父節點中，注意通過上移中間元素，樹最終還是保持平衡，分裂結果的結點存在2個關鍵字元素。
插入【4】時，導緻最左邊的葉子結點被分裂，【4】恰好也是中間元素，上移到父節點中，然後元素【16】,【18】,【24】,【25】陸續插入不需要任何分裂操作
最後，當插入【19】時，含有【14】,【16】,【17】,【18】的結點需要分裂，把中間元素【17】上移到父節點中，但是情況來了，父節點中空間已經滿了，是以也要進行分裂，将父節點中的中間元素【13】上移到新形成的根結點中，這樣具體插入操作的完成。
删除
首先查找B樹中需删除的元素,如果該元素在B樹中存在，則将該元素在其結點中進行删除；删除該元素後，首先判斷該元素是否有左右孩子結點，如果有，則上移孩子結點中的某相近元素(“左孩子最右邊的節點”或“右孩子最左邊的節點”)到父節點中，然後是移動之後的情況；如果沒有，直接删除。
某結點中元素數目小于（m/2）-1,(m/2)向上取整，則需要看其某相鄰兄弟結點是否豐滿；
如果豐滿（結點中元素個數大于(m/2)-1），則向父節點借一個元素來滿足條件；
如果其相鄰兄弟都不豐滿，即其結點數目等于(m/2)-1，則該結點與其相鄰的某一兄弟結點進行“合并”成一個結點；
接下來還以5階B樹為例，詳細講解删除的動作；
關鍵要領，元素個數小于 2（m/2 -1）就合并，大于4（m-1）就分裂
如圖依次删除依次删除【8】,【20】,【18】,【5】
首先删除元素【8】，當然首先查找【8】，【8】在一個葉子結點中，删除後該葉子結點元素個數為2，符合B樹規則，操作很簡單，咱們隻需要移動【11】至原來【8】的位置，移動【12】至【11】的位置（也就是結點中删除元素後面的元素向前移動）
下一步，删除【20】,因為【20】沒有在葉子結點中，而是在中間結點中找到，咱們發現他的繼承者【23】(字母升序的下個元素)，将【23】上移到【20】的位置，然後将孩子結點中的【23】進行删除，這裡恰好删除後，該孩子結點中元素個數大于2，無需進行合并操作。
下一步删除【18】，【18】在葉子結點中,但是該結點中元素數目為2，删除導緻隻有1個元素，已經小于最小元素數目2,而由前面我們已經知道：如果其某個相鄰兄弟結點中比較豐滿（元素個數大于ceil(5/2)-1=2），則可以向父結點借一個元素，然後将最豐滿的相鄰兄弟結點中上移最後或最前一個元素到父節點中，在這個執行個體中，右相鄰兄弟結點中比較豐滿（3個元素大于2），是以先向父節點借一個元素【23】下移到該葉子結點中，代替原來【19】的位置，【19】前移；然【24】在相鄰右兄弟結點中上移到父結點中，最後在相鄰右兄弟結點中删除【24】，後面元素前移。
最後一步删除【5】， 删除後會導緻很多問題，因為【5】所在的結點數目剛好達标，剛好滿足最小元素個數（ceil(5/2)-1=2）,而相鄰的兄弟結點也是同樣的情況，删除一個元素都不能滿足條件，是以需要該節點與某相鄰兄弟結點進行合并操作；首先移動父結點中的元素（該元素在兩個需要合并的兩個結點元素之間）下移到其子結點中，然後将這兩個結點進行合并成一個結點。是以在該執行個體中，咱們首先将父節點中的元素【4】下移到已經删除【5】而隻有【6】的結點中，然後将含有【4】和【6】的結點和含有【1】,【3】的相鄰兄弟結點進行合并成一個結點。
也許你認為這樣删除操作已經結束了，其實不然，在看看上圖，對于這種特殊情況，你立即會發現父節點隻包含一個元素【7】，沒達标（因為非根節點包括葉子結點的元素K必須滿足于2=<K<=4，而此處的K=1），這是不能夠接受的。如果這個問題結點的相鄰兄弟比較豐滿，則可以向父結點借一個元素。而此時兄弟節點元素剛好為2，剛剛滿足，隻能進行合并，而根結點中的唯一進制素【13】下移到子結點，這樣，樹的高度減少一層。
看完插入，删除，想必也把B樹的特征掌握了，下面普及下其他知識，換個腦子
計算機儲存設備一般分為兩種：記憶體儲器(main memory)和外存儲器(external memory)。
記憶體儲器為記憶體，記憶體存取速度快，但容量小，價格昂貴，而且不能長期儲存資料(在不通電情況下資料會消失)。
外存儲器即為磁盤讀取，磁盤讀取資料靠的是機械運動，每次讀取資料花費的時間可以分為尋道時間、旋轉延遲、傳輸時間三個部分，尋道時間指的是磁臂移動到指定磁道所需要的時間，主流磁盤一般在5ms以下；旋轉延遲就是我們經常聽說的磁盤轉速，比如一個磁盤7200轉，表示每分鐘能轉7200次，也就是說1秒鐘能轉120次，旋轉延遲就是1/120/2 = 4.17ms；傳輸時間指的是從磁盤讀出或将資料寫入磁盤的時間，一般在零點幾毫秒，相對于前兩個時間可以忽略不計。那麼通路一次磁盤的時間，即一次磁盤IO的時間約等于5+4.17 = 9ms左右，聽起來還挺不錯的，但要知道一台500 -MIPS的機器每秒可以執行5億條指令，因為指令依靠的是電的性質，換句話說執行一次IO的時間可以執行40萬條指令，資料庫動辄十萬百萬乃至千萬級資料，每次9毫秒的時間，顯然是個災難。下圖是計算機硬體延遲的對比圖，供大家參考：
考慮到磁盤IO是非常高昂的操作，計算機作業系統做了一些優化，當一次IO時，不光把目前磁盤位址的資料，而是把相鄰的資料也都讀取到記憶體緩沖區内，因為局部預讀性原理告訴我們，當計算機通路一個位址的資料的時候，與其相鄰的資料也會很快被通路到。每一次IO讀取的資料我們稱之為一頁(page)。具體一頁有多大資料跟作業系統有關，一般為4k或8k，也就是我們讀取一頁内的資料時候，實際上才發生了一次IO，這個理論對于索引的資料結構設計非常有幫助。
事實1 ： 不同容量的存儲器，通路速度差異懸殊。
磁盤(ms級别) << 記憶體(ns級别)， 100000倍
若記憶體通路需要1s，則一次外存通路需要一天
為了避免1次外存通路，甯願通路記憶體100次...是以将<code>最常用</code>的資料存儲在最快的存儲器中
事實2 ： 從磁盤中讀 1 B，與讀寫 1KB 的時間成本幾乎一樣
從以上資料中可以總結出一個道理，索引查詢的資料主要受限于硬碟的I/O速度，查詢I/O次數越少，速度越快，是以B樹的結構才應需求而生；B樹的每個節點的元素可以視為一次I/O讀取，樹的高度表示最多的I/O次數，在相同數量的總元素個數下，每個節點的元素個數越多，高度越低，查詢所需的I/O次數越少；假設，一次硬碟一次I/O資料為8K，索引用int(4位元組)類型資料建立，理論上一個節點最多可以為2000個元素，2000*2000*2000=8000000000，80億條的資料隻需3次I/O（理論值），可想而知，B樹做為索引的查詢效率有多高；
另外也可以看出同樣的總元素個數，查詢效率和樹的高度密切相關
B樹的高度
一棵含有N個總關鍵字數的m階的B樹的最大高度是多少？
log（m/2）(N+1)/2 + 1 ，log以（m/2）為低，(N+1)/2的對數再加1
算法如下
B+樹是應檔案系統所需而産生的B樹的變形樹，那麼可能一定會想到，既然有了B樹，又出一個B+樹，那B+樹必然是有很多優點的
B+樹的特征：
有m個子樹的中間節點包含有m個元素（B樹中是k-1個元素），每個元素不儲存資料，隻用來索引；
所有的葉子結點中包含了全部關鍵字的資訊，及指向含有這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大的順序連結。 (而B 樹的葉子節點并沒有包括全部需要查找的資訊)；
所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大（或最小）關鍵字。 (而B 樹的非終節點也包含需要查找的有效資訊)；
為什麼說B+樹比B樹更适合資料庫索引？
1）B+樹的磁盤讀寫代價更低
B+樹的内部結點并沒有指向關鍵字具體資訊的指針。是以其内部結點相對B 樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了；
2）B+樹查詢效率更加穩定
由于非終結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當；
3）B+樹便于範圍查詢（最重要的原因，範圍查找是資料庫的常态）
B樹在提高了IO性能的同時并沒有解決元素周遊的我效率低下的問題，正是為了解決這個問題，B+樹應用而生。B+樹隻需要去周遊葉子節點就可以實作整棵樹的周遊。而且在資料庫中基于範圍的查詢是非常頻繁的，而B樹不支援這樣的操作或者說效率太低；不懂可以看看這篇解讀-》範圍查找
補充：B樹的範圍查找用的是中序周遊，而B+樹用的是在連結清單上周遊；
B+樹如下：