二叉樹的應用---4.B+樹

（一）B+樹及其查找：

B+數可以保持資料的穩定有序，其插入和修改具有較穩定的時間複雜度，在B+樹中，對資料的引用指向葉子結點，内部結點的關鍵字隻是充當劃分子樹的分界值：

其定義和B-樹相同：

• 樹中每個結點最多有m個子樹
• 根結點最少有兩個子樹
• 除了根結點以外的非葉子結點最少有m/2個子樹
• 所有葉子結點都出現在同一層
• 其中有n+1個子樹的非葉子結點的資訊如下圖：

  

通常B+樹上有兩個指針，一個指向根結點，另一個指向關鍵字最小的葉子結點，如圖所示：

B+樹查找的過程和b-樹相似，但查找時，無論非葉子結點的關鍵字是否和給定關鍵字相同，都要沿着相應子樹向下查找，一直找到葉子結點；是以，每次查找都是從根結點到葉子結點的一條路徑；

（二）B+樹的插入和删除：

與B-樹相似，B+樹的插入和删除均是在葉子結點上進行；

插入：

• （1）當插入後關鍵字數目滿足條件時：

  

• （2）當結點中的關鍵字數目大于m個時要分裂為兩個結點，每個結點的關鍵字數目分别為m/2，（m+1）/2；

  與B+樹不同的是:如圖，插入23後，關鍵字數目超過3，則将葉子結點分裂為兩部分q和p，把前兩個關鍵字和指針移動到新結點q，同時把q的最後一個關鍵字複制到雙親結點，

  

删除：

（1）在删除葉子結點的最大關鍵字後，其在非終端結點的副本仍可以作為一個分解關鍵字使用

如圖，若删除25，則隻删除25即可，其餘無需變化；

和B-樹類似：（2），當删除的結點的兄弟結點關鍵字數目大于m/2，則将葉子結點個兄弟結點的關鍵字重新配置設定

（3）否則删除葉子結點，将剩餘關鍵字合并到兄弟結點中

如圖為（2）情況：

如圖為（3）的情況：