外部归并排序算法,使用B+树，分块整理等

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <time.h> #include <math.h> #define M 128 //建M阶B+树，根据题意定义M的大小,M=1024/8-1 struct date { int year,month,day; }; struct record { long key1,key2,key3,key4,key5; double a1,a2,a3; char ch1,ch2; struct date time1,time2,time3; char str[85]; }; struct node // 定义B+树的非叶子节点节点 { int d; //节点中键的数目 long nodekey[M-1]; // 节点中的键 struct node *child[M]; // 指向子节点的指针 }; struct slot //块的索引 { int offset; int length; }; const int staticsize = 5*sizeof(long) + 3*sizeof(double) + 2*sizeof(char) + 3*6 + 3*sizeof(char); const int recordlength=sizeof(struct record); const int slotlen=sizeof(struct slot); //定义索引的长度 int level=0; //树的高度 struct node *root; //树的根 int temp_level; //树的暂时高度 记得在使用前要初始化。。 struct node *t1; //用来放分裂出来的节点 struct node *t2; struct node *newchild; void insert(struct node *r, struct node *page) //插入（加载）一页的函数,只支持顺序插入 { int i,j; if(temp_level>1) // r是一个非次叶子节点 { for(i=0;i<(*r).d;i++); //找到满足子节点的child[i] temp_level--; insert((*r).child[i],page); //递归插入页 if((*newchild).nodekey[0]==-1) { return; //如果子节点为空，说明没有分裂出新节点来，故插入成功，程序结束 } else //分裂出新节点来，处理之 { if((*r).d<(M-1)) //节点中有空间就可以放入newchild { (*r).nodekey[(*r).d]=(*newchild).nodekey[0]; //由于数据已经排好序，所以就直接插入就ok了 (*r).d++; (*r).child[(*r).d]=(*newchild).child[0]; (*newchild).nodekey[0]=-1; return; } else //节点没有空间时的处理 { t2=(struct node *)malloc(sizeof(struct node)); // 申请空间用于放分裂出来的新节点 for(i=(M-2)/2+1,j=0;i<(M-1);i++,j++) //分裂节点 { (*t2).nodekey[j]=(*r).nodekey[i]; (*t2).child[j]=(*r).child[i]; } (*t2).child[j]=(*r).child[i]; (*r).d=(M-2)/2; (*t2).nodekey[j]=(*newchild).nodekey[0]; //把原来要插入的newchild插到新节点后面 (*t2).child[j+1]=(*newchild).child[0]; (*t2).d=j+1; // 要弹出去一个，又插入一个新的，所以。。。 (*newchild).nodekey[0]=(*r).nodekey[(M-2)/2]; //把中间的码弹到新的newchild节点去 (*newchild).child[0]=t2; if(r==root) //假如r是根 { struct node *temproot2; temproot2=(struct node *)malloc(sizeof(struct node)); //申请一个指针空间来放索引 (*temproot2).nodekey[0]=(*newchild).nodekey[0]; (*temproot2).child[0]=r; (*temproot2).child[1]=t2; (*temproot2).d=1; root=temproot2; //根节点转变成新节点 level++; } return; } } } else if(temp_level==0) //索引都没的时候 { struct node *temproot; //创建临时新的根 temproot=(struct node *)malloc(sizeof(struct node)); //申请一个指针空间来放索引 (*temproot).child[0]=page; //把叶子节点指针转化成节点指针赋给根 (*temproot).d=0; root=temproot; level++; return; } else // r是一个次叶子节点 temp_level=1的时候 { if((*r).d<(M-1)) { (*r).nodekey[(*r).d]=(*page).nodekey[0]; //由于数据已经排好序，所以就直接插入就ok了 (*r).d++; (*r).child[(*r).d]=page; (*newchild).nodekey[0]=-1; return; } else // 次叶子节点没有空间的时候 { t1=(struct node *)malloc(sizeof(struct node)); for(i=(M-2)/2+1,j=0;i<(M-1);i++,j++) //分裂节点 { (*t1).nodekey[j]=(*r).nodekey[i]; (*t1).child[j]=(*r).child[i]; } (*t1).child[j]=(*r).child[i]; (*r).d=(M-2)/2; (*t1).nodekey[j]=(*page).nodekey[0]; //把数据插到新节点中 (*t1).child[j+1]=page; (*t1).d=j+1; // 要弹出去一个，又插入一个新的，所以。。。 (*newchild).nodekey[0]=(*r).nodekey[(M-2)/2]; //把中间的码弹到新的newchild节点去 (*newchild).child[0]=t1; if(r==root) //假如r是根 { struct leaf *temp; struct node *temproot1; temproot1=(struct node *)malloc(sizeof(struct node)); //申请一个指针空间来放索引 (*temproot1).nodekey[0]=(*newchild).nodekey[0]; (*temproot1).child[0]=r; (*temproot1).child[1]=t1; (*temproot1).d=1; root=temproot1; //根节点转变成新节点 level++; return; } return; } } } struct node *search(struct node *r,long k) //搜索函数，用于找到数据项 { int i; printf("经过了首键为%ld的索引页!\n",(*r).nodekey[0]); // 按题目要求输出搜索时的过程页 if(temp_level==0)return NULL; else if(temp_level==1) { for(i=0;i<(*r).d&&k>=(*r).nodekey[i];i++); //当只有一个节点索引时 return (*r).child[i]; } else //否则 { for(i=0;i<(*r).d&&k>=(*r).nodekey[i];i++); // 找到满足child[i] temp_level--; return search((*r).child[i],k); } } struct node *find(long k) //同上，只是把根作为参数传入 { return search(root,k); } int main() // 主函数，实现文件读取，找打记录，建树，搜索记录等功能 { FILE *input,*output; int i,j,len1,sign=0; // current用于记录当前的页码(pageID) long current=0; long tempkey; struct record temp; struct node *templeaf2; struct node tempnode; struct node *r; struct slot index; clock_t start,finish; //用来计算整理的时间 double totaltime1,totaltime2; printf("开始块加载B+树！\n"); start=clock(); root=NULL; //初始化根 input=fopen("organize.dat","rb"); newchild=(struct node *)malloc(sizeof(struct node)); while(!feof(input)) { struct node *templeaf; templeaf=(struct node*)malloc(sizeof(struct node)); fseek(input,current*1024,0); if(feof(input))break; fread(&temp.key1,4,1,input); (*templeaf).nodekey[0]=temp.key1; (*templeaf).nodekey[1]=current; (*newchild).nodekey[0]=-1; temp_level=level; r=root; insert(r,templeaf); current++; } printf("建树成功！\n"); finish= clock(); totaltime1=(double)((finish-start)/CLOCKS_PER_SEC); printf("建树总共用时：%lf秒.\n",totaltime1); printf("树的高度为%d\n",level); printf("\n"); //完成搜索的功能 printf("请输入要搜索的key："); scanf("%ld",&tempkey); start=clock(); temp_level=level; //开始搜索前设置临时树的高度全局变量 templeaf2=find(tempkey); //在B+树搜索数据 printf("找到首键为%ld的数据快\n",(*templeaf2).nodekey[0]); printf("找到PAGEID为%ld的数据快\n",(*templeaf2).nodekey[1]); i=1; while(1) { fseek(input,(*templeaf2).nodekey[1]*1024,0); //从文件中找到数据位置 fseek(input,(1024-i*slotlen),1); fread(&index,slotlen,1,input); if(index.offset==-1)break; //遇到结束标志，该页记录读完，退出 fseek(input,((*templeaf2).nodekey[1]*1024+index.offset),0); //从文件中找到数据位置 fread(&temp,index.length,1,input); if(tempkey==temp.key1) { sign=1; printf("数据已找到，具体信息如下：\n"); printf("%ld|%ld|%ld|%ld|%ld|%.2lf|%.2lf|%.2lf|%c|%c|%d-%02d-%02d|%d-%02d-%02d|%d-%02d-%02d|%s\n",temp.key1,temp.key2,temp.key3,temp.key4,temp.key5,temp.a1,temp.a2,temp.a3,temp.ch1,temp.ch2,temp.time1.year,temp.time1.month,temp.time1.day,temp.time2.year,temp.time2.month,temp.time2.day,temp.time3.year,temp.tim