B-树，B+树

现在的位置: 首页 > 综合 > 正文

2018年12月16日 ⁄ 综合 ⁄ 共 3023字 ⁄ 字号小中大 ⁄ 评论关闭

1.B-树

B-树是一种平衡的多路查找树，一棵m阶B-树，或为空树，或为满足下列特性的m叉树：

树中每个节点至多有m棵子树。
如果根节点不是叶子节点，则至少有两个子树。
除了根节点以外，所有非终端节点至少有m / 2取上届棵子树。
所有非终端节点包含以下信息（n，A0, K1, A1, K2, A2 ... Kn, An），n表示节点所含关键字个数，K表示关键字，A表示指向子树的指针。
所有叶子节点都出现在同一层次上，并且不带任何信息，即指向叶子节点的指针为空。

#define m 3
class BTnode{
public:
    int keynum;       //节点中关键字个数
    int key[m+1];     //关键字,0号未用
    BTnode *ptr[m+1]; //子树指针，0号未用
}

class Result{
public:
    BTnode *pt;       //指向找到的节点
    int i;            //在节点的关键字序列中的序号
    int tag;          //标识符，0表示查找失败，1表示查找成功
}

B-树的查询算法很简单，首先从根节点出发，一次遍历关键字，如果某个关键字与所查询的key相等，则查询成功，返回当前节点，如果key小于某个关键字，则递归想该关键字的对应的指针所指向的子树查询，当到达叶子节点说明未找到。

Result * searchBTree(BTree *T, int key){
    Result *rs = new Result();
    int i = 0;
    BTree *p = T, *q;
    bool check = false;
    while(p && !check){
        for(i = 1; i <= p -> keynum; i++)
            if(key <= p -> key[i])
                break;
        
        if(i > 0 && p -> key[i] == key)
            check = true;
        else{
            q = p;
            p = p -> ptr[i-1];  //这里应该是插入i的前一个指针节点
        }  
    }
    if(check){
        rs -> pt = p;
        rs -> i = i;
        rs -> tag = 1;
    }
    else{
        rs -> pt = q;
        rs -> i = i;
        rs -> tag = 0;
    }
    return rs;
}

深度为l+1的m阶B-树所具有的节点树N具有以下性质：N + 1 >= 2 * （M / 2）^（l - 1）. （m / 2取上界）

2.B-树的插入与删除

B-树是从一棵空树，一次插入节点而成。由于B-树的关键字个数必须 >= m / 2 （取上界） - 1，因此每次插入一个节点，不是建立一个叶子节点，而是现在最底层的非终端节点添加一个关键字，如果关键字的个数小于m，则插入完成，否则需要将节点“分裂”。

假设*p节点中已经有m - 1个关键字，当插入一个关键字后，节点中含有信息（m，A0，K1， A1，。。。， Km，Am）。此时可以将*p分解为*p（[m / 2] - 1, A0, K1, A1, ..., K[m / 2 - 1], A[m / 2 - 1]），和*q（m - [m / 2], A[m/2], K[m/2 + 1], A[m/2 + 1], ..., K[m], A[m]）。而关键字K[m/2]和*q一起插入到*p的双亲节点中。然后递归判断*p的双亲节点，[ ] 在此表示取上界。

void insertBTree(BTree *T, int key, BTree *q, int i){
    //在q的关键字q -> key[i]和q-> key[i+1]之间插入关键字key，必要时需要分裂节点
    int x = key, s;
    BTree *ap = NULL;
    bool finish = false;
    while(q && !finish){
        Insert(q, i, x, ap);  //将x和ap分别插入q -> key[i+1]和q -> ptr[i+1]
        if(q -> keynum < m) finish = true;
        else{
            s = ceil(m / 2);
            split(q, s, ap);
            x = q -> key[s];
            q = q -> parent;
            if(q) i = search(q, x);  //在双亲节点q中查找x的插入位置
        }
    }
    if(!finish)
        newroot(T, q, x, ap);  //如果T是空树，或者根节点已经分裂，或者是根节点分裂，因为根节点的双亲为NULL
}

void Insert(BTree *q, int i, int key, BTree *ap){
    int j;
    for(j = q -> keynum; j > i; j--)
        q -> key[j+1] = key[j];
        q -> key[j] = key;
    for(j = q -> keynum; j > i; j--)
        q -> ptr[j+1] = q -> ptr[j];
    q -> ptr[j] = ap;
    q -> keynum++;
}

void split(BTree *q, int s, BTree *ap){
    int i;
    cout << "split " << q -> key[s] << endl;
    ap = new BTree();
    ap -> ptr[0] = q -> ptr[s];
    for(i = s + 1; i <= m; i++){        //因为要分裂，所以关键字个数肯定是m
        ap -> ptr[i - s] = q -> ptr[i];
        qp -> key[i - s] = q -> key[i];
    }
    ap -> keynum = q -> m - s;
    ap -> parent = q -> parent;
    q -> keynum = s - 1;
}

void newroot(BTree *root, int x, BTree *ap){
    BTree *p = new BTree();
    if(root) root -> parent = p;  //如果root不是空树
    p -> ptr[0] = root;
    root = p;                     //root指向新的根
    root -> parent = NULL;
    root -> keynum = 1;
    root -> key[1] = x;
    root -> ptr[1] = ap;
    if(ap) ap -> parent = root;   //如果原来的树不是空树
}

在B-树上删除一个关键字，首先应该找到关键字所在的该节点，并从中删除。如果该节点为最下层的非终端节点，且其中的关键字数目不少于[m / 2]，则删除完成，否则要进行合并。如果删除关键字为非终端节点中的ki，则可以ai所指子树中最小的关键字Y代替ki，然后再相应节点中删除Y。所以可以只考虑删除最下层非终端节点中关键字的情况，分三种情形：

被删关键字所在节点中的关键字树目不小于ceil(m / 2)，只需删除关键字Ki和相应指针Ai，其他不变。例如删除关键字12.
被删除的关键字所在节点中关键字个数等于ceil(m / 2) - 1，而该节点的相邻右兄弟（或左兄弟）节点关键字个数大于ceil(m / 2) - 1，则需将其兄弟节点中最小（最大）的关键字上移至双亲节点，将双亲节点中小于（大于）且仅靠该上移关键字的关键字下一至被删除关键字所在的节点中。例如删除关键字50.
被删的关键字所在的节点和其兄弟节点的关键字树木均等于ceil(m / 2) - 1，假设该节点有右兄弟，且右兄弟节点由其双亲中的指针Ai所指，则删去关键字后，他所在节点中剩余的关键字和指针，加上双亲节点中的关键字Ki一起，合并到Ai所指的兄弟节点中去（如果没有右兄弟，就合并到左兄弟中去）。例如删除53: