1、B樹的定義
    B樹是一種平衡的多分樹（m叉樹），通常我們說m階的B樹，它必須滿足如下條件：
    （1）每個結點至多有m個子結點；
    （2）若根結點不是葉子結點，則至少有兩棵子樹；
    （3）所有的葉結點在同一層；
    （4）有k個子結點的非根結點恰好包含k-1個關鍵碼。

2、B-樹數據結構
#define M 4        //B-樹的階，暫設為4
#define false 0
#define true 1

typedef struct BTNode
{
    int                keynum;            //節點中關鍵字個數，即節點的大小
    struct BTNode    *parent;        //指向雙親結點
    int                key[M+1];        //關鍵字向量，0號單元未用
    struct BTNode    *son[M+1];        //子樹指針向量
    //Record        *recptr[M+1];    //記錄指針向量，0號單元未用(文件中使用)
}BTNode, *BTree;        //B-樹節點和B-樹的類型

typedef struct
{
    BTNode            *pt;            //指向找到的節點
    int pos; //1...m,在節點中的關鍵字序號
    int                tag;            //1:查找成功，0:查找失敗
}Result;        //B-樹的查找結果類型

//初始化
void init_BTree(BTree &root)
{
    root=NULL;
}

2、B樹的查找
    B樹上的查找是一個順指針查找結點和在結點內的關鍵碼中查找交叉進行的過程。從根結點開始，在結點包含的關鍵碼中查找給定的關鍵碼，找到則查找成功；否則確定給定關鍵碼可能在的子樹，重復上面的操作，直到查找成功或者指針為空為止。
    下圖顯示了在B樹中查找關鍵碼21的過程。

int search(BTree &p,int key)
{
    int j;
    for(j=1; j<=p->keynum; j++)
        if(p->key[j] > key)
        {
            break;
        }
    return j-1;        //應該插入的位置的前一位
}
Result searchBtree(BTree &root, int key)
{
    //在m階B樹t上查找關鍵碼key，反回(pt,i,tag)。
    //若查找成功，則特征值tag=1，指針pt所指結點中第i個關鍵碼等于key；
    //否則，特征值tag=0,等于key的關鍵碼記錄,應插入在指針pt所指結點中第i個和第i+1個關鍵碼之間
    int found=false;
    int i;
    BTree p=root,father=NULL;    //初始化，p指向待查節點，q指向p的雙親
    Result    result;        //SearchBTree函數返回值

    while(p && !found)
    {
        i=search(p,key);    //p->node[i].key≤K<p->node[i+1].key
        if(i>0 && p->key[i]==key)
        {
            found=true;        //找到待查關鍵字
        }
        else
        {
            father=p;
            p=p->son[i];
        }
    }
    result.pos=i+1;        //pos是插入的位置,記住加1
    if(found)    //查找成功
    {
        result.pt=p;
        result.tag=1;   
    }
    else    //查找不成功，返回key的插入位置i
    {
        result.pt=father;
        result.tag=0;   
    }
    return result;
}//SearchBTree
 

3、B樹的插入
    首先是在恰當的葉子結點中添加關鍵碼，如果該結點中關鍵碼不超過m-1個，則插入成功。否則要把這個結點分裂為兩個。并把中間的一個關鍵碼拿出來插到結點的父結點里去。父結點也可能是滿的，就需要再分裂，再往上插。最壞的情況，這個過程可能一直傳到根，如果需要分裂根，由于根是沒有父結點的，這時就建立一個新的根結點。插入可能導致B樹朝著根的方向生長。 

B-樹的生成從空樹開始，逐個插入關鍵字而得。關鍵字的個數必須至少為[m/2]-1，每次插入總在最底層某個終端結點添加一個關鍵字，如果該結點關鍵字個數小于m-1則直接插入，如果發現新插入關鍵字后，關鍵字總數超過m-1個則結點需要分裂，做法如下：

　　(a)假設結點p中已經含有m-1個關鍵字，再插入一個關鍵字之后(插入總要保持關鍵字數組的大小有序，從小到大排好序)，可以將p分裂為p和p’，其中p含有的信息為[m/2]-1([m]表示大于m的最小整數)，p’含有的信息為m-[m/2] ([m]表示大于m的最小整數)。然后將關鍵字K[m/2]和指向p’的指針則一起插入到p的雙親結點中去。

　　(b)檢查雙親結點，如果雙親結點出現(a)的情況，則回到步驟a繼續執行。直到插入滿足條件為止，樹的深度增加過程是隨著插入而自下而上生長的過程。
    下圖顯示了在B樹中插入關鍵碼33的過程。

