B树的原理与实现-阿里云开发者社区

一、b树定义

b树的定义

可以概括为

2 ≪ 根节点子树 ≪ M 2\ll 根节点子树\ll M2≪根节点子树≪M

M / 2 ≪ 分支节点子树 ≪ M M/2\ll分支节点子树 \ll MM/2≪分支节点子树≪M

当前节点关键字数 = 当前节点子树数量 − 1 当前节点关键字数=当前节点子树数量-1当前节点关键字数=当前节点子树数量−1

B树是多路平衡搜索树，并要求所有叶结点都在同一层。

二、实现b树

1.定义b树节点

typedef int KEY_VALUE;
typedef struct _btree_node {
  KEY_VALUE *keys;
  struct _btree_node **childrens;
  int num;//当前节点key的数量
  int leaf;//当前节点是否为叶子节点
} btree_node;
typedef struct _btree {
  btree_node *root;//根节点
  int t;
} btree;

对于 b树 btree_node：

root为根节点，t为一个整数，2*t=M，2*t-1=M-1，通过这种方式，限制每个节点的最大key个数为奇数，最多子树个数为偶数

对于b树节点 btree：

KEY_VALUE *keys;存放key，可以理解为keys[2t-1]

struct _btree_node **childrens; 存放子节点，可以理解为指针数组，_btree_node *childrens[2t];

2.插入节点

所有节点都是插入到叶子节点

在插入前，有以下几种情况

1.找到对应的节点，并且未满

2.找到的节点已满

2.1.找的内节点已满，内节点(除叶子节点)分裂

2.2.找的叶子节点已满，叶子节点分裂

上述操作完成后，就可以插入节点了

叶子节点分裂

在分裂keys后，子节点也要分裂

void btree_split_child(btree *T, btree_node *x, int i) {//当前这个节点，第i棵子节点要分裂
  int t = T->t;
  btree_node *y = x->childrens[i];//要分裂的节点
  btree_node *z = btree_create_node(t, y->leaf);//创建一个新的节点，之后会把y中 t-1个key给复制到这里（y原来有2t-1个，由于满了，没法加入新的key，因此要分裂）。
  z->num = t - 1;
  int j = 0;
  for (j = 0;j < t-1;j ++) {//把要分裂的节点后面t-1个key，复制给新创建的节点
    z->keys[j] = y->keys[j+t];
  }
  if (y->leaf == 0) {//把对应的子树也拷贝过来
    for (j = 0;j < t;j ++) {
      z->childrens[j] = y->childrens[j+t];
    }
  }
  y->num = t - 1;
  for (j = x->num;j >= i+1;j --) {//由于分裂多了一个节点，要插入到( btree_node *x)的分裂的孩子节点的后面（有可能是中间，因此要遍历），把后面的节点在数组中统统后移一位
    x->childrens[j+1] = x->childrens[j];
  }
  x->childrens[i+1] = z;//当前这个节点的孩子数量+1
  for (j = x->num-1;j >= i;j --) {//由于分裂，要将子节点正中间一个key插入到父节点（ btree_node *x）的keys中，把当前节点后面的key在数组中统统后移一位
    x->keys[j+1] = x->keys[j];
  }
  x->keys[i] = y->keys[t-1];
  x->num += 1;//当前这个节点的 key数量+1
}

根节点分裂

如果根节点的keys满了，那么就需要分裂根节点了，

当要插入根节点满时，就给根节点创建一个空的父节点，添加F的时候，就把最中间的c放到上面空节点上去就行了，这样就和之前的分裂叶子节点一样了，然后再插入新的F

在btree_insert中，只对根节点进行特殊处理因为处理完根节点后，后面的操作都是一样的。

void btree_insert(btree *T, KEY_VALUE key) {
  //int t = T->t;
  btree_node *r = T->root;
  if (r->num == 2 * T->t - 1) {//根节点满了
    btree_node *node = btree_create_node(T->t, 0);//给根节点创建一个空的父节点，把空节点作为根节点，然后去分裂新的空节点的第i个子节点就行了
    T->root = node;
    node->childrens[0] = r;
    btree_split_child(T, node, 0);
    int i = 0;
    if (node->keys[0] < key) i++;
    btree_insert_nonfull(T, node->childrens[i], key);
  } else {//根节点没满,往根节点传输 要新加入的key，后续会放到特定的叶子节点上。
    btree_insert_nonfull(T, r, key);
  }
}

查找要插入的子节点，如果子节点满了，就分裂，分裂完再找位置插入。

void btree_insert_nonfull(btree *T, btree_node *x, KEY_VALUE k) {
  int i = x->num - 1;
  if (x->leaf == 1) {//如果插入的是叶子节点
    while (i >= 0 && x->keys[i] > k) {//把key插入到合适的位置，因此要把大于key的全部向后移动一格
      x->keys[i+1] = x->keys[i];
      i --;
    }
    x->keys[i+1] = k;
    x->num += 1;
  } else {//如果插入的不是叶子节点，就去寻找插入的子树，如果要插入的子树满了就进行分裂
    while (i >= 0 && x->keys[i] > k) i --;
    if (x->childrens[i+1]->num == (2*(T->t))-1) {
      btree_split_child(T, x, i+1);
      if (k > x->keys[i+1]) i++;
    }
    btree_insert_nonfull(T, x->childrens[i+1], k);
  }
}

3.删除节点

如果判断出子树key数量==M/2-1, 因为要删除当前子树中的一个key，因此提前借位。

