Skip to content

Commit d21f726

Browse files
ujoyliujoyli
committed
up
1 parent bef7a6c commit d21f726

1 file changed

Lines changed: 58 additions & 29 deletions

File tree

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

Lines changed: 58 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -14,15 +14,16 @@ int _get_index_in_parent(Node* node) {
1414
}
1515
return -1;
1616
}
17+
1718
int _insert(int item, int **k, int count) {
1819
int *keys;
1920
int i;
2021
for (i = 0; i < count; i++) {
21-
if (*k[i] == item)
22+
if ((*k)[i] == item)
2223
return 0;
23-
if (*k[i] > item) {
24+
if ((*k)[i] > item) {
2425
keys = (int *)calloc(count+1, sizeof(int));
25-
memcpy(keys, *k, sizeof(int)*(i-1));
26+
memcpy(keys, *k, sizeof(int)*i);
2627
keys[i] = item;
2728
memcpy(keys+i+1, *k+i+1, sizeof(int)*(count-i));
2829
free(*k);
@@ -44,22 +45,25 @@ void _insert2parent(Node* leaf, Node* node) {
4445

4546
index = _get_index_in_parent(leaf);
4647
children = (Node**)calloc(count + 1, sizeof(Node*));
47-
memcpy(children, parent->children, sizeof(Node*) * index);
48+
memcpy(children, parent->children, sizeof(Node*) * (index+1) );
4849
children[index+1] = node;
49-
memcpy(children+index+1+1, parent->children+index+1, count-index);
50+
memcpy(children+index+1+1, parent->children+index+1, count-index-1);
5051
free(parent->children);
5152
parent->children = children;
5253

5354
_insert(leaf->keys[leaf->count-1], &parent->keys, parent->count);
55+
parent->count += 1;
5456
}
5557

5658
void _split(Node* lleaf, BPtree*tree) {
5759
int i;
58-
Node* new_parent;
60+
int frends_count = 0;
61+
Node* new_parent, *tmp;
62+
5963
int count = lleaf->count;
60-
int half = count/2;
61-
6264

65+
//new node has half of orignal keys
66+
int half = count/2;
6367
Node* node = (Node*)calloc(1,sizeof(Node));
6468
node->keys = (int*)calloc(half, sizeof(int));
6569
node->count = half;
@@ -72,40 +76,57 @@ void _split(Node* lleaf, BPtree*tree) {
7276
}
7377

7478
lleaf->next = node;
79+
//just set count is ok
7580
lleaf->count = lleaf->count-half;
7681

7782
if (lleaf->parent != NULL) {
7883
_insert2parent(lleaf, node);
79-
if (lleaf->parent->count > tree->m)
80-
_split(lleaf->parent, tree);
84+
if (lleaf->parent->count > tree->m)
85+
_split(lleaf->parent, tree);
8186
} 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];
87+
new_parent = (Node*)calloc(1, sizeof(Node));
88+
tmp = lleaf;
89+
while(tmp != NULL) {
90+
frends_count += 1;
91+
tmp = tmp->next;
92+
}
93+
94+
new_parent->count = frends_count;
95+
new_parent->children = (Node**)calloc(frends_count, sizeof(Node*));
96+
new_parent->keys = (int*)calloc(frends_count, sizeof(int));
97+
tmp = lleaf;
98+
i = 0;
99+
while(tmp != NULL) {
100+
new_parent->children[i] = tmp;
101+
tmp->parent = new_parent;
102+
tmp = tmp->next;
103+
i+=1;
104+
}
105+
tmp = lleaf;
106+
i = 0;
107+
while (tmp != NULL) {
108+
new_parent->keys[i] = tmp->keys[tmp->count - 1];
109+
i+=1;
110+
tmp = tmp->next;
111+
}
91112
tree->root = new_parent;
92113
}
93-
94114
}
95115

96-
97-
98116
void _append(int item, int **k, int count) {
99-
int * keys = (int*)calloc(count+1,sizeof(int));
117+
int real = count + 1;
118+
int * keys = (int*)calloc(real, sizeof(int));
100119
memcpy(keys, *k, sizeof(int)*count);
101120
keys[count] = item;
102-
free(*k);
121+
if (*k != NULL)
122+
free(*k);
103123
*k = keys;
104124
}
105125

106126
int insert(int item, BPtree* tree) {
107127
int min;
108128
int count;
129+
int index;
109130
Node * lleaf;
110131
lleaf = tree->lleaf;
111132
count = lleaf->count;
@@ -114,16 +135,24 @@ int insert(int item, BPtree* tree) {
114135
min = tree->m/2+1;
115136

116137
while(1) {
138+
//TODO:this is a liner insert, change 2 tree insert
117139
if (_insert(item, &lleaf->keys, count) == 0) {
118140
lleaf->count+=1;
119141
break;
120142
}
143+
144+
if (lleaf->next == NULL) {
145+
_append(item, &lleaf->keys, count);
146+
lleaf->count+=1;
147+
if (lleaf->parent != NULL) {
148+
//update the max value in parent
149+
index = _get_index_in_parent(lleaf);
150+
lleaf->parent->keys[index] = item;
151+
}
152+
break;
153+
}
154+
lleaf = lleaf->next;
121155

122-
if (lleaf->next == NULL) {
123-
_append(item,&lleaf->keys,count);
124-
lleaf->count+=1;
125-
break;
126-
}
127156
}
128157

129158
if (lleaf->count > tree->m) {

0 commit comments

Comments
 (0)