在大型的資料庫存儲中，實作索引查找，如果采用二叉查找樹的查找的話，由于節點的存儲資料是有限的（不可能将節點存儲過多的資料，否則就變成線性的查找了），這樣如果資料量很大的，就會導緻樹的深度過大進而造成磁盤IO操作過于頻繁，就會導緻效率非常低下。
我們知道動态查找樹能夠提高查找效率，比如：二叉查找樹，平衡二叉查找樹，紅黑樹。他們查找效率的時間複雜度O(log2n)，跟樹的深度有關系，是以為了提高索引查找的效率，可以通過減少樹的深度，其中基本思想是：采用多叉樹結構。
B-樹
B-樹就是我們平常說的B樹，不要讀成B減樹了，它在檔案系統中很有用。
B-樹的定義和特點
一個m階的B-樹為滿足下列條件的m叉樹：
1、每個分支最多有m棵子樹（關鍵字最多m-1個）；
2、除根結點外，每個分支結點最少有[ m/2 ] ( 向上取整 )棵子樹；
3、根結點最少有兩棵子樹（除非根結點為葉結點，此時B-樹隻有一個葉結點）；
4、所有的葉子結點都位于同一層，葉結點不包含任何關鍵字資訊；
5、所有分支結點（非終端結點）中包含如下資訊：
其中，n為結點中關鍵字值的個數, n<=m
keyi為關鍵字，且滿足 keyi<keyi+1 ，1<=i<n
pi為指向該結點的第i+1棵子樹的根的指針，0<=i<=n，（pi指的結點中所有關鍵字值都大于keyi）如下為一個4階B-樹：
對于該4階B-樹，有如下特點：
1、每個分支結點最多有4棵子樹(即最多有m-1個關鍵字值)；
2、每個分支結點最少有2棵子樹；
3、根結點最少有2棵子樹；
4、所有“葉結點”都在同一層上，并且不帶資訊（可以看作是外部結點或查找失敗的結點，實際上這些結點不存在，指向這些結點的指針為空）
B-樹的查找
首先将給定的關鍵字k在B-樹的根結點的關鍵字集合中采用順序查找法或者折半查找法進行查找，若有k=keyi , 則查找成功，根據相應的指針取得記錄。否則，若k<keyi,則在指針pi-1所指的結點中重複上述查找過程，直到在某結點中查找成功，或者有pi-1=NULL，查找失敗。（類似于二叉排序樹的查找）
如下圖：
C語言實作如下：
#define//B-樹最大的階數
typedef struct node {
int keynum; //關鍵字個數
keytype key[M+1]; //關鍵字集合 key[0]未使用，關鍵字下标從1開始
struct node *ptr[M+1]; //子樹根結點集合
rectype *recptr[M+1]; //存儲位置集合
}*BTree; B-樹查找算法實作如下：
keytype MBSEARCH(Btree T,keytype k)
{
int i,n;
BTree p=T;
while(p!=NULL){
n=p->keynum;
p->key[n+1]=Maxkey;
i=1; //在P指結點的關鍵字集合中查找k
while(k>p->key[i])
i++;
if(p->key[i]==k)
return p->key[i];
else
p=p->ptr[i-1]; //在pi-1指的結點中查找
}
return -1;
} B-樹的插入
由于一棵m階B-樹的結點中最多有m-1個關鍵字值，是以當關鍵字數目超過m-1時，需要進行結點分裂，基本思想如下：
若将k插入到某結點後使得該結點中關鍵字值數目超過m-1時，則要以該結點位置居中的那個關鍵字值為界将該結點一分為二，産生一個新結點，并把位置居中的那個關鍵字值插入到雙親結點中；如雙親結點也出現上述情況,則需要再次進行分裂。最壞情況下，需要一直分裂到根結點，以緻于使得B-樹的深度加1。
B-樹的生成從空樹開始，即逐個在葉結點中插入結點(關鍵字)而得到。
插入結點（關鍵字）的步驟如下：
一個原始的B-樹階為3，如下圖：
首先，我需要插入一個關鍵字：30，可以得到如下的結果：
再插入26，得到如下的結果：
OK，此時如圖所示，在插入的那個終端結點中，它的關鍵字數已經超過了m-1=2，是以我們需要對結點進分裂，是以我們先對關鍵字排序，得到：26 30 37 ，是以它的左部分為（不包括中間值）：26，中間值為：30，右部為：37，左部放在原來的結點，右部放入新的結點，而中間值則插入到父結點，并且父結點會産生一個新的指針，指向新的結點的位置，如下圖所示：
OK，然後我們繼續插入新的關鍵字：85，得到如下圖結果：
正如圖所示，我需要對剛才插入的那個結點進行“分裂”操作，操作方式和之前的一樣，得到的結果如下：
哦，當我們分裂完後，突然發現之前的那個結點的父親結點的度為4了，說明它的關鍵字數超過了m-1，是以需要對其父結點進行“分裂”操作，得到如下的結果：
該部分内容參考自：五分鐘搞懂什麼是B-樹（全程圖解）
B+樹
B+樹的定義
一個m階的B+樹為滿足下列條件的m叉樹：
B+樹 可以看做是 在B-樹基礎上，為葉子結點增加連結清單指針，所有關鍵字都在葉子結點中出現，非葉子結點作為葉子結點的索引；B+樹總是到葉子結點才命中；B+樹的執行個體如下：