多路查找樹(muitl-way search tree)，其每一個節點的孩子數可以多于兩個，且每一個節點處可以存儲多個元素。主要有4中特殊形式。
一、2-3樹
定義：其中的每一個節點都具有兩個孩子（稱為2節點）或者三個孩子（稱為3節點）。
并且2-3樹中所有的葉子都在同一層上。
一個2節點包含一個元素和兩個孩子（或者沒有孩子）。
一個3節點包含一小一大兩個元素和三個孩子（或者沒有孩子）。
1. 2-3樹的插入實作
1）對于空樹，插入一個2節點即可；
2）插入節點到一個2節點的葉子上。由于本身就隻有一個元素，是以隻需要将其更新為3節點即可。
3）插入節點到一個3節點的葉子上。因為3節點本身最大容量，是以需要拆分，且将樹中兩元素或者插入元素的三者中選擇其一向上移動一層。
三種情況：
- 更新父節點
大話資料結構—多路查找樹（B樹） - 更新根節點
大話資料結構—多路查找樹（B樹） - 增加樹高度
大話資料結構—多路查找樹（B樹）
2. 2-3樹的删除實作
1）所删元素位于一個3節點的葉子節點上，直接删除，不會影響樹結構。
2）所删元素位于一個2節點上，直接删除，破壞樹結構。
分為四種情況：
- 此節點雙親也是2節點，且擁有一個3節點的右孩子；
大話資料結構—多路查找樹（B樹） - 此節點的雙親是2節點，它右孩子也是2節點；
大話資料結構—多路查找樹（B樹） - 此節點的雙親是3節點；
大話資料結構—多路查找樹（B樹） - 目前樹是一個滿二叉樹，降低樹高；
大話資料結構—多路查找樹（B樹）
3）所删元素位于非葉子的分支節點。此時按樹中序周遊得到此元素的前驅或後續元素，補位。
- 分支節點是2節點
大話資料結構—多路查找樹（B樹） - 分支節點是3節點
大話資料結構—多路查找樹（B樹）
二、2-3-4樹
2-3-4樹是2-3樹的擴充，包括了4節點的使用，一個4節點包含小中大三個元素和四個孩子（或沒有孩子）。
1. 2-3-4樹插入實作
建構一個數組為{7,1,2,5,6,9,8,4,3}的2-3-4樹的過程
2. 2-3-4樹删除實作
删除順序使1,6,3,4,5,2,9
三、B樹（B-樹）
B樹（B-樹）是一種平衡的多路查找樹。2-3樹和2-3-4樹都是B樹的特例。節點最大的孩子數組稱為B樹的階（order），是以，2-3樹是3階B樹，2-3-4樹是4階B樹。
比如說要查找7，首先從外存讀取得到根節點3,5,8三個元素，發現7不在，但是5、8之間，是以就通過A2再讀取外存的6,7節點找到結束。
B樹的插入和删除和2-3樹、2-3-4樹類似。
B樹的資料結構為内外存的資料互動準備的。當要處理的資料很大時，無法一次全部裝入記憶體。這時對B樹調整，使得B樹的階數與硬碟存儲的頁面大小相比對。比如說一棵B樹的階為1001（即1個節點包含1000個關鍵字），高度為2（從0開始），它可以存儲超過10億個關鍵字（1001x1001x1000+1001x1000+1000）,隻要讓根節點持久的保留在記憶體中，那麼在這顆樹上，尋找某一個關鍵字至多需要兩次硬碟的讀取即可。
對于n個關鍵字的m階B樹，最壞情況查找次數計算
第一層至少1個節點，第二層至少2個節點，由于除根節點外每個分支節點至少有⌈m/2⌉棵子樹，則第三層至少有2x⌈m/2⌉個節點。。。這樣第k+1層至少有2x(⌈m/2⌉)^(k-1),實際上，k+1層的節點就是葉子節點。若m階B樹有n個關鍵字，那麼當你找到葉子節點，其實也就等于查找不成功的節點為n+1，是以
n+1>=2x(⌈m/2⌉)^(k-1),即
在含有n個關鍵字的B樹上查找時，從根節點到關鍵位元組點的路徑上涉及的節點數不超多
四、B+樹
下圖B樹，我們要周遊它，假設每個節點都屬于硬碟的不同頁面，我們為了中序周遊所有的元素，頁面2-頁面1-頁面3-頁面1-頁面4-頁面1-頁面5.而且我們每經過節點周遊時，都會對節點中的元素進行一次周遊，糟糕！有沒有可能讓周遊時每個元素隻通路一次呢？
B+樹是應檔案系統所需而出的一種B樹的變形樹，在B樹中，每一個元素樹中隻出現一次，而B+樹中，出現在分支節點中的元素會被當做他們在該分支節點位置的中序後繼者（葉子節點）中再次列出。另外，每一個葉子節點都會儲存一個指向後一葉子節點的指針。
下圖就是B+樹，灰色關鍵字，在根節點出現，在葉子節點中再次列出。
B+樹适合随機查找，隻不過查到後是索引，不能提供實際記錄的通路，還需要到達包含此關鍵字的終端節點。非葉結點僅具有索引作用，跟記錄有關的資訊均存放在葉結點中。B+樹适合帶有範圍的查找。B+樹插入、删除類似B樹。
五、引用參考
- 從B樹、B+樹、B*樹談到R 樹 July經典
- B-樹、B+樹、B*樹的差別
- B-樹（B樹）學習筆記
附加源碼
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存儲空間初始配置設定量 */
#define m 3 /* B樹的階，暫設為3 */
#define N 17 /* 資料元素個數 */
#define MAX 5 /* 字元串最大長度+1 */
typedef int Status; /* Status是函數的類型,其值是函數結果狀态代碼，如OK等 */
typedef struct BTNode
{
int keynum; /* 結點中關鍵字個數，即結點的大小 */
struct BTNode *parent; /* 指向雙親結點 */
struct Node /* 結點向量類型 */
{
int key; /* 關鍵字向量 */
struct BTNode *ptr; /* 子樹指針向量 */
int recptr; /* 記錄指針向量 */
}node[m+]; /* key,recptr的0号單元未用 */
}BTNode,*BTree; /* B樹結點和B樹的類型 */
typedef struct
{
BTNode *pt; /* 指向找到的結點 */
int i; /* 1..m，在結點中的關鍵字序号 */
int tag; /* 1:查找成功，O:查找失敗 */
}Result; /* B樹的查找結果類型 */
/* 在p->node[1..keynum].key中查找i,使得p->node[i].key≤K＜p->node[i+1].key */
int Search(BTree p, int K)
{
int i=,j;
for(j=;j<=p->keynum;j++)
if(p->node[j].key<=K)
i=j;
return i;
}
/* 在m階B樹T上查找關鍵字K，傳回結果(pt,i,tag)。若查找成功，則特征值 */
/* tag=1，指針pt所指結點中第i個關鍵字等于K；否則特征值tag=0，等于K的 */
/* 關鍵字應插入在指針Pt所指結點中第i和第i+1個關鍵字之間。 */
Result SearchBTree(BTree T, int K)
{
BTree p=T,q=NULL; /* 初始化，p指向待查結點，q指向p的雙親 */
Status found=FALSE;
int i=;
Result r;
while(p&&!found)
{
i=Search(p,K); /* p->node[i].key≤K<p->node[i+1].key */
if(i>&&p->node[i].key==K) /* 找到待查關鍵字 */
found=TRUE;
else
{
q=p;
p=p->node[i].ptr;
}
}
r.i=i;
if(found) /* 查找成功 */
{
r.pt=p;
r.tag=;
}
else /* 查找不成功，傳回K的插入位置資訊 */
{
r.pt=q;
r.tag=;
}
return r;
}
/* 将r->key、r和ap分别插入到q->key[i+1]、q->recptr[i+1]和q->ptr[i+1]中 */
void Insert(BTree *q,int i,int key,BTree ap)
{
int j;
for(j=(*q)->keynum;j>i;j--) /* 空出(*q)->node[i+1] */
(*q)->node[j+]=(*q)->node[j];
(*q)->node[i+].key=key;
(*q)->node[i+].ptr=ap;
(*q)->node[i+].recptr=key;
(*q)->keynum++;
}
/* 将結點q分裂成兩個結點，前一半保留，後一半移入新生結點ap */
void split(BTree *q,BTree *ap)
{
int i,s=(m+)/;
*ap=(BTree)malloc(sizeof(BTNode)); /* 生成新結點ap */
(*ap)->node[].ptr=(*q)->node[s].ptr; /* 後一半移入ap */
for(i=s+;i<=m;i++)
{
(*ap)->node[i-s]=(*q)->node[i];
if((*ap)->node[i-s].ptr)
(*ap)->node[i-s].ptr->parent=*ap;
}
(*ap)->keynum=m-s;
(*ap)->parent=(*q)->parent;
(*q)->keynum=s-; /* q的前一半保留，修改keynum */
}
/* 生成含資訊(T,r,ap)的新的根結點&T，原T和ap為子樹指針 */
void NewRoot(BTree *T,int key,BTree ap)
{
BTree p;
p=(BTree)malloc(sizeof(BTNode));
p->node[].ptr=*T;
*T=p;
if((*T)->node[].ptr)
(*T)->node[].ptr->parent=*T;
(*T)->parent=NULL;
(*T)->keynum=;
(*T)->node[].key=key;
(*T)->node[].recptr=key;
(*T)->node[].ptr=ap;
if((*T)->node[].ptr)
(*T)->node[].ptr->parent=*T;
}
/* 在m階B樹T上結點*q的key[i]與key[i+1]之間插入關鍵字K的指針r。若引起 */
/* 結點過大,則沿雙親鍊進行必要的結點分裂調整,使T仍是m階B樹。 */
void InsertBTree(BTree *T,int key,BTree q,int i)
{
BTree ap=NULL;
Status finished=FALSE;
int s;
int rx;
rx=key;
while(q&&!finished)
{
Insert(&q,i,rx,ap); /* 将r->key、r和ap分别插入到q->key[i+1]、q->recptr[i+1]和q->ptr[i+1]中 */
if(q->keynum<m)
finished=TRUE; /* 插入完成 */
else
{ /* 分裂結點*q */
s=(m+)/;
rx=q->node[s].recptr;
split(&q,&ap); /* 将q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新結點*ap */
q=q->parent;
if(q)
i=Search(q,key); /* 在雙親結點*q中查找rx->key的插入位置 */
}
}
if(!finished) /* T是空樹(參數q初值為NULL)或根結點已分裂為結點*q和*ap */
NewRoot(T,rx,ap); /* 生成含資訊(T,rx,ap)的新的根結點*T，原T和ap為子樹指針 */
}
void print(BTNode c,int i) /* TraverseDSTable()調用的函數 */
{
printf("(%d)",c.node[i].key);
}
int main()
{
int r[N]={,,,,,,,,,,,,,,,,};
BTree T=NULL;
Result s;
int i;
for(i=;i<N;i++)
{
s=SearchBTree(T,r[i]);
if(!s.tag)
InsertBTree(&T,r[i],s.pt,s.i);
}
printf("\n請輸入待查找記錄的關鍵字: ");
scanf("%d",&i);
s=SearchBTree(T,i);
if(s.tag)
print(*(s.pt),s.i);
else
printf("沒找到");
printf("\n");
return ;
}