一、什麼是B-樹（B-Tree）
B樹是平衡多叉樹，可以看做是對2-3樹的一種擴充，即允許每個節點有最多M個子節點，其中M為B樹的階。每個節點的多個key按升序排列，且有 節點所含key值的個數 = 節點的子樹的個數 – 1，就意味着某節點的每個子樹所在的位置是由該節點的key值的分布決定的。B樹的另外一個特性就是所有的葉子節點都處于同一層，也就是說從根節點到任意節點的深度都相等（平衡）。
2-3樹和2-3-4樹都是B樹的特例。結點最大的孩子數目稱為B樹的階，是以2-3樹是3階B樹，2-3-4樹是4階B樹。
B+樹是B樹的一種變形，二者的差異在于，非葉子節點的節點（就是中間節點）的子樹的個數 = 該節點的key的個數，這是因為B+樹中的中間節點的key并不用于儲存資料，而隻用來索引，而葉子節點中包含了全部的key以及value；所有的中間節點的key都同時存在于子節點，且在子節點的key中是最大或者最小的；所有的子節點都按照升序以指針連接配接在一起。由于B+樹的中間節點不再存儲value，那麼同樣大小的磁盤頁可以容納更多的節點元素，是以資料量相同的B樹與B+樹相比，後者更加“矮胖”，進而可以減少磁盤I/O。B+樹因為每次都要查找到葉子節點，是以查找性能穩定。範圍查詢時隻需在葉子節點順序周遊，更簡單。
二、B-樹的定義
B-樹是一種多路搜尋樹，要注意，并不是二叉樹。
- 定義任意非葉子結點最多隻有M個兒子；且M>2；
- 根結點的兒子數為[2, M]；
- 除根結點以外的非葉子結點的兒子數為[M/2, M]；
- 每個結點存放至少M/2-1（取上整）和至多M-1個關鍵字；（至少2個關鍵字）
- 非葉子結點的關鍵字個數=指向兒子的指針個數-1；
- 非葉子結點的關鍵字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
- 非葉子結點的指針：P[1], P[2], …, P[M]；其中P[1]指向關鍵字小于K[1]的子樹，P[M]指向關鍵字大于K[M-1]的子樹，其它P[i]指向關鍵字屬于(K[i-1], K[i])的子樹；
- 所有葉子結點位于同一層，且不帶任何資訊，也是為了保持算法的一緻性。
舉個栗子：M=3的情況下，我們的B-樹是長這樣子的：
三、B-樹的特性
- 關鍵字集合分布在整顆樹中；
- 任何一個關鍵字出現且隻出現在一個結點中；
- 搜尋有可能在非葉子結點結束；
- 其搜尋性能等價于在關鍵字全集内做一次二分查找；
- 自動層次控制；
四、對B-樹的操作
1.B-樹插入
一個原始的B-樹階為3，如下圖：
首先，我需要插入一個關鍵字：30，可以得到如下的結果：
再插入26，得到如下的結果：
OK，此時如圖所示，在插入的那個終端結點中，它的關鍵字數已經超過了m-1=2，是以我們需要對結點進分裂，是以我們先對關鍵字排序，得到：26 30 37 ，是以它的左部分為（不包括中間值）：26，中間值為：30，右部為：37，左部放在原來的結點，右部放入新的結點，而中間值則插入到父結點，并且父結點會産生一個新的指針，指向新的結點的位置，如下圖所示：
然後我們繼續插入新的關鍵字：85，得到如下圖結果：
正如圖所示，我需要對剛才插入的那個結點進行“分裂”操作，操作方式和之前的一樣，得到的結果如下：
當我們分裂完後，突然發現之前的那個結點的父親結點的度為4了，說明它的關鍵字數超過了m-1，是以需要對其父結點進行“分裂”操作，得到如下的結果：
2.B-樹删除
待補充（貌似小夥伴們不太喜歡看這個東東）
五、用途
B-樹主要應用在檔案系統
為了将大型資料庫檔案存儲在硬碟上 以減少通路硬碟次數為目的 在此提出了一種平衡多路查找樹——B-樹結構。由其性能分析可知它的檢索效率是相當高的 為了提高 B-樹性能’還有很多種B-樹的變型，力圖對B-樹進行改進。
未完待續。。。
- https://q.115.com/182920/T1267386.html?uid=20069