sql2.cpp

This project attempts to implement a Database using B+Tree. The project has developed a DATABASE SYS

# include <iostream.h>
# include <fstream.h>
# include <process.h>
# include <conio.h>
# include <stdlib.h>
# include <ctype.h>
# include <string.h>
# include <stdio.h>
# include <malloc.h>
enum {FALSE,TRUE};

# define n 2       //2
# define nn (n+n)  //4
 /* B+Data Structure */
	 struct ITEM
	 {
	  char *key;
	  ITEM() { key=new char[30]; }         //Data (Index)
	  struct PAGE *p;        //Page Pointer
	 };

class PAGE
{
	 int m;               //Serial Number 1 -+
	 struct PAGE *p0;     //              1  |
	 struct ITEM e[nn+1]; //nn+1 is 5     5  |--> 8 elements
	 struct PAGE *chain; //Page chain     1 -+
 public:
	PAGE(){m=0; p0=chain=NULL; }
	PAGE * BplusInsert(char[],PAGE *); //Insert a node into B+Tree
	PAGE * BplusDelete(char[],PAGE *);  //Delete a node from B+Tree
	PAGE * Search(char[],PAGE *,int *,struct ITEM *); //Search for a given value
	int KeySearch(PAGE *,char[],int *,int *); //Search B+Tree for given key
	void Insert(PAGE *,int *,struct ITEM ,struct ITEM *,int);
	void UnderFlow(PAGE *,PAGE *,int, int *);
	void Update(PAGE *,char[]); //Update B+Tree on modifications.
	void Del(PAGE *,PAGE *,int,int *);
	void DeleteElement(char[],PAGE *,int *);
	void PrintTree(PAGE *,int);
	void PrintRecordChain(PAGE *);
	int FindIndex(PAGE *,char []);
	void write(char [],PAGE *);
void CreateTable();
void DeleteTable();
void InsertRec(PAGE *);
void DeleteRec(PAGE *);
void SelectAll();
void Desc();
};
/* Search for 'x' in node, if it exists then returns 1 otherwise 0
   k - Position where key is found. r-maximum position
   at which x<node[r+1] */
int PAGE::KeySearch(PAGE *node,char x[50],int *k,int *r)
{
 int l=1;
 *r=node->m;
 while(l<=*r)
 {
  *k = (l+(*r))/2;

  if(strcmp(x,node->e[*k].key)<=0)	//  Check whether key is present at RHS
    *r=*k-1;
  if(strcmp(x,node->e[*k].key)>=0) 	//  Check whether key is present at LHS
    l=*k+1;
 }
   if(l-(*r)>1)
     return(1);
   else
     return(0);
}

/* Insert 'u' into page 'root' */
void PAGE::Insert(PAGE *root,int *h,struct ITEM u,struct ITEM *v,int r)
{
  int i;
  struct ITEM t[nn+2];
  PAGE *b;
  if(root->m<nn)
  {
   root->m+=1;
   *h=FALSE;
   for(i=root->m;i>=r+2;i--)
      root->e[i]=root->e[i-1];
   root->e[r+1]=u;
  }
  else
     {
      /* Enter Data into Table 't' */
      for(i=1;i<=r;i++)
	t[i]=root->e[i];

      t[r+1]=u;

      for(i=r+1;i<=nn;i++)
	t[i+1]=root->e[i];

	b=new PAGE;
      /* Left Page */
      for(i=1;i<=n;i++)
	root->e[i]=t[i];

      /* record that has to be sent to upper node */
      strcpy(v->key,t[n+1].key);
      v->p=t[n+1].p;

      /* Right Page */
      for(i=1;i<=n+1;i++)
	b->e[i]=t[i+n];

      /* is it leaf node, move the mid node */
      if(root->p0==NULL)
      {
       root->e[n+1]=*v;
       root->m=n;
       /* Chaining of records at leaf nodes */
       b->chain=root->chain;
       root->chain=b;
	      b->m=n+1; //=n;
	      b->p0=t[n+1].p;//+1
	      v->p=b;
      }
      else
      {
	      root->m=n-1; //=n;
	      b->m=n+1; //=n;
	      b->p0=t[n].p;//+1
	      v->p=b;
      }

    }
}
/* Search for key 'x' if it does not exist then insert */
PAGE * PAGE::Search(char x[50],PAGE *root,int *h,struct ITEM *v)
{
 struct ITEM u;
 int found;
 int i,k,r;
 PAGE *q;
 if(!root) //if Root is NULL
 {
    *h=TRUE;
    strcpy(v->key,x);
    v->p=NULL;
 }
  else
     {
	if(KeySearch(root,x,&k,&r))
	    *h=FALSE;
	else
	   {
	      if(r==0)
		q=root->p0;
	      else
		q=root->e[r].p;

	      q=Search(x,q,h,&u);

	      if(*h==TRUE)
		 Insert(root,h,u,v,r);
	   }
     }
  return(root);
}

