数据库-实验4-数据库操作的实现算法-B树-索引查找

实验四数据库操作的实现算法1、实验目的：掌握B树索引查找算法，多路归并排序算法，并用高级语言实现2、实验内容：选择熟悉的高级语言设计和实现程序完成下列功能：1）随机生成具有1,000,000条记录的文本文件，每条记录的长度为128字节，其中固定包含一个整型属性A，属性A的值随机生成。其他属性可以自己定义。2）针对属性A，用高级语言实现两趟多路归并排序算法。要求在内存分配8M空间用于外部归并排序3）以属性A为键值，实现B树索引。完成索引的插入，删除和查找。3、实验报告截屏给出实验结果给出算法流程图由于共有1000000个元组，每个元组128B，因此总大小为128M，又内存限制为8M，则至少要分成128M/8M=16组。为了尽可能的减少I/O次数,因此采用16路归并的方法；为了减少归并的时间，采用败者树，在O(lgn)的时间复杂度内选出最小的Ａ属性元组，这种方法从划分到归并，读入两次，写出两次，最少的I/O次数是4*1000000.附上程序代码1、生成1000000个128字节的元组代码：#includeiostream#includefstream#includectime#includecstdlibusingnamespacestd;constintN=1000000;stringRandomChineseCharacters(){//srand((unsigned)time(NULL));inthigh=0xd7-0xc1;//16-55区汉字intlow=0xfe-0xa1;inthigh_zn;intlow_zn;charname[3];name[2]='\0';strings;for(inti=0;i60;i++){high_zn=rand()%high+0xc1;low_zn=rand()%low+0xa1;name[0]=high_zn;name[1]=low_zn;s.append(name);}returns;}intmain(){ofstreamofp(example2.txt);if(!ofp.is_open()){coutcan'topenfile!endl;return0;}srand((unsigned)time(NULL));intt1=0,t2=0;//4+stringname;for(inti=1;i=N;i++){t1=rand();t2=i;name=RandomChineseCharacters();//coutnamesizeof(t1)sizeof(t2)name.length()endl;ofpt1t2nameendl;}return0;}2、16组快速排序和16路归并排序的代码//Extenal_Merge_Sort.cpp:定义控制台应用程序的入口点。//#includestdafx.h#includeiostream#includefstream#includectime#includecstdlib#includestring.h#includeassert.husingnamespacestd;typedefstructData{intdata;intnum;charname[121];}Data;//利用败者树constintN=1000000;//数据总量constintFILE_NUM=16;//文件个数constintMAX_PART=62500;//每一个文件大小FILE*fpreads[FILE_NUM];constintMIN=-1;//最小值,必须比要排序数字的最小值要小，否则出错constintMAX=9999999;//最大值,必须比要排序数字的最大值要大，否则出错intresult=0;intcmp(constvoid*a,constvoid*b){if((*(Data*)a).data(*(Data*)b).data)return1;elseif((*(Data*)a).data(*(Data*)b).data)return-1;elsereturn0;}//从unsort_data.txt中读取数据intread_data(FILE*fp,Data*array,intN){intlength=0;for(inti=0;iMAX_PART&&(EOF!=fscanf_s(fp,%d%d%s\n,&array[i].data,&array[i].num,array[i].name,_countof(array[i].name)));i++){length++;}returnlength;}//打开data0.txt-data9.txt这10个文件FILE*open_file(intcount,char*mode){FILE*fpwrite=NULL;charfilename[20];memset(filename,0,20);sprintf_s(filename,20,data%d.txt,count);fopen_s(&fpwrite,filename,mode);assert(fpwrite!=NULL);returnfpwrite;}//向data0.txt-data9.txt这10个文件写入排好序的数据voidwrite_data(Data*array,intN,intcount){FILE*fpwrite=open_file(count,w);inti=0;for(i=0;iN;i++){fprintf(fpwrite,%d%d%s\n,array[i].data,array[i].num,array[i].name);}fprintf(fpwrite,%d%d%s\n,MAX,array[i-1].num,array[i-1].name);//在每个文件最后写入一个最大值，表示文件结束fclose(fpwrite);}//内部排序，调用16次快速排序，产生data0.txt-data16.txt这10个有序文件voidinterior_sort(void){clock_tbegin=clock();FILE*fpread=NULL;fopen_s(&fpread,unsort_data.txt,r);assert(fpread!=NULL);intcount=0;Data*array=newData[MAX_PART];assert(array!=NULL);while(1){memset(array,0,sizeof(Data)*MAX_PART);intlength=read_data(fpread,array,MAX_PART);if(length==0){break;}qsort(array,length,sizeof(Data),cmp);write_data(array,length,count);count++;}delete[]array;fclose(fpread);clock_tend=clock();cout16timesQuickSortUseTime(end-begin)/CLK_TCKsendl;}//调整voidadjust(intls[],Datadata[],ints){intt=(s+FILE_NUM)/2;while(t){if(data[s].datadata[ls[t]].data){inttemp=s;s=ls[t];ls[t]=temp;}t/=2;}ls[0]=s;}voidcreate_loser_tree(intls[],Datadata[]){data[FILE_NUM].data=MIN;for(inti=0;iFILE_NUM;i++){ls[i]=FILE_NUM;}for(inti=FILE_NUM-1;i=0;i--){adjust(ls,data,i);}}voidmerge_sort_by_losertree(){clock_tbegin=clock();FILE*fpreads[FILE_NUM];//10个文件的描述符Datadata[FILE_NUM+1];//10个文件的10个当前最小数据intls[FILE_NUM];//存放败者索引的节点intindex;FILE*fpwrite=NULL;fopen_s(&fpwrite,sort_data_by_losertree.txt,w);assert(fpwrite!=NULL);for(inti=0;iFILE_NUM;i++){fpreads[i]=open_file(i,r);}for(inti=0;iFILE_NUM;i++){fscanf_s(fpreads[i],%d%d%s\n,&data[i].data,&data[i].num,data[i].name,_countof(data[i].name));}create_loser_tree(ls,data);//创建败者树while(data[ls[0]].data!=MAX){index=ls[0];fprintf(fpwrite,%d%d%s\n,data[index].data,data[index].num,data[index].name);result++;//测试数据是否全部读完。fscanf_s(fpreads[index],%d%d%s\n,&data[index].data,&data[index].num,data[index].name,_countof(data[index].name));adjust(ls,data,index);}for(inti=0;iFILE_NUM;i++){fclose(fpreads[i]);}fclose(fpwrite);clock_tend=clock();cout16PathMergeSortUseTime:(end-begin)/CLK_TCKsendl;}int_tmain(intargc,_TCHAR*argv[]){interior_sort();merge_sort_by_losertree();coutMergedData:resultendl;getchar();return0;}3、B树索引的建立、查找、删除的代码#includestdafx.h#includestdio.h#includestdlib.h#includeassert.h#includectime/***@briefthedegreeofbtree*keypernode:[M-1,2M-1]*childpernode:[M,2M]*/#defineM2#defineMaxSize1000001typedefstructbtree_node{intk[2*M-1];structbtree_node*p[2*M];intnum;boolis_leaf;}btree_node;/***@briefallocateanewbtreenode*default:is_leaf==true**@returnpointerofnewnode*/btree_node*btree_node_new();/***@briefcreateabtreeroot**@returnpointerofbtreeroot*/btree_node*btree_create();/***@briefsplitchildifnumofkeyinchildexceed2M-1**@paramparent:parentofchild*@parampos:p[pos]pointstochild*@paramchild:thenodetobesplited**@return*/intbtree_split_child(btree_node*parent,int