B树详解
我们知道，内存的读写速度是远远高于磁盘的读写速度。磁盘的IO成本是极高的，所以，应尽量减少磁盘的访问次数。同样量级的数据，用二叉树和B树（多叉树）存储，树的高度是不同的。树的高度决定了访问磁盘的次数。
B树的性质
一颗M阶B树T，满足以下条件
- 每个结点至多拥有M颗子树
- 根结点至少拥有两颗子树
- 除了根结点以外，其余每个分支结点至少拥有M/2课子树
- 所有的叶结点都在同一层上
- 有k课子树的分支结点则存在k-1个关键字，关键字按照递增顺序进行排序
- 关键字数量满足ceil(M/2)-1 <= n <= M-1
B树添加节点（分裂）
void btree_split_child(btree *T, btree_node *x, int i) { int t = T->t; btree_node *y = x->childrens[i]; btree_node *z = btree_create_node(t, y->leaf); z->num = t - 1; int j = 0; for (j = 0;j < t-1;j ++) { 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 --) { x->childrens[j+1] = x->childrens[j]; } x->childrens[i+1] = z; for (j = x->num-1;j >= i;j --) { x->keys[j+1] = x->keys[j]; } x->keys[i] = y->keys[t-1]; x->num += 1; } 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) { 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); } } 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); 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 { btree_insert_nonfull(T, r, key); } }
B树删除节点（借位或合并）
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->key[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; }
文章参考与<零声教育>的C/C++linux服务期高级架构线上课学习。有兴趣的同学可以了解下哦。
