^-^
后端技术_磁盘存储链式的B树和B+树
最近更新：2024-09-23   |   字数总计：1.8k   |   阅读估时：9分钟   |   阅读量：次
  1. B树/B-树
    1. 性质
  2. B+树

B树/B-树

  • 背景：树的层高决定了查找的耗时，在磁盘寻址过程中二叉树耗时过高，所以采用多叉树降层高存储。
  • B树：所有的叶子节点在同一层的多叉树；

性质

  • 一颗M阶B树T，满足以下条件
  1. 每个结点至多拥有M颗子树
  2. 根结点至少拥有两棵子树
  3. 除了根节点以外，其余每个分节点至少拥有M/2颗子树
  4. 所有的叶子节点都在同一层
  5. 有k颗子树的分支节点则存在k-1个关键字，关键字按照递增顺序进行排序
  6. 关键字数量满足ceil(M/2)-1 <= n <= M-1

54

  • 添加操作难点：
  1. 根节点分裂
  2. 每次添加找最右部分的叶子节点添加，当该子节点满了之后，子节点中部分裂，子节点中间节点放到父节点中
  • 删除操作难点：
  1. 当该节点删除后数量不满足时，需要从父节点取下一个值并与右侧的节点合并
  2. 当节点满足M/2-1时仍要删除其子节点时，需要从父节点借位
  3. 当借位后假如出现了key数量不满足的情况，需要合并
  4. 假如删除的是内节点，需要将内节点先合并到叶子节点中再删除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
// #define SUB_M 3

typedef struct _btree_node{
    int *keys;
    struct _btree_node **childrens;
    int num;
    int leaf;
} btree_node;

typedef struct _btree{
    btree_node *root;
    int t; // SUB_M
} btree;

// 创建节点
btree_node* btree_create_node(int t, int leaf){
    btree_node *node = (btree_node*)calloc(1, sizeof(btree_node));
    if(node == NULL) return NULL;
    node->leaf = leaf;
    node->keys = calloc(1, (t * 2 - 1) * sizeof(int));
    node->childrens = calloc(1, 2* t* sizeof(btree_node*));
    node->num = 0;
    return node;
}

// 销毁节点
void btree_destroy_node(btree_node *node){
    free(node->childrens);
    free(node->keys);
    free(node);
}

// 创建树
void btree_create(btree *T, int t)
{
    T->t = t;
    btree_node* root = btree_create_node(t, 1);
    T->root = root;
}

// 分裂, x是待分裂的父节点，idx是x的第几个子节点，idx的这个节点才是待分裂的节点
// 最开始 x->childrens[idx] == y，x->t == t
// y 先分裂成 y 和 z ，y和z的num都变成t-1
// x->childrens[idx + 1] = z, x-> keys[idx+1] = y->keys[t-1]，其余位置都依次填满， 也就是y分裂成两个，并把中间的key合并到父节点x中
void btree_split_child(btree *T, btree_node *x, int idx){
    int t = T->t;

    btree_node *y = x->childrens[idx];
    btree_node *z = btree_create_node(t, y->leaf);
    z->num = t - 1;
    int i = 0;
    for(i = 0;i< t-1;i++){
        z->keys[i] = y->keys[t + i];
    } 
    if(y->leaf == 0){
        for(int i = 0; i<t;i++){
            z->childrens[i] = y->childrens[t + i];
        }
    }
    y->num = t-1;
    for(i = x->num;i>=idx+1;i--){
        x->childrens[i+1] = x->childrens[i];
    }
    x->childrens[idx+1] = z;
    for(i = x->num-1 ; i >= idx ; i--){
        x->keys[i+1] = x->keys[i];
    }
    x->keys[idx] = y->keys[t-1];
    x->num += 1;
}

void btree_insert(btree* T, int key){
    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);
    }
}

void btree_insert_nonfull(btree *T, btree_node* x, int key)
{
     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_merge(btree *T, btree_node *node, int idx){
    btree_node *left = x->childrens[idx];
    btree_node *right = x->childrens[idx+1];

    left->keys[T->t-1] = node->keys[idx];
    int i = 0;
    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;
    btree_destroy_node(right);
    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, int 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){
            // 直接删掉这个key
            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;
			}
        }else if(node->childrens[idx]->num >= T->t){
            btree_node *left = node->childrens[idx];
			node->keys[idx] = left->keys[left->num - 1];// 将左侧最后一个key提上来
			btree_delete_key(T, left, left->keys[left->num - 1]);// 再从子节点中将已经合并到父节点中的key删除掉
        }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{
            // 左右两侧的子节点key都不够借，先合并节点再删除
            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) { // 此时child的keys已经不够删除了，需要借节点

			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;
                
                // 从left和right的子节点的个数中多的一个借一个
				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);
    }
}

B+树

  • btree/b-tree所有节点存储数据
  • b+tree叶子节点存储数据，内节点索引用的
  • 假设有100w的数据，那么btree中一部分存在了内存里，而另一部分因为内存空间问题，会存储在磁盘中，那么查询的时候，有可能会有多次磁盘寻址的情况；而b+tree我们可以只将索引存储在内存中，通过一次磁盘索引就取出数据；
2024-03-30 该篇文章被 Cleofwine 归为分类: 服务端

上一篇：后端技术_海量数据去重的Hash与BloomFilter 下一篇：后端技术_随处可见的红黑树
© 2023-2026 Cleofwine / Email / GitHub / 浙ICP备2024136127号
🌙赠我弯弯一枚月，也赠予我晚星⭐ 本站由Hexo驱动｜使用Hexo-theme-A4主题