main.c

c语言编写的B+树

#include<stdio.h>
#include<malloc.h>

#define TDN  500 //总记录个数
#define SD  100 //每个记录所占字节（byte）(每个记录为3个int)
#define LD  1024 //数据块的块长（byte）(1024/32=32)
#define ND  10 //数据块允许的记录数（1024/100）
#define AND  7 //实际存放的记录数
#define NDB  71//数据块的块数（500/7）
#define LI  1024//索引块的块长（byte）(1024/32=32)
#define NI  7 //索引块允许的索引项数（(512-32)/(32+32)）
#define ANI  5 //实际存放的索引项数

int exit(int n);
int sqt=1;//顺序查找的头指针,且从第1块开始放索引叶子块

//-----------------------------------------------------------------------------------

void build(FILE *fp1,FILE *fp2)//建立B+树
{
	int i,j,k,n,m,finish,root;
	int n1,n2;
	int max[20];//用于建立索引时记录每块的最大值
	int num[10];//用于记录索引块的项数
	int data[32];
	int index[32];

    //建立数据文件
	for(i=1;i<=NDB;i++) 
	{//第i个数据块
		for(j=(i-1)*AND+1,k=0;j<=i*AND,k<3*AND;j++,k+=3)
		{//j:当前数据块的当前记录
			for(m=k,n=j;n<=j+2;n++,m++)
				data[m]=n;
		}
		fwrite(data,sizeof(int),32,fp1);//输入一个数据块
	}

	//建立索引文件
	index[0]=8;//建第0块，前8个数据是写入的有效数据
	index[1]=TDN;
	index[2]=SD;
	index[3]=LD;
    index[4]=ND;
	index[5]=LI;
    index[6]=NI;
	//第8个有效数据是根的块号，待树建立好后再写入
	fwrite(index,sizeof(int),32,fp2);
	finish=1;//记录已建立好的块数(0块已建立)
	n=NDB/ANI;//数据块块数/索引项数
	if(NDB%ANI!=0)
		n1=n+1;
	else
		n1=n;//n1为索引叶子块数
	for(i=1;i<=n1;i++)//0记录个数
	{
		if(i<n1)
		{//对第i个索引叶子结点
			index[0]=ANI;//5，实际索引项数
			for(j=1,k=(i-1)*ANI+1;j<=2*index[0];j++)
			{//k是第i个索引结点的第一项,依次加一，k为当前记录好，j<=10
				if(j%2==1)
					index[j]=AND*k;//一个记录数据7*k，所指数据块中的最大值
				else
				{
					index[j]=k;//一个记录指针，当前记录号
					k++;
				}
			}
			max[i]=index[2*index[0]-1];//第i个叶子结点的最大索引数
			index[j]=i+1;
			fwrite(index,sizeof(int),32,fp2);//输入第i个索引块的信息
			finish++;
		}
		else
		{
			index[0]=NDB%ANI;//71对5的模，剩余的索引项数
			for(j=1,k=ANI*(i-1)+1;j<=2*(index[0]-1);j++)
			{
				if(j%2==1)
					index[j]=AND*k;//一个记录数据
				else
				{
					index[j]=k;//一个记录指针
					k++;
				}
			}
			max[i]=index[j]=TDN;
			index[j+1]=k;
			index[j+2]=-1;//标记为空指针，叶子索引结点建立完成
			fwrite(index,sizeof(int),32,fp2);
			finish++;
		}
	}
	n=n1/ANI;//建倒数第二层，n1/5
	if(n1%ANI!=0)
		n2=n+1;
	else
		n2=n;//n2为倒数第二层块数
//----------------------------------------------------------------------------------
	if(n1%ANI==0)
	{
		for(i=1;i<=n2;i++)
			num[i]=ANI;//num为索引块的项数
	}
	else
	{
		if(n2-2>0)
		{
			for(i=1;i<=n2-2;i++)
				num[i]=ANI;
		}
		else if(n2==2)
		{
			if(n1%2==0)
				num[1]=num[2]=n1/2;
			else
			{
				num[1]=n1/2+1;
				num[2]=n1/2;
			}
		}
		else
			num[1]=n1;
	}
//------------------------------------------------------------------------------------
	for(i=1;i<=n2;i++)
	{
		index[0]=num[i];
		for(j=1,k=(i-1)*num[i-1]+1;j<=2*index[0];j++)
		{
			if(j%2==1)
				index[j]=max[k];//一个记录数据
			else
			{
				index[j]=k;//一个记录指针
				k++;
			}
		}
		max[i]=index[j-2];
		index[j]=-2;//标记结束
		fwrite(index,sizeof(int),32,fp2);
		finish++;
	}
	root=finish;//根块
	index[0]=n2;
	for(j=1,k=1;j<=2*index[0];j++)
	{
		if(j%2==1)
			index[j]=max[k];
		else
		{
			index[j]=finish+(k-1)-n2;
			k++;
		}	
	}
	index[j]=-2;
	fwrite(index,sizeof(int),32,fp2);
	finish++;
	fseek(fp2,0L,0);
	fread(index,sizeof(int),32,fp2);
	index[7]=root;
    fseek(fp2,0L,0);
	fwrite(index,sizeof(int),32,fp2);
}

