# B树——磁盘链式存储数据结构

## B树详解

### B树的性质

1. 每个结点至多拥有M颗子树
2. 根结点至少拥有两颗子树
3. 除了根结点以外，其余每个分支结点至少拥有M/2课子树
4. 所有的叶结点都在同一层上
5. 有k课子树的分支结点则存在k-1个关键字，关键字按照递增顺序进行排序
6. 关键字数量满足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;
}

|
2月前
|

52 2
|
2月前
|

【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
【数据结构和算法】--- 二叉树（4）--二叉树链式结构的实现（2）
21 0
|
2月前
|

Python中使用列表和字典来存储和处理复杂的数据结构
Python中使用列表和字典来存储和处理复杂的数据结构
30 4
|
2月前
【数据结构】链式二叉树的层序遍历
【数据结构】链式二叉树的层序遍历
27 5
|
2月前
|

【数据结构】手把手分析：链式二叉树的实现
【数据结构】手把手分析：链式二叉树的实现
25 5
|
2月前
|

【数据结构】最最基础的链式结构——单链表，还不会你就吃大亏了！
【数据结构】最最基础的链式结构——单链表，还不会你就吃大亏了！
29 5
|
2月前
|

JavaScript中的对象是数据结构，存储键值对，键为字符串，值可为任意类型，包括函数（作为方法）
【6月更文挑战第25天】JavaScript中的对象是数据结构，存储键值对，键为字符串，值可为任意类型，包括函数（作为方法）。
29 2
|
2月前
|

JavaScript中的数组是核心数据结构，用于存储和操作序列数据
【6月更文挑战第22天】JavaScript中的数组是核心数据结构，用于存储和操作序列数据。创建数组可以使用字面量[]或new Array()。访问元素通过索引，如myArray[0]，修改同样如此。常见方法包括：push()添加元素至末尾，pop()移除末尾元素，shift()移除首元素，unshift()添加到开头，join()连接为字符串，slice()提取子数组，splice()进行删除、替换，indexOf()查找元素位置，sort()排序数组。还有其他如reverse()、concat()等方法。
118 2
|
1月前
|

geopandas是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于pandas库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。GeoDataFrame是geopandas中的核心数据结构，它类似于pandas的DataFrame，但包含了一个额外的地理列（通常是geometry列），用于存储地理空间数据。
geopandas是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于pandas库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。GeoDataFrame是geopandas中的核心数据结构，它类似于pandas的DataFrame，但包含了一个额外的地理列（通常是geometry列），用于存储地理空间数据。
26 0
|
2月前
|

【Chrome插件】如何在Chrome插件开发中处理复杂数据结构的存储？

80 5