Skip to content

Commit bef7a6c

Browse files
ujoyliujoyli
committed
hhh
1 parent 0b3f2ee commit bef7a6c

3 files changed

Lines changed: 174 additions & 0 deletions

File tree

‎1-树/5-B+树/eddyli/b+tree.c‎

Lines changed: 136 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,136 @@
1+
#include<string.h>
2+
#include<stdio.h>
3+
#include<stdlib.h>
4+
#include<assert.h>
5+
#include"b+tree.h"
6+
7+
int _get_index_in_parent(Node* node) {
8+
int i;
9+
Node* p = node->parent;
10+
int count = p->count;
11+
for (i = 0; i < count; i++) {
12+
if(p->children[i] == node)
13+
return i;
14+
}
15+
return -1;
16+
}
17+
int _insert(int item, int **k, int count) {
18+
int *keys;
19+
int i;
20+
for (i = 0; i < count; i++) {
21+
if (*k[i] == item)
22+
return 0;
23+
if (*k[i] > item) {
24+
keys = (int *)calloc(count+1, sizeof(int));
25+
memcpy(keys, *k, sizeof(int)*(i-1));
26+
keys[i] = item;
27+
memcpy(keys+i+1, *k+i+1, sizeof(int)*(count-i));
28+
free(*k);
29+
*k = keys;
30+
return 0;
31+
}
32+
}
33+
return -1;
34+
}
35+
36+
/*
37+
*insert node into leaf's parent
38+
*/
39+
void _insert2parent(Node* leaf, Node* node) {
40+
Node **children;
41+
int index;
42+
Node * parent = leaf->parent;
43+
int count = parent->count;
44+
45+
index = _get_index_in_parent(leaf);
46+
children = (Node**)calloc(count + 1, sizeof(Node*));
47+
memcpy(children, parent->children, sizeof(Node*) * index);
48+
children[index+1] = node;
49+
memcpy(children+index+1+1, parent->children+index+1, count-index);
50+
free(parent->children);
51+
parent->children = children;
52+
53+
_insert(leaf->keys[leaf->count-1], &parent->keys, parent->count);
54+
}
55+
56+
void _split(Node* lleaf, BPtree*tree) {
57+
int i;
58+
Node* new_parent;
59+
int count = lleaf->count;
60+
int half = count/2;
61+
62+
63+
Node* node = (Node*)calloc(1,sizeof(Node));
64+
node->keys = (int*)calloc(half, sizeof(int));
65+
node->count = half;
66+
node->next = lleaf->next;
67+
node->prev = lleaf;
68+
node->parent = lleaf->parent;
69+
70+
for (i = 0; i < half; i++) {
71+
node->keys[i] = lleaf->keys[i+half];
72+
}
73+
74+
lleaf->next = node;
75+
lleaf->count = lleaf->count-half;
76+
77+
if (lleaf->parent != NULL) {
78+
_insert2parent(lleaf, node);
79+
if (lleaf->parent->count > tree->m)
80+
_split(lleaf->parent, tree);
81+
} else {
82+
new_parent = (Node*)calloc(1, sizeof(Node*));
83+
new_parent->count = 2;
84+
new_parent->children = (Node**)calloc(2, sizeof(Node*));
85+
new_parent->keys = (int*)calloc(2, sizeof(int));
86+
new_parent->children[0] = lleaf;
87+
new_parent->children[1] = node;
88+
89+
new_parent->keys[0] = lleaf->keys[lleaf->count - 1];
90+
new_parent->keys[1] = node->keys[node->count - 1];
91+
tree->root = new_parent;
92+
}
93+
94+
}
95+
96+
97+
98+
void _append(int item, int **k, int count) {
99+
int * keys = (int*)calloc(count+1,sizeof(int));
100+
memcpy(keys, *k, sizeof(int)*count);
101+
keys[count] = item;
102+
free(*k);
103+
*k = keys;
104+
}
105+
106+
int insert(int item, BPtree* tree) {
107+
int min;
108+
int count;
109+
Node * lleaf;
110+
lleaf = tree->lleaf;
111+
count = lleaf->count;
112+
113+
if (tree->m%2 != 0)
114+
min = tree->m/2+1;
115+
116+
while(1) {
117+
if (_insert(item, &lleaf->keys, count) == 0) {
118+
lleaf->count+=1;
119+
break;
120+
}
121+
122+
if (lleaf->next == NULL) {
123+
_append(item,&lleaf->keys,count);
124+
lleaf->count+=1;
125+
break;
126+
}
127+
}
128+
129+
if (lleaf->count > tree->m) {
130+
_split(lleaf, tree);
131+
} else if(lleaf->count < min) {
132+
assert(lleaf == tree->root);
133+
}
134+
135+
return 0;
136+
}

‎1-树/5-B+树/eddyli/b+tree.h‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
//count must in {[m/2], m};
2+
typedef struct Node {
3+
int count;
4+
int *keys;
5+
struct Node **children;
6+
struct Node *next;
7+
struct Node *prev;
8+
struct Node *parent;
9+
} Node;
10+
11+
typedef struct BPtree {
12+
int m;
13+
Node *root;
14+
Node *lleaf;
15+
} BPtree;
16+
17+
int insert(int, BPtree*);

‎1-树/5-B+树/eddyli/test.c‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#include"b+tree.h"
2+
#include<string.h>
3+
4+
int main() {
5+
6+
BPtree tree;
7+
Node node;
8+
memset(&node, 0, sizeof(node));
9+
tree.m = 3;
10+
tree.root = tree.lleaf = &node;
11+
insert(1, &tree);
12+
insert(3, &tree);
13+
insert(5, &tree);
14+
insert(7, &tree);
15+
insert(9, &tree);
16+
insert(2, &tree);
17+
insert(4, &tree);
18+
insert(6, &tree);
19+
insert(8, &tree);
20+
insert(10, &tree);
21+
}

0 commit comments

Comments
 (0)