1、B樹的定義
    B樹是一種平衡的多分樹（m叉樹），通常我們說(shuō)m階的B樹，它必須滿足如下條件：
    （1）每個(gè)結(jié)點(diǎn)至多有m個(gè)子結(jié)點(diǎn)；
    （2）若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；
    （3）所有的葉結(jié)點(diǎn)在同一層；
    （4）有k個(gè)子結(jié)點(diǎn)的非根結(jié)點(diǎn)恰好包含k-1個(gè)關(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é)點(diǎn)中關(guān)鍵字個(gè)數(shù)，即節(jié)點(diǎn)的大小
    struct BTNode    *parent;        //指向雙親結(jié)點(diǎn)
    int                key[M+1];        //關(guān)鍵字向量，0號(hào)單元未用
    struct BTNode    *son[M+1];        //子樹指針向量
    //Record        *recptr[M+1];    //記錄指針向量，0號(hào)單元未用(文件中使用)
}BTNode, *BTree;        //B-樹節(jié)點(diǎn)和B-樹的類型

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

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

2、B樹的查找
    B樹上的查找是一個(gè)順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)的關(guān)鍵碼中查找交叉進(jìn)行的過(guò)程。從根結(jié)點(diǎn)開始，在結(jié)點(diǎn)包含的關(guān)鍵碼中查找給定的關(guān)鍵碼，找到則查找成功；否則確定給定關(guān)鍵碼可能在的子樹，重復(fù)上面的操作，直到查找成功或者指針為空為止。
    下圖顯示了在B樹中查找關(guān)鍵碼21的過(guò)程。

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é)點(diǎn)中第i個(gè)關(guān)鍵碼等于key；
    //否則，特征值tag=0,等于key的關(guān)鍵碼記錄,應(yīng)插入在指針pt所指結(jié)點(diǎn)中第i個(gè)和第i+1個(gè)關(guān)鍵碼之間
    int found=false;
    int i;
    BTree p=root,father=NULL;    //初始化，p指向待查節(jié)點(diǎn)，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é)點(diǎn)中添加關(guān)鍵碼，如果該結(jié)點(diǎn)中關(guān)鍵碼不超過(guò)m-1個(gè)，則插入成功。否則要把這個(gè)結(jié)點(diǎn)分裂為兩個(gè)。并把中間的一個(gè)關(guān)鍵碼拿出來(lái)插到結(jié)點(diǎn)的父結(jié)點(diǎn)里去。父結(jié)點(diǎn)也可能是滿的，就需要再分裂，再往上插。最壞的情況，這個(gè)過(guò)程可能一直傳到根，如果需要分裂根，由于根是沒有父結(jié)點(diǎn)的，這時(shí)就建立一個(gè)新的根結(jié)點(diǎn)。插入可能導(dǎo)致B樹朝著根的方向生長(zhǎng)。 

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

　　(a)假設(shè)結(jié)點(diǎn)p中已經(jīng)含有m-1個(gè)關(guān)鍵字，再插入一個(gè)關(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é)點(diǎn)中去。

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

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

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

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

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

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

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

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

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

1、B+樹的查找

　　對(duì)B+樹可以進(jìn)行兩種查找運(yùn)算：

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

　　2.從根結(jié)點(diǎn)開始，進(jìn)行隨機(jī)查找。

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

2、B+樹的插入

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

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

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

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

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

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

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

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

3、B+樹的刪除

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

　　插入算法：

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

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

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

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

　　刪除算法：

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

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

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

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