/* Balancing or page 'a' for underflow.
c- parent node,s-positions of sub tree for borrowing data and merging
 if required. h=true if 'c' underflows */
void PAGE::UnderFlow(PAGE *c,PAGE *a,int s, int *h)
{
 int mc,mb,i,k;
  PAGE *b;
  int dec;

  mc=c->m;
  if(s<mc)
  { /* b=page to the right og a */
   s=s+1;
   b=c->e[s].p;
   mb=b->m;
   a->e[n].p=b->p0;
   k=(mb-n+1)/2;

   if(k>=0)
   {
    /* move k items from b to a */
     for(i=1;i<=k-1;i++)
       a->e[i+n]=b->e[i];
     c->e[s]=b->e[k];
     c->e[s].p=b;

     mb=mb-k;

     b->p0=b->e[k].p;
     for(i=1;i<=mb;i++)
       b->e[i]=b->e[i+k];

     a->m=(n-1)+k;
     b->m=mb;
     *h=FALSE;
     strcpy(a->e[n].key,c->e[s].key);
    }
    else
      {
	/* merge pages a and b*/
	dec=0;

	strcpy(a->e[n].key,c->e[s].key);
	if(a->p0==NULL)
	  dec=1;
	for(i=1;i<=mb;i++)
	  a->e[i+n-dec]=b->e[i];

	for(i=s;i<=mc-1;i++)
	  c->e[i]=c->e[i+1];
	  a->m=nn-dec;
	  c->m=c->m-1;

	  *h=(c->m<n)?1:0;
	  a->chain=b->chain;
	  free(b);
      }
    }
    else
      {
	/* b = page to the left of a */
	if(s==1)
	  b=c->p0;
	else
	  b=c->e[s-1].p;

	mb=b->m;
	k=(mb-n+1)/2;

	if(k>0)
	{
	  /* Move k items from b to a */
	  for(i=n-1;i>=1;i--)
	    a->e[i+k]=a->e[i];
	  for(i=k;i>=1;i--)
	    a->e[i]=b->e[i+n];
	  a->e[k].p=a->p0;
	  a->p0=b->e[n+1].p;

	  c->e[s]=b->e[n];
	  c->e[s].p=a;

	  b->m=mb-k;
	  a->m=(n-1)+k;
	  *h=FALSE;
	}
	else
	   {
	     /* Merge pages a and b */
	     dec=0;
	     /* To leaf page do not move parent key since that a
	     only a directive */
	     if(b->p0==NULL)
	       dec=1;

	     b->e[n+1]=c->e[s];
	     b->e[n+1].p=a->p0;
	     for(i=1;i<=n-1;i++)
	       b->e[i+n+1-dec]=a->e[i];
	     b->m=nn-dec;
	     c->m=c->m-n;
	     *h=(c->m<n)?1:0;
	     b->chain=a->chain;
	     free(a);
	   }
      }
}
/* Replace all occurences of x in a B+Tree by the right most
key of left subtree i.e left sub tree=x<node->e[r].key
for heighest value of 'r' */
void PAGE::Update(PAGE *p,char x[])
{
 PAGE *node;
 int k,r;
 char y[20];
  if(p==NULL)
   return;
   KeySearch(p,x,&k,&r);

  if(r==0)
    node=p->p0;
  else
    node=p->e[r].p;

    while(node->p0)
      node=node->e[node->m].p;
    strcpy(y,node->e[node->m].key);

    /* Replace all occurences of 'x' by 'y' */
    for(node=p;node->p0;node=node->e[node->m].p)
      if(KeySearch(node,x,&k,&r))
	strcpy(node->e[k].key,y);
}

