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树用途：查找信息快速，但是随着查找深度的增加，会影响查找的效率，所以，通常会使用平衡二叉树的平衡算法来进行动态平衡。