1.相邻两棵子树的根节点key数量都是M/2 -1，就合并两棵子树

2.左边子树的根节点key数量大于M/2 -1,向左边子树借一个key

3.右边子树的根节点key数量大于M/2-1,向右边子树借一个key

如下图中，是M=6的情况，要删除A，从根节点开始遍历，只有根节点可以为1。由于A在左边，于是遍历到（I）这个节点，由于（CF）这个子节点中key的数量证号为M/2 -1 =2,因此要进行借key。

进行借位，把I移下来，L移上去，把原来L的第一个子节点给新的key=I的节点的最后的子节点。

当遍历到CFI这个节点时候，发现子节点AB和子节点DE数量都是M/2 -1 ，因此进行合并

然后直接进行删除就行了

void btree_merge(btree *T, btree_node *node, int idx) {
  btree_node *left = node->childrens[idx];
  btree_node *right = node->childrens[idx+1];
  int i = 0;
  /data merge
  left->keys[T->t-1] = node->keys[idx];
  for (i = 0;i < T->t-1;i ++) {
    left->keys[T->t+i] = right->keys[i];
  }
  if (!left->leaf) {
    for (i = 0;i < T->t;i ++) {
      left->childrens[T->t+i] = right->childrens[i];
    }
  }
  left->num += T->t;
  //destroy right
  btree_destroy_node(right);
  //node 
  for (i = idx+1;i < node->num;i ++) {
    node->keys[i-1] = node->keys[i];
    node->childrens[i] = node->childrens[i+1];
  }
  node->childrens[i+1] = NULL;
  node->num -= 1;
  if (node->num == 0) {
    T->root = left;
    btree_destroy_node(node);
  }
}
void btree_delete_key(btree *T, btree_node *node, KEY_VALUE key) {
  if (node == NULL) return ;
  int idx = 0, i;
  while (idx < node->num && key > node->keys[idx]) {
    idx ++;
  }
  if (idx < node->num && key == node->keys[idx]) {
    if (node->leaf) {
      for (i = idx;i < node->num-1;i ++) {
        node->keys[i] = node->keys[i+1];
      }
      node->keys[node->num - 1] = 0;
      node->num--;
      if (node->num == 0) { //root
        free(node);
        T->root = NULL;
      }
      return ;
    } else if (node->childrens[idx]->num >= T->t) {
      btree_node *left = node->childrens[idx];
      node->keys[idx] = left->keys[left->num - 1];
      btree_delete_key(T, left, left->keys[left->num - 1]);
    } else if (node->childrens[idx+1]->num >= T->t) {
      btree_node *right = node->childrens[idx+1];
      node->keys[idx] = right->keys[0];
      btree_delete_key(T, right, right->keys[0]);
    } else {
      btree_merge(T, node, idx);
      btree_delete_key(T, node->childrens[idx], key);
    }
  } else {
    btree_node *child = node->childrens[idx];
    if (child == NULL) {
      printf("Cannot del key = %d\n", key);
      return ;
    }
    if (child->num == T->t - 1) {
      btree_node *left = NULL;
      btree_node *right = NULL;
      if (idx - 1 >= 0)
        left = node->childrens[idx-1];
      if (idx + 1 <= node->num) 
        right = node->childrens[idx+1];
      if ((left && left->num >= T->t) ||
        (right && right->num >= T->t)) {
        int richR = 0;
        if (right) richR = 1;
        if (left && right) richR = (right->num > left->num) ? 1 : 0;
        if (right && right->num >= T->t && richR) { //borrow from next
          child->keys[child->num] = node->keys[idx];
          child->childrens[child->num+1] = right->childrens[0];
          child->num ++;
          node->keys[idx] = right->keys[0];
          for (i = 0;i < right->num - 1;i ++) {
            right->keys[i] = right->keys[i+1];
            right->childrens[i] = right->childrens[i+1];
          }
          right->keys[right->num-1] = 0;
          right->childrens[right->num-1] = right->childrens[right->num];
          right->childrens[right->num] = NULL;
          right->num --;
        } else { //borrow from prev
          for (i = child->num;i > 0;i --) {
            child->keys[i] = child->keys[i-1];
            child->childrens[i+1] = child->childrens[i];
          }
          child->childrens[1] = child->childrens[0];
          child->childrens[0] = left->childrens[left->num];
          child->keys[0] = node->keys[idx-1];
          child->num ++;
          node->keys[idx-1] = left->keys[left->num-1];
          left->keys[left->num-1] = 0;
          left->childrens[left->num] = NULL;
          left->num --;
        }
      } else if ((!left || (left->num == T->t - 1))
        && (!right || (right->num == T->t - 1))) {
        if (left && left->num == T->t - 1) {
          btree_merge(T, node, idx-1);          
          child = left;
        } else if (right && right->num == T->t - 1) {
          btree_merge(T, node, idx);
        }
      }
    }
    btree_delete_key(T, child, key);
  }
}
int btree_delete(btree *T, KEY_VALUE key) {
  if (!T->root) return -1;
  btree_delete_key(T, T->root, key);
  return 0;
}

4.总结

添加节点–》分裂

删除节点–》合并

三、b+树

btree和b+tree区别

1.b+tree所有数据存储在叶子节点

2.b+tree所有叶子节点通过前后指针链起来

B树的原理与实现

一、b树定义

二、实现b树

1.定义b树节点

2.插入节点

3.删除节点

4.总结

三、b+树

热门文章

最新文章

相关课程

相关电子书