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

2、B-樹數(shù)據(jù)結(jié)構(gòu)
#define M 4        //B-樹的階，暫設(shè)為4
#define false 0
#define true 1

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

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

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

2、B樹的查找
    B樹上的查找是一個順指針查找結(jié)點和在結(jié)點內(nèi)的關(guān)鍵碼中查找交叉進行的過程。從根結(jié)點開始，在結(jié)點包含的關(guān)鍵碼中查找給定的關(guān)鍵碼，找到則查找成功；否則確定給定關(guān)鍵碼可能在的子樹，重復(fù)上面的操作，直到查找成功或者指針為空為止。
    下圖顯示了在B樹中查找關(guān)鍵碼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;        //應(yīng)該插入的位置的前一位
}
Result searchBtree(BTree &root, int key)
{
    //在m階B樹t上查找關(guān)鍵碼key，反回(pt,i,tag)。
    //若查找成功，則特征值tag=1，指針pt所指結(jié)點中第i個關(guān)鍵碼等于key；
    //否則，特征值tag=0,等于key的關(guān)鍵碼記錄,應(yīng)插入在指針pt所指結(jié)點中第i個和第i+1個關(guān)鍵碼之間
    int found=false;
    int i;
    BTree p=root,father=NULL;    //初始化，p指向待查節(jié)點，q指向p的雙親
    Result    result;        //SearchBTree函數(shù)返回值

    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;        //找到待查關(guān)鍵字
        }
        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樹的插入
    首先是在恰當(dāng)?shù)娜~子結(jié)點中添加關(guān)鍵碼，如果該結(jié)點中關(guān)鍵碼不超過m-1個，則插入成功。否則要把這個結(jié)點分裂為兩個。并把中間的一個關(guān)鍵碼拿出來插到結(jié)點的父結(jié)點里去。父結(jié)點也可能是滿的，就需要再分裂，再往上插。最壞的情況，這個過程可能一直傳到根，如果需要分裂根，由于根是沒有父結(jié)點的，這時就建立一個新的根結(jié)點。插入可能導(dǎo)致B樹朝著根的方向生長。 

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

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

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

void split(BTree &q, int s, BTree &ap)
{
    // 將結(jié)點q分裂成兩個結(jié)點，前一半保留，后一半移入新生結(jié)點ap
    int i;
    cout<<"分裂!"<<"  "<<q->key[s]<<endl;
    ap=(BTree)malloc(sizeof(BTNode));        //生成新結(jié)點ap
    ap->son[0] = q->son[s];            //原來結(jié)點中間位置關(guān)鍵字相應(yīng)指針指向的子樹放到新生成結(jié)點的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)        //生成新的根節(jié)點
{
    //生成含信息(root,r,ap)的新的根結(jié)點*root，原root和ap為子樹指針
    BTree p;
    p=(BTree)malloc(sizeof(BTNode));
    if(root)    //如果原來的樹不是空樹
        root->parent=p;                    //遠(yuǎn)來的根的雙親指針指向新根
    p->son[0]=root;                        //新根的第一個孩子節(jié)點是原來的根節(jié)點
    root=p;        //root指向新根   
    root->parent=NULL;                    //新根的雙親是空指針
    root->keynum=1;           
    root->key[1]=x;                        //新根的第一個關(guān)鍵字就是前面分裂出來的關(guān)鍵字
    root->son[1]=ap;                    //新根的第二個孩子節(jié)點是原來的根中分裂出來的節(jié)點
    if(ap)        //如果原來的樹不是空樹
        ap->parent=root;                //原來的根中分裂出來的節(jié)點的雙親指針指向新根
}//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上節(jié)點q的key[i]和key[i+1]之間插入關(guān)鍵字key
    //若引起節(jié)點過大，則沿雙親鏈進行必要的節(jié)點分裂整理，使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
        {    //分裂結(jié)點*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]移入到新節(jié)點*ap
            q=q->parent;
            if(q)
                i=search(q,x)+1;        //在雙親結(jié)點*q中去查找x的插入位置,記住加1，因為search()返回的是插入位置的前一位
        }//else
    }//while
    if(!finished)                //root是空樹(參數(shù)q初值為NULL)或者根節(jié)點已分裂為節(jié)點*q和*ap
        NewRoot(root, x, ap);    //生成含信息(root,x,ap)的新的根節(jié)點*root，原root和ap為子樹指針
}//insertBtree

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

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

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

　　1.有n棵子樹的結(jié)點中含有n個關(guān)鍵字。

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

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

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

1、B+樹的查找

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

　　1.從最小關(guān)鍵字起順序查找；

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

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

2、B+樹的插入

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

　　①如果當(dāng)前結(jié)點是根結(jié)點并且插入后結(jié)點關(guān)鍵字?jǐn)?shù)目小于等于m，則算法結(jié)束；

　　②如果當(dāng)前結(jié)點是非根結(jié)點并且插入后結(jié)點關(guān)鍵字?jǐn)?shù)目小于等于m，則判斷若a是新索引值時轉(zhuǎn)步驟④后結(jié)束，若a不是新索引值則直接結(jié)束；

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

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

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

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

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

3、B+樹的刪除

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

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

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

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

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

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

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

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

　　時間復(fù)雜度與樹的深度的有關(guān)。

　　步驟：若根結(jié)點的關(guān)鍵字值等于查找的關(guān)鍵字，成功。

　　否則：若小于根結(jié)點的關(guān)鍵字值，遞歸查左子樹。

　　若大于根結(jié)點的關(guān)鍵字值，遞歸查右子樹。

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

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

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

　　插入算法：

　　首先執(zhí)行查找算法，找出被插結(jié)點的父親結(jié)點。

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

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

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

　　刪除算法：

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

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

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

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