void PAGE::Del(PAGE *p,PAGE *root,int k,int *h)
{
 PAGE *q;
 q=p->e[p->m].p;

 if(q==NULL)
 {
  strcpy(root->e[k].key,p->e[p->m].key);
  p->m=p->m-1;
  *h=(p->m<n)?1:0;
 }
 else
    {
      Del(q,root,k,h);
      if(*h==TRUE)
	 UnderFlow(p,q,p->m,h);
    }
}

void PAGE::DeleteElement(char x[50],PAGE *a,int *h)
{
 int found,r,k,i;
 PAGE *q;
   if(a==NULL)
   {
    *h=FALSE;
    cout<<"\nNo elements in tree";
    return;
   }
   found=KeySearch(a,x,&k,&r);

   if(r==0)
     q=a->p0;
   else
     q=a->e[r].p;

   if(found)
   {
      if(q==NULL)
      {
	for(i=k;i<=a->m-1;i++)
	  a->e[i]=a->e[i+1];
	a->m=a->m-1;
	*h=(a->m<n)?1:0;
      }
      else
	{
	  Del(q,a,k,h);
	  if(*h==TRUE)
	     UnderFlow(a,q,r,h);
	}
   }
    else
       {
	DeleteElement(x,q,h);
	if(*h==TRUE)
	  UnderFlow(a,q,r,h);
       }
}
PAGE * PAGE::BplusInsert(char data[50],PAGE *root)
{
  struct ITEM u;
  int h;
  PAGE *q;
		 int i,b=0,j;
		  PAGE *prev,*link; char val[50],dt[50];
		  if(root)
		  {
		     for(prev=link=root;link;link=link->p0) prev=link;
		     for(link=prev;link;link=link->chain)
		       for(i=1;i<=link->m;i++)
		       {
			 for(j=0;link->e[i].key[j]!=' ';j++)
			 {
			     val[j]=link->e[i].key[j];
			     dt[j]=data[j];
			 } val[j]='\0'; dt[j]='\0';
			     //cout<<endl<<"["<<val<<","<<dt<<"]";
			 if(strcmp(dt,val)==0)
			    {b=1; break; }
		       }
		  }
		  if(b==1) return(root);
  h=FALSE;
  root=Search(data,root,&h,&u);
  if(h)
  {
    q=root;
    root=new PAGE;
    root->m=1;
    root->p0=q;
    strcpy(root->e[1].key,u.key);
    root->e[1].p=u.p;
    root->chain=NULL;
  }
  return(root);
}
PAGE * PAGE::BplusDelete(char data[],PAGE *root)
{
  struct ITEM u;
  int h;
  PAGE *q;

  h=FALSE;

  DeleteElement(data,root,&h);
  if(h)
  {
    /* Base page size was reduced */
    if(root->m==0)
    {
     q=root;
     root=root->p0;
     free(q);
    }
  }
  Update(root,data);
return(root);
}
void PAGE::PrintTree(PAGE *root,int level)
{
  int i;
  if(root)
  {
     if(level==0)  for(i=0;i<level*12;i++)   cout<<" "; else
		   for(i=0;i<level*6;i++)   cout<<" ";

//textcolor(YELLOW);
if(level!=0) cout<<" 滥哪