一直没有找到实现的代码，前段时间写了一个，数据库里的索引就是用的整个东西实现的
1 /* btree implementation example ,any bug send mail to serenaiad@126.com
2
3 You can modify,destribute this code , please reserve this note when destribute this code.
4 */
5 #include <stdio.h>
6 #include <stdlib.h>
7
8
9 #define NODESIZE 3 //number of values each node
10 #define TOTALNODES 100 //number of nodes
11
12
13 typedef enum {
14 inner,leaf
15 } nodetype;
16
17 typedef struct{
18 int nodeindex;
19 int valueindex;
20 int pointer;
21 } valuelocation;
22
23 typedef struct{
24 nodetype type;
25 int valuecount;
26 int values[NODESIZE];
27 int pointers[NODESIZE+1];
28 } node;
29
30 int freenode; //the first free node
31 int rootnode; //root node
32 node nodes[TOTALNODES]; //nodes array
33
34
35 int CreateBtree();
36 int LoadBtree();
37 int WriteBtree();
38 int InsertValue(int value,int pointer);
39 int DeleteValue(int value);
40 char *GetSysTime();
41
42
43 /* find the node index for new value to insert ,return -1 if the btree is empty(no value in it) */
44 int FindNewValueNode(int value,int path[]);
45
46 /* 一个中间节点中，要搜索指定的值，需要查找向那个指针所指向的节点去搜索，
47 这里返回下一级节点指针在指针数组中的index */
48 int FindValuePtIndex(int value,node* n);
49
50 /* 把一个节点，指针对插入到一个中间节点去
51 index: 这个节点的index, value: 值， pointer 指针
52 path: 从根节点到叶节点的全路径
53 */
54 void InsertPtToInnerNode(int index,int value,int pointer, int path[]);
55
56 void DeletePtInnerNode(int index,int minvalue,int pointer,int path[]);
57 void PrintBtree();
58 void PrintNode(int index);
59
60 /* 从空余节点中取一个全新的节点 */
61 int GetFreeNode();
62 int ReleaseNode(int index);
63
64 /* 查找某值，如果值存在，返回这个值所在节点的index , 如果不存在，返回 -1 */
65 valuelocation FindValue(int value);
66
67 /* 当某个根节点的最小值改变了以后，他的某个父节点的值需要调整
68 path - access path ; indexstart - 从哪一级开始 ; val - 老值 ; newval - 新值 */
69 void UpdateAncestorNodeMinValue(int path[],int posstart,int val,int newval);
70 /* 经过一个节点可以访问到的最小值 */
71 int MinValueThroughNode(int index);
72 void Usage();
73 void test();
74 int FindNodeValueIndex(int value, node* n);
75 void DeleteValueInLeafNode(node* n,int value);
76 int GetPosInAccessPath(int index , int path[]);
77 void DeletePointerInInnerNode(node* n,int index, int path[], int pointer,int minvalue);
78 //验证一个节点的的值和指针是否正确
79 int VerifyNode(int index);
80 int VerifyBtree();
81
82 int main(int argc, char* argv[])
83 {
84 valuelocation l;
85 if(argc==1)
86 {
87 Usage();
88 return 0;
89 }
90 if(strcmp(argv[1],"-create")==0)
91 CreateBtree();
92 if(strcmp(argv[1],"-i")==0)
93 {
94 LoadBtree();
95 if(InsertValue(atoi(argv[2]),atoi(argv[3]))!=0)
96 printf("Insert Value Failed.\n");
97 WriteBtree();
98 }
99 if(strcmp(argv[1],"-p")==0)
100 PrintBtree();
101 if(strcmp(argv[1],"-pn")==0)
102 {
103 LoadBtree();
104 PrintNode(atoi(argv[2]));
105 }
106 if(strcmp(argv[1],"-test")==0)
107 test();
108 if(strcmp(argv[1],"-f")==0)
109 {
110 LoadBtree();
111 l=FindValue(atoi(argv[2]));
112 if(l.nodeindex==-1 )
113 printf("Value %d not found.\n",atoi(argv[2]));
114 else
115 printf("Value %d found , pointer:%d\n",atoi(argv[2]),l.pointer);
116 }
117 if(strcmp(argv[1],"-d")==0)
118 {
119 LoadBtree();
120 if(DeleteValue(atoi(argv[2]))!=0)
121 printf("delete value failed.\n");
122 WriteBtree();
123 }
124 if(strcmp(argv[1],"-verify")==0)
125 {
126 LoadBtree();
127 VerifyBtree();
128 }
129 return 0;
130 }
131
132 int CreateBtree()
133 {
134 FILE* f;
135 node n;
136 int itmp;
137 int i;
138 if((f=fopen("btree.dat","w"))==NULL)
139 {
140 printf("Can't open file!\n");
141 return 1;
142 }
143 freenode=0;
144 rootnode=-1;
145 fwrite(&freenode,1,sizeof(int),f);
146 fwrite(&rootnode,1,sizeof(int),f);
147 for (i=0;i<TOTALNODES;i++)
148 {
149 n.pointers[NODESIZE]=i+1;
150 if(i==(TOTALNODES-1))
151 n.pointers[NODESIZE]=-1;
152 fwrite(&n,1,sizeof(n),f);
153 }
154 fclose(f);
155 }
156
157 void Usage()
158 {
159 printf("Usage: btree -create | -i value | -d value | -e value\n");
160 printf("-create : create new btree file.\n");
161 printf("-p : print btree.\n");
162 printf("-pn nodeindex : print node nodeindex\n");
163 printf("-i value : insert new value.\n");
164 printf("-d value : delete a value.\n");
165 printf("-f value : find if value exists.\n");
166 printf("-verify : verify if the btree is correct.\n");
167 }
168
169 int LoadBtree()
170 {
171 FILE* f;
172 if((f=fopen("btree.dat","r"))==NULL)
173 {
174 printf("Can't open file.\n");
175 return 1;
176 }
177 fread(&freenode,1,sizeof(int),f);
178 fread(&rootnode,1,sizeof(int),f);
179 fread(nodes,1,sizeof(node)*TOTALNODES,f);
180 fclose(f);
181 return 0;
182 }
183 int WriteBtree()
184 {
185 FILE* f;
186 if((f=fopen("btree.dat","w"))==NULL)
187 {
188 printf("Can't open file.\n");
189 return 1;
190 }
191 fwrite(&freenode,1,sizeof(int),f);
192 fwrite(&rootnode,1,sizeof(int),f);
193 fwrite(nodes,1,sizeof(node)*TOTALNODES,f);
194 fclose(f);
195 return 0;
196 }
197
198 int InsertValue(int value,int pointer)
199 {
200 node* n;
201 node* newNode;
202 node* pn;
203 int i,inode,insertPos,ni,pi;
204 int tmpvalues[NODESIZE+1];
205 int tmppointers[NODESIZE+1];
206 int halfsize=(NODESIZE+1)/2;
207 int path[101];
208 int pathindex;
209 int minval,newval;
210 int pos;
211
212 insertPos=-1;
213 inode=FindNewValueNode(value,path); //先找出需要往那个节点里插入值
214
215 if( inode==-1) // 如果这是btree中的第一个值
216 {
217 ni=GetFreeNode();
218 n=nodes+ni;
219 rootnode=ni;
220 n->type=leaf;
221 n->valuecount=1;
222 n->values[0]=value;
223 n->pointers[0]=pointer;
224 n->pointers[NODESIZE]=-1;
225 }
226 else
227 {
228 n=nodes+inode;
229 for(i=0;i<n->valuecount;i++)
230 {
231 if(value==n->values)
232 return 1;
233 }
234 for(i=1;i<=path[0];i++)
235 {
236 if(inode==path)
237 pathindex=i;
238 }
239 if (n->valuecount==NODESIZE) // the leaf node needs to split
240 {
241 ni=GetFreeNode();
242 newNode=nodes+ni;
243 newNode->type=leaf;
244 newNode->valuecount=NODESIZE+1-halfsize;
245 for(i=0;i<NODESIZE;i++)
246 {
247 if(value< n->values)
248 {
249 insertPos=i;
250 break;
251 }
252 }
253 if(insertPos==-1)
254 insertPos=NODESIZE;
255 if (insertPos==0)
256 {
257 minval=n->values[0];
258 newval=value;
259 UpdateAncestorNodeMinValue(path,pathindex-1,minval,newval);
260 }
261 for(i=0;i<insertPos;i++)
262 {
263 tmpvalues=n->values;
264 tmppointers=n->pointers;
265 }
266 tmpvalues[insertPos]=value;
267 tmppointers[insertPos]=pointer;
268 for(i=NODESIZE-1;i>=insertPos;i--)
269 {
270 tmpvalues[i+1]=n->values;
271 tmppointers[i+1]=n->pointers;
272 }
273 for(i=0;i<halfsize;i++)
274 {
275 n->values=tmpvalues;
276 n->pointers=tmppointers;
277 }
278 n->valuecount=halfsize;
279 for(i=halfsize;i<NODESIZE+1;i++)
280 {
281 newNode->values[i-halfsize]=tmpvalues;
282 newNode->pointers[i-halfsize]=tmppointers;
283 }
284 newNode->pointers[NODESIZE]=n->pointers[NODESIZE];
285 n->pointers[NODESIZE]=ni;
286 if(inode==path[1]) // if the node is root node
287 {
288 pi=GetFreeNode();
289 rootnode=pi; // change new root node
290 pn=nodes+pi;
291 pn->type=inner;
292 pn->valuecount=1;
293 pn->values[0]=newNode->values[0];
294 pn->pointers[0]=inode;
295 pn->pointers[1]=ni;
296 }
297 else // 如果这个叶节点不是根节点，那么需要向它的父节点插入值和指针
298 {
299 InsertPtToInnerNode(path[pathindex-1],newNode->values[0],ni,path);
300 }
301
302 }
303 else // the leaf node has enough space
304 {
305 for(i=0;i < n->valuecount;i++)
306 {
307 if(value < n->values)
308 {
309 insertPos=i;
310 break;
311 }
312 }
313 if(insertPos==-1)
314 {
315 insertPos=n->valuecount;
316 }
317 if(insertPos==0)
318 {
319 minval=n->values[0];
320 newval=value;
321 }
322 for(i=n->valuecount;i>insertPos;i--)
323 {
324 n->values=n->values[i-1];
325 n->pointers=n->pointers[i-1];
326 }
327 n->values[insertPos]=value;
328 n->pointers[insertPos]=pointer;
329 n->valuecount=n->valuecount+1;
330 if(insertPos==0)
331 {
332 UpdateAncestorNodeMinValue(path,pathindex-1,minval,newval);
333 }
334 }
335 }
336 return 0;
337 }
338
Serenaiad 回复于：2006-12-23 01:59:23
339
340 int FindNewValueNode(int value,int path[])
341 {
342 node* n;
343 node* root;
344 int i,ni;
345 if (rootnode== -1 )
346 return -1;
347 else
348 {
349 path[0]=1;
350 path[1]=rootnode;
351 root=nodes+rootnode;
352 n=root;
353 ni=rootnode;
354 while(n->type==inner)
355 {
356 ni=n->pointers[FindValuePtIndex(value,n)];
357 n=nodes+ni;
358 path[0]=path[0]+1;
359 path[path[0]]=ni;
360 }
361 return ni;
362 }
363 }
364
365 int FindValuePtIndex(int value,node* n)
366 {
367 int count;
368 int i;
369 count=n->valuecount;
370
371 for(i=0;i<count;i++)
372 {
373 if(value < n->values)
374 return i;
375 }
376 return count;
377 }
378
379
380 int GetFreeNode()
381 {
382 node* n;
383 int i;
384 n=nodes+freenode;
385 i=freenode;
386 freenode=n->pointers[NODESIZE];
387 return i;
388 }
389
390 void InsertPtToInnerNode(int index,int value,int pointer, int path[])
391 {
392 node* n;
393 node* newnode;
394 node* parentnode;
395 int tmpvalues[NODESIZE+1];
396 int tmppointers[NODESIZE+1+1];
397 int halfsize;
398 int i,j,insertpos,ni,pi; // ni-new node index, pi-parent node index
399 int pathindex;
400 int valueinsert; //the value insert to parent node
401
402 n=nodes+index;
403 insertpos=-1;
404 halfsize=(NODESIZE+1)/2;
405 if(n->valuecount==NODESIZE) // the node is full, need to split
406 {
407 ni=GetFreeNode();
408 newnode=nodes+ni;
409 newnode->type=inner;
410 for(i=0;i<NODESIZE;i++)
411 {
412 if(value<n->values)
413 {
414 insertpos=i;
415 break;
416 }
417 }
418 if(insertpos==-1)
419 insertpos=NODESIZE;
420
421 tmppointers[0]=n->pointers[0];
422 for(i=0;i<insertpos;i++)
423 {
424 tmpvalues=n->values;
425 tmppointers[i+1]=n->pointers[i+1];
426 }
427 tmpvalues[insertpos]=value;
428 tmppointers[insertpos+1]=pointer;
429 for(i=insertpos;i<NODESIZE;i++)
430 {
431 tmpvalues[i+1]=n->values;
432 tmppointers[i+1+1]=n->pointers[i+1];
433 }
434
435 n->valuecount=halfsize;
436 for(i=0;i<halfsize;i++)
437 {
438 n->values=tmpvalues;
439 n->pointers[i+1]=tmppointers[i+1];
440 }
441
442 for(i=halfsize;i<NODESIZE+1;i++)
443 {
444 newnode->values[i-halfsize]=tmpvalues;
445 newnode->pointers[i-halfsize]=tmppointers[i+1];
446 }
447 newnode->valuecount=NODESIZE+1-halfsize; //中间的那个值插入到上级节点
448 valueinsert=newnode->values[0];
449 for(i=1;i<newnode->valuecount;i++)
450 {
451 newnode->values[i-1]=newnode->values;
452 }
453 newnode->valuecount=newnode->valuecount-1;
454
455 for(i=1 ;i<=path[0];i++)
456 {
457 if(index==path)
458 pathindex=i;
459 }
460 if(pathindex==1) // if this inner node is root node
461 {
462 pi=GetFreeNode();
463 rootnode=pi;
464 parentnode=nodes+pi;
465 parentnode->type=inner;
466 parentnode->valuecount=1;
467 parentnode->values[0]=valueinsert;
468 parentnode->pointers[0]=index;
469 parentnode->pointers[1]=ni;
470 }
471 else
472 InsertPtToInnerNode(path[pathindex-1],valueinsert,ni,path);
473 }
474 else // if the node doesn't need to split
475 {
476 for(i=0;i< n->valuecount;i++)
477 {
478 if (value < n->values)
479 {
480 insertpos=i;
481 break;
482 }
483 }
484 if(insertpos==-1)
485 insertpos=n->valuecount;
486
487 for(i=n->valuecount;i > insertpos;i--)
488 {
489 n->values=n->values[i-1];
490 n->pointers[i+1]=n->pointers;
491 }
492 n->values[insertpos]=value;
493 n->pointers[insertpos+1]=pointer;
494 n->valuecount=n->valuecount+1;
495 }
496 }
497
498 void PrintBtree()
499 {
500 LoadBtree();
501 printf("BTree: Root:%d \n\n",rootnode);
502 if(rootnode!=-1)
503 PrintNode(rootnode);
504 }
505
Serenaiad 回复于：2006-12-23 02:00:33
506 void PrintNode(int index)
507 {
508 node* n;
509 int i;
510 n=nodes+index;
511 if(n->type==inner)
512 printf("NodeIndex:%d ValueCount:%d, type:InnerNode\n",index,n->valuecount);
513 else
514 printf("NodeIndex:%d ValueCount:%d, type:LeafNode\n",index,n->valuecount);
515 if (n->type==leaf)
516 printf("Values: ");
517 else
518 printf("Values: ");
519 for(i=0;i< n->valuecount;i++)
520 printf(" %4d ",n->values);
521 printf("\n");
522 printf("Pointers: ");
523 if(n->type==inner)
524 {
525 for(i=0;i< n->valuecount+1;i++)
526 printf(" %4d ",n->pointers);
527 }
528 else
529 {
530 for(i=0;i< n->valuecount;i++)
531 printf(" %4d ",n->pointers);
532 printf("next:%d",n->pointers[NODESIZE]);
533 }
534
535 printf("\n\n");
536 if( n->type == inner)
537 {
538 for(i=0;i< n->valuecount+1 ;i++)
539 PrintNode(n->pointers);
540 }
541 }
542
543 void test()
544 {
545 int i,j;
546 int ni;
547 int minval;
548 node* n;
549 int values[100];
550 valuelocation v;
551 int valuecount;
552 int index;
553 int val;
554 printf("RAND_MAX:%d\n",RAND_MAX);
555
556 LoadBtree();
557 srand(atoi(GetSysTime()));
558 //random();
559 for(i=0;i<100;i++)
560 {
561
562 while(1)
563 {
564
565 val=rand();
566 v=FindValue(val);
567 if(v.nodeindex==-1)
568 {
569 InsertValue(val,val);
570 break;
571 }
572 }
573 }
574 if(VerifyBtree()!=0)
575 return ;
576 WriteBtree();
577
578
579 minval=MinValueThroughNode(rootnode);
580 v=FindValue(minval);
581 ni=v.nodeindex;
582 n=nodes+ni;
583 i=0;
584 printf("values: \n");
585 while(n!=NULL)
586 {
587 for(j=0;j<n->valuecount;j++)
588 {
589 values=n->values[j];
590 printf("value %d is %d\n",i,values);
591 i++;
592 }
593
594 if(n->pointers[NODESIZE]==-1)
595 n=NULL;
596 else
597 n=nodes+n->pointers[NODESIZE];
598 }
599 printf("\n");
600 //begin to delete
601 valuecount=100;
602 while(valuecount>10)
603 {
604 i=random();
605 i=rand();
606 index=i/(RAND_MAX/valuecount);
607 if(index>valuecount-1)
608 continue;
609 v=FindValue(values[index]);
610 if(v.nodeindex==-1)
611 {
612 printf("value %d not in btree.\n",values[index]);
613 return ;
614 }
615 printf("Delete %d value:%d\n",index,values[index]);
616 if(DeleteValue(values[index])!=0)
617 {
618 printf("delete value failed\n");
619 return ;
620 }/*
621 v=FindValue(32085);
622 if(v.nodeindex==-1)
623 {
624 printf("value %d not in btree.\n",32085);
625 return ;
626 }*/
627
628 for(i=index;i<valuecount-1;i++)
629 values=values[i+1];
630 if(VerifyBtree()!=0)
631 return;
632 WriteBtree();
633 valuecount--;
634
635 }
636 WriteBtree();
637 }
638
639 valuelocation FindValue(int value)
640 {
641 int i,vi;
642 node* n;
643 int path[101];
644 valuelocation v;
645 v.nodeindex=-1;
646 vi=FindNewValueNode(value,path);
647 if(vi==-1)
648 {
649 return v;
650 }
651 else
652 {
653 n=nodes+vi;
654 for(i=0;i<n->valuecount;i++)
655 {
656 if(n->values==value)
657 {
658 v.nodeindex=vi;
659 v.valueindex=i;
660 v.pointer=n->pointers;
661 return v;
662 }
663 }
664 return v;
665 }
666 }
667
668 int DeleteValue(int value)
669 {
670 int i,j,ni,pi,bi; //ni - node index; pi - parent node index ; bi - borther node index
671 int vi ; // vi - value index int he pointers array
672 int halfsize=(NODESIZE+1)/2;
673 int minval,pminval,nminval;
674 int newval;
675 int valuepos;
676
677 node* n;
678 node* pn; // parent node
679 node* prenode=NULL; // previous brother node
680 node* nextnode=NULL; //next brother node
681
682 // 本节点和前一个兄弟节点还是和后一个兄弟节点发生关系（借值或合并) P ,N
683 char NodeProc; // P - previous node N- next node
684 char MethodProc; // M-merge B-borrow
685 int path[101];
686 valuelocation v;
687
688 ni=FindNewValueNode(value,path);
689 if( ni==-1)
690 {
691 return 1;
692 }
693 else
694 {
695 n=nodes+ni;
696 valuepos=-1;
697 for(i=0;i<n->valuecount;i++)
698 {
699 if(value==n->values)
700 {
701 valuepos=i;
702 break;
703 }
704 }
705 if(valuepos==-1)
706 return 1;
707 if(n->valuecount > halfsize) // the node have enough value
708 {
709 if(value==n->values[0]) // 如果删掉的这个值是这个节点的最小值,那么需要update 他的某个父节点的值
710 {
711 minval=n->values[0];
712 newval=n->values[1];
713 if(path[0]!=1) // if this node is not root node
714 UpdateAncestorNodeMinValue(path,path[0]-1,minval,newval);
715 }
716 DeleteValueInLeafNode(n,value);
717 return 0;
718 }
719 else// if the node doesn't have enough values;
720 {
721 vi=FindNodeValueIndex(value,n);
722 if(path[0]==1) // this leaf node is root node
723 {
724 DeleteValueInLeafNode(n,value);
725 if(n->valuecount==0)
726 {
727 ReleaseNode(ni);
728 rootnode=-1;
729 }
730 return 0;
731 }
732 else // if the node is not root node
733 {
734
735 pi=path[path[0]-1];
736 pn=nodes+pi; // get parent node
737 for(i=0 ;i<NODESIZE+1;i++)
738 {
739 if(pn->pointers==ni)
740 {
741 if(i!=0)
742 {
743 bi=pn->pointers[i-1];
744 prenode=nodes+pn->pointers[i-1];
745 }
746 if(i!=NODESIZE)
747 {
748 bi=pn->pointers[i+1];
749 nextnode=nodes+pn->pointers[i+1];
750 }
751 break;
752 }
753 }
754 if(prenode!=NULL)
755 {
756 NodeProc='P';
757 if(prenode->valuecount > halfsize)
758 MethodProc='B';
759 else
760 MethodProc='M';
761 }
762 else
763 {
764 NodeProc='N';
765 if(nextnode->valuecount > halfsize)
766 MethodProc='B';
767 else
768 MethodProc='M';
769 }
770 //printf("NodeProc: %c ,MethodProc:%c\n",NodeProc,MethodProc);
771 if(MethodProc=='B') //如果需要借值
772 {
773 if(NodeProc=='P') //如果从前一个节点借
774 {
775 if(value==n->values[0])
776 {
777 minval=value;
778 newval=n->values[1];
779 UpdateAncestorNodeMinValue(path,path[0]-1,minval,newval);
780 }
781 DeleteValueInLeafNode(n,value);
782
783 for(i=n->valuecount ; i>=1 ;i--)
784 {
785 n->values=n->values[i-1];
786 n->pointers=n->pointers[i-1];
787 }
788 minval=n->values[0];
789 newval=prenode->values[prenode->valuecount-1];
790 n->values[0]=prenode->values[prenode->valuecount-1];
791 n->pointers[0]=prenode->pointers[prenode->valuecount-1];
792 n->valuecount=n->valuecount+1;
793 UpdateAncestorNodeMinValue(path,path[0]-1,minval,newval);
794 prenode->valuecount=prenode->valuecount-1;
795 }
796 else //如果需要从后一个节点借
797 {
798 if(value==n->values[0]) //如果这个删除的最小值
799 {
800 newval=n->values[1];
801 UpdateAncestorNodeMinValue(path,path[0]-1,value,newval);
802 }
803 DeleteValueInLeafNode(n,value);
804
805 //处理下一个节点
806 minval=nextnode->values[0];
807 newval=nextnode->values[1];
808 n->values[n->valuecount]=nextnode->values[0];
809 n->pointers[n->valuecount]=nextnode->pointers[0];
810 n->valuecount=n->valuecount+1;
811 DeleteValueInLeafNode(nextnode,minval);
812 UpdateAncestorNodeMinValue(path,path[0]-1,minval,newval);// 下一个节点的最小值也改变了，所以需要也update 父节点
813 }
814 return 0;
815 }
816 else //如果合并节点
817 {
818 if(NodeProc=='P') // 如果和前一个节点合并
819 {
820 if(value==n->values[0])
821 {
822 newval=n->values[1];
&nbs |
