一、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所有叶子节点通过前后指针链起来