void split(BTree &q, int s, BTree &ap)
{
    // 將結點q分裂成兩個結點，前一半保留，后一半移入新生結點ap
    int i;
    cout<<"分裂!"<<"  "<<q->key[s]<<endl;
    ap=(BTree)malloc(sizeof(BTNode));        //生成新結點ap
    ap->son[0] = q->son[s];            //原來結點中間位置關鍵字相應指針指向的子樹放到新生成結點的0棵子樹中去
    for(i=s+1;i<=M;i++)        //后一半移入ap
    {
        ap->key[i-s]=q->key[i];
        ap->son[i-s]=q->son[i];
    }//for
    ap->keynum=M-s;
    ap->parent=q->parent;
    q->keynum=s-1;        //q的前一半保留，修改keynum
}//split

void NewRoot(BTree &root, int x, BTree &ap)        //生成新的根節點
{
    //生成含信息(root,r,ap)的新的根結點*root，原root和ap為子樹指針
    BTree p;
    p=(BTree)malloc(sizeof(BTNode));
    if(root)    //如果原來的樹不是空樹
        root->parent=p;                    //遠來的根的雙親指針指向新根
    p->son[0]=root;                        //新根的第一個孩子節點是原來的根節點
    root=p;        //root指向新根   
    root->parent=NULL;                    //新根的雙親是空指針
    root->keynum=1;           
    root->key[1]=x;                        //新根的第一個關鍵字就是前面分裂出來的關鍵字
    root->son[1]=ap;                    //新根的第二個孩子節點是原來的根中分裂出來的節點
    if(ap)        //如果原來的樹不是空樹
        ap->parent=root;                //原來的根中分裂出來的節點的雙親指針指向新根
}//NewRoot

void insert(BTree &q, int i, int key, BTree &ap)    //插入
{
    int j;
    for(j=q->keynum; j>=i; j--)
    {
        q->key[j+1]=q->key[j];
    }
    q->key[i]=key;
    for(j=q->keynum; j>=i; j--)
    {
        q->son[j+1]=q->son[j];
    }
    q->son[i]=ap;
    q->keynum++;
}//insert
void insertBtree(BTree &root, int key, BTree &q, int i)
{
    //在B-樹T上節點q的key[i]和key[i+1]之間插入關鍵字key
    //若引起節點過大，則沿雙親鏈進行必要的節點分裂整理，使T仍是M階的B-樹
    BTree ap=NULL;
    int x=key;
    int finished = false;
    int s;
    while(q && !finished)
    {
        insert(q, i, x, ap);    //將key和ap分別插入到q->key[i+1]和q->son[i+1]
        if(q->keynum <    M)
            finished = true;    //插入完成
        else
        {    //分裂結點*q
            s=ceil(M/2);
            x=q->key[s];
            split(q, s, ap);    //將q->key[s+1...M],q->son[s...M]和q->recptr[s+1...M]移入到新節點*ap
            q=q->parent;
            if(q)
                i=search(q,x)+1;        //在雙親結點*q中去查找x的插入位置,記住加1，因為search()返回的是插入位置的前一位
        }//else
    }//while
    if(!finished)                //root是空樹(參數q初值為NULL)或者根節點已分裂為節點*q和*ap
        NewRoot(root, x, ap);    //生成含信息(root,x,ap)的新的根節點*root，原root和ap為子樹指針
}//insertBtree

void SearchInsertBTree(BTree &root,int key)//搜索插入
{
    //在m階B樹*t上結點*q的key[i],key[i+1]之間插入關鍵碼key
    //若引起結點過大，則沿雙親鏈進行必要的結點分裂調整，使*t仍為m階B樹
    Result    rs;
    rs = searchBtree(root,key);
    if(!rs.tag)    //tag=0查找不成功，插入
    {
        cout<<"樹中沒有相同的節點，插入!"<<endl;
        insertBtree(root, key, rs.pt, rs.pos);    //在B-樹T上節點re.pt的key[i]和key[i+1]之間插入關鍵字key
    }
    else
    {
        cout<<"樹中已有相同的節點!"<<endl;
    }
}//InserBTree

4、B樹的刪除
    B樹中的刪除操作與插入操作類似，但要稍微復雜些。如果刪除的關鍵碼不在葉結點層，則先把此關鍵碼與它在B樹里的后繼對換位置，然后再刪除該關鍵碼。如果刪除的關鍵碼在葉結點層，則把它從它所在的結點里去掉，這可能導致此結點所包含的關鍵碼的個數小于 -1。這種情況下，考察該結點的左或右兄弟，從兄弟結點移若干個關鍵碼到該結點中來(這也涉及到它們的父結點中的一個關鍵碼要做相應變化)，使兩個結點所含關鍵碼個數基本相同。只有在兄弟結點的關鍵碼個數也很少，剛好等于 -1時，這個移動不能進行。這種情況下，要把將刪除關鍵碼的結點，它的兄弟結點及它們的父結點中的一個關鍵碼合并為一個結點。

B+樹
　B+樹是應文件系統所需而出的一種B-樹的變型樹。一棵m階的B+樹和m階的B-樹的差異在于：

　　1.有n棵子樹的結點中含有n個關鍵字。

　　2.所有的葉子結點中包含了全部關鍵字的信息，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序鏈接。

