前戲 我們大家都知道動態查找樹能夠提高查找效率，比如：二叉查找樹，平衡二叉查找樹，紅黑樹。他們查找效率的時間複雜度O(log2n)，跟樹的深度有關係，那麼怎麼樣才能提高效率呢？當然最快捷的方式就是減少樹的深度了。那麼怎麼減少樹的深度呢？為瞭解答這個問題，我們慢慢來看，先看個實際問題吧。 問題背景 在 ...
前戲
我們大家都知道動態查找樹能夠提高查找效率，比如：二叉查找樹，平衡二叉查找樹，紅黑樹。他們查找效率的時間複雜度O(log2n)，跟樹的深度有關係，那麼怎麼樣才能提高效率呢？當然最快捷的方式就是減少樹的深度了。那麼怎麼減少樹的深度呢？為瞭解答這個問題，我們慢慢來看，先看個實際問題吧。
問題背景
在大型的資料庫存儲中，實現索引查找，如果採用二叉查找樹的查找的話，由於節點的存儲數據是有限的（不可能將節點存儲過多的數據，否則就變成線性的查找了），這樣如果數據量很大的，就會導致樹的深度過大從而造成磁碟IO操作過於頻繁（你們知道磁碟IO操作是非常耗時的），就會導致效率非常低下。可能有童鞋會問了，那為什麼不把節點索引載入到記憶體中，這樣訪問不就快了嗎？其實這顯然是不可能完成的，因為往往存儲的索引可能就有好幾個G了。全部載入到記憶體也是不現實的。能做的只有逐一載入每一個磁碟頁，這裡的磁碟頁就相當於索引樹的節點。
根據平衡二叉樹的啟發，自然就想到了平衡多路查找樹結構。也就是本文的主題B-tree，好了廢話不多說了，進入正題！
B-tree的簡介
B-樹就是我們平常說的B樹，不要讀成B減樹了，它在文件系統中很有用（原因之前已經介紹了），我們先來看下一個m階的Bs樹具有如下幾個特性：
- 根節點至少有兩個子女
- 每個中間節點都包含k-1個元素和k個孩子，其中m/2<=k<=m
- 每個葉子節點都包含k-1元素，其中m/2<=k<=m
- 所有的葉子節點都位於同一層
每個節點的元素從小到大排列，節點當中k-1個元素正好是k個孩子包含的元素的值域分劃。
看起來是不是很複雜，沒看懂也沒有關係，我們用實際例子來演示下。例子來源網路，參考：
https://blog.csdn.net/qq_35644234/article/details/66969238
B-樹插入
其實B-樹的插入是很簡單的，它主要是分為如下的兩個步驟：
1. 使用之前介紹的查找演算法查找出關鍵字的插入位置，如果我們在B-樹中查找到了關鍵字，則直接返回。否則它一定會失敗在某個最底層的終端結點上。
2.然後，我就需要判斷那個終端結點上的關鍵字數量是否滿足：n<=m-1,如果滿足的話，就直接在該終端結點上添加一個關鍵字，否則我們就需要產生結點的“分裂”。
分裂的方法是：生成一新結點。把原結點上的關鍵字和k（需要插入的值）按升序排序後，從中間位置把關鍵字（不包括中間位置的關鍵字）分成兩部分。左部分所含關鍵字放在舊結點中，右部分所含關鍵字放在新結點中，中間位置的關鍵字連同新結點的存儲位置插入到父結點中。如果父結點的關鍵字個數也超過（m-1），則要再分裂，再往上插。直至這個過程傳到根結點為止。
一個原始的B-樹階為3，如下圖：
階指的是，一個節點最多能有多少個子節點
首先，我需要插入一個關鍵字：30，可以得到如下的結果：
再插入26，得到如下的結果：
OK，此時如圖所示，在插入的那個終端結點中，它的關鍵字數已經超過了m-1=2，所以我們需要對結點進分裂，所以我們先對關鍵字排序，得到：26 30 37 ，所以它的左部分為（不包括中間值）：26，中間值為：30，右部為：37，左部放在原來的結點，右部放入新的結點，而中間值則插入到父結點，並且父結點會產生一個新的指針，指向新的結點的位置，如下圖所示：
OK，然後我們繼續插入新的關鍵字：85，得到如下圖結果：
正如圖所示，我需要對剛纔插入的那個結點進行“分裂”操作，操作方式和之前的一樣，得到的結果如下：
哦，當我們分裂完後，突然發現之前的那個結點的父親結點的度為4了，說明它的關鍵字數超過了m-1，所以需要對其父結點進行“分裂”操作，得到如下的結果：