void print(FILE *fp1,FILE *fp2)//打印信息
{
	int i,j;
	int index[32]; 

	fseek(fp2,0L,0);
	fread(index,sizeof(int),32,fp2);
	printf("索引文件信息如下：\n");
	printf("记录个数为：%d个\n",index[1]);
	printf("每个记录的长度为：%d Bytes\n",index[2]);
	printf("数据块长度为：%d Bytes\n",index[3]);
	printf("每个数据块允许的记录数：%d个\n",index[4]);
	printf("索引块的长度为：%d Bytes\n",index[5]);
	printf("每个索引块允许的项数：%d个\n",index[6]);
	printf("根所在的块为：%d\n",index[7]);
	printf("索引块信息：索引项数； 最大值	指向数据块号\n");
	for(i=1;i<=19;i++)
	{
		printf("索引块%d:\n",i);
		fread(index,sizeof(int),32,fp2);
		for(j=0;j<=2*index[0];j++)
			printf("%d  ",index[j]);
		printf("\n");
	}
	printf("\n");
}

void sort(FILE *fp1,FILE *fp2)//查找
{
	int i,j,n,k,e;
	int result=0;
	int data[32],index[32];

	n=1;
	while(n)
	{
		printf("请输入你要查找的记录号：\n");
		scanf("%d",&e);
		fseek(fp2,0L,0);
		fread(index,sizeof(int),32,fp2);
		k=index[7];
		for(i=1;i<=3;i++)
		{
			fseek(fp2,k*sizeof(int)*32L,0);
			fread(index,sizeof(int),32,fp2);
			for(j=1;j<=2*index[0];j+=2)
			{
				if(index[j]>=e)
				{
					k=index[j+1];
					printf("%d,",k);
					break;
				}
			}
		}
		fseek(fp1,(long)(k-1)*LD,0);
		fread(data,sizeof(int),32,fp1);
		for(i=0;i<40;i+=3)
		{
			if(data[i]==e)
			{
				printf("%d ",data[i]);
				printf("\n");
				result=1;
			}
		}
		if(result==0)
			printf("没有找到\n");
		printf("\n");
		printf("是否还需要继续查找？是（1）/否（0）\n");
		scanf("%d",&n);
	}
	return;
}

main()
{
	FILE *fp1,*fp2;
	fp1=fopen("data","wb+");
	fp2=fopen("index","wb+");
	if(fp1==NULL||fp2==NULL)
	{
		printf("cann't open this files!\n");
		exit(0);
	}
	else
		build(fp1,fp2);
	print(fp1,fp2);
	sort(fp1,fp2);
	fclose(fp1);
	fclose(fp2);
	return 0;
}