　　3.所有的非終端結點可以看成是索引部分，結點中僅含其子樹（根結點）中的最大（或最小）關鍵字。

　　通常在B+樹上有兩個頭指針，一個指向根結點，一個指向關鍵字最小的葉子結點。

1、B+樹的查找

　　對B+樹可以進行兩種查找運算：

　　1.從最小關鍵字起順序查找；

　　2.從根結點開始，進行隨機查找。

　　在查找時，若非終端結點上的劇組機等于給定值，并不終止，而是繼續向下直到葉子結點。因此，在B+樹中，不管查找成功與否，每次查找都是走了一條從根到葉子結點的路徑。其余同B-樹的查找類似。

2、B+樹的插入

　　m階B樹的插入操作在葉子結點上進行，假設要插入關鍵值a，找到葉子結點后插入a，做如下算法判別：

　　①如果當前結點是根結點并且插入后結點關鍵字數目小于等于m，則算法結束；

　　②如果當前結點是非根結點并且插入后結點關鍵字數目小于等于m，則判斷若a是新索引值時轉步驟④后結束，若a不是新索引值則直接結束；

　　③如果插入后關鍵字數目大于m(階數)，則結點先分裂成兩個結點X和Y，并且他們各自所含的關鍵字個數分別為：u=大于(m+1)/2的最小整數，v=小于(m+1)/2的最大整數；

　　由于索引值位于結點的最左端或者最右端，不妨假設索引值位于結點最右端，有如下操作：

　　如果當前分裂成的X和Y結點原來所屬的結點是根結點，則從X和Y中取出索引的關鍵字，將這兩個關鍵字組成新的根結點，并且這個根結點指向X和Y，算法結束；

　　如果當前分裂成的X和Y結點原來所屬的結點是非根結點，依據假設條件判斷，如果a成為Y的新索引值，則轉步驟④得到Y的雙親結點P，如果a不是Y結點的新索引值，則求出X和Y結點的雙親結點P；然后提取X結點中的新索引值a’，在P中插入關鍵字a’，從P開始，繼續進行插入算法；

　　④提取結點原來的索引值b，自頂向下，先判斷根是否含有b，是則需要先將b替換為a，然后從根結點開始，記錄結點地址P，判斷P的孩子是否含有索引值b而不含有索引值a，是則先將孩子結點中的b替換為a，然后將P的孩子的地址賦值給P，繼續搜索，直到發現P的孩子中已經含有a值時，停止搜索，返回地址P。

3、B+樹的刪除

　　B+樹的刪除也僅在葉子結點進行，當葉子結點中的最大關鍵字被刪除時，其在非終端結點中的值可以作為一個“分界關鍵字”存在。若因刪除而使結點中關鍵字的個數少于m/2 （m/2結果取上界，如5/2結果為3）時，其和兄弟結點的合并過程亦和B-樹類似。

　　另外的看法，當作補充和豐富吧。B樹，B-樹和B+樹是三個不同的概念。
 
B樹

　　二叉排序樹（Binary Sort Tree）又稱二叉查找樹，也叫B樹。

　　它或者是一棵空樹；或者是具有下列性質的二叉樹：

　　(1)若左子樹不空，則左子樹上所有結點的值均小于左子樹所在樹的根結點的值；

　　(2)若右子樹不空，則右子樹上所有結點的值均大于右子樹所在樹的根結點的值；

　　(3)左、右子樹也分別為二叉排序樹；

1、二叉排序樹（B樹）的查找：

　　時間復雜度與樹的深度的有關。

　　步驟：若根結點的關鍵字值等于查找的關鍵字，成功。

　　否則：若小于根結點的關鍵字值，遞歸查左子樹。

　　若大于根結點的關鍵字值，遞歸查右子樹。

　　若子樹為空，查找不成功。

2、二叉排序樹（B樹）的插入和刪除：

　　二叉排序樹是一種動態樹表。其特點是：樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等于給定值的節點時再進行插入。新插入的結點一定是一個新添加的葉子節點，并且是查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點。

　　插入算法：

　　首先執行查找算法，找出被插結點的父親結點。

　　判斷被插結點是其父親結點的左兒子還是右兒子。將被插結點作為葉子結點插入。

　　若二叉樹為空。則首先單獨生成根結點。

　　注意：新插入的結點總是葉子結點，所以算法復雜度是O(h)。

　　刪除算法：

　　如果刪除的結點沒有孩子，則刪除后算法結束；

　　如果刪除的結點只有一個孩子，則刪除后該孩子取代被刪除結點的位置；

　　如果刪除的結點有兩個孩子，則選擇右孩子為根的樹，它的左子樹中，值最小的點作為新的根，同時在該最小值處開始，執行刪除算法，如此繼續到刪除算法的前兩種情況時，刪除算法結束。

　　B樹用途：查找信息快速，但是隨著查找深度的增加，會影響查找的效率，所以，通常會使用平衡二叉樹的平衡算法來進行動態平衡。