btpr.cpp

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

# include <iostream.h>
# include <conio.h>
# include <malloc.h>
enum {FALSE,TRUE,STOP=0};

# define n 2       //2
# define nn (n+n)  //4
 /* B+Data Structure */
	 struct ITEM
	 {
	  int key;          //Data
	  struct PAGE *p;   //Page Pointer
	 };
   struct PAGE
   {
	 int m;               //No of Allocations Filled 1 -+
	 struct PAGE *p0;     //						 1  |
	 struct ITEM e[nn+1]; //nn+1 is 5				 5  |--> 8 elements
	 struct PAGE *chain;  //Page chain				 1 -+
   };

class Btree
{
 public:
	PAGE * BplusInsert(int,PAGE *); //Insert a node into B+Tree
	PAGE * BplusDelete(int,PAGE *);  //Delete a node from B+Tree
	PAGE * Search(int,PAGE *,int *,struct ITEM *); //Search for a given value
	int KeySearch(PAGE *,int,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 *,int); //Update B+Tree on modifications.
	void Del(PAGE *,PAGE *,int,int *);
	void DeleteElement(int,PAGE *,int *);
	void PrintTree(PAGE *,int);
	void PrintRecordChain(PAGE *);
};
/* Search for 'x' in node, if it exiss the returns 1 otherwise 0
   k - Position where key is found. r-maximum position
   at which x<node[r+1] */
int Btree::KeySearch(PAGE *node,int x,int *k,int *r)
{
 int l=1;
 *r=node->m; //-1
 while(l<=*r)
 {
  *k = (l+(*r))/2;

  if(x<=node->e[*k].key)
    *r=*k-1;
  if(x>=node->e[*k].key)
    l=*k+1;
 }
   if(l-(*r)>1)
     return(1);
   else
     return(0);
}

/* Insert 'u' into page 'root' */
void Btree::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;//(PAGE *)malloc(sizeof(PAGE));
      /* Left Page */
      for(i=1;i<=n;i++)
	root->e[i]=t[i];

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

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

      /* is it leaf node, move the mid node */
      if(root->p0==NULL)
      {
       root->e[n+1]=*v;
       root->m=n;//+1;
       /* 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 the insert */
PAGE * Btree::Search(int x,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;
    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 Btree::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;
     a->e[n].key=c->e[s].key;
    }
    else
      {
	/* merge pages a and b*/
	dec=0;

	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 Btree::Update(PAGE *p,int x)
{
 PAGE *node;
 int k,r,y;
  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;
    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))
	node->e[k].key=y;
}
void Btree::Del(PAGE *p,PAGE *root,int k,int *h)
{
 PAGE *q;
 q=p->e[p->m].p;

 if(q==NULL)
 {
  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 Btree::DeleteElement(int x,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 * Btree::BplusInsert(int data,PAGE *root)
{
  struct ITEM u;
  int h;
  PAGE *q;
		 int i,b=0;
		  PAGE *prev,*link;
		  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++)
			 if(link->e[i].key==data)
			    {b=1; break; }
		  }
		  if(b==1) return(root);
  h=FALSE;
  root=Search(data,root,&h,&u);
  if(h)
  {                   //A node is created for the first time.
    q=root;
    root=new PAGE;//(PAGE *)malloc(sizeof(PAGE));
    root->m=1;
    root->p0=q;
    root->e[1].key=u.key;
    root->e[1].p=u.p;
    root->chain=NULL;
  }
  return(root);
}
PAGE * Btree::BplusDelete(int 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 Btree::PrintTree(PAGE *root,int level)
{
  int i;
  if(root)
  {
     if(level==1)  for(i=0;i<level*12;i++)   cout<<" "; else
		   for(i=0;i<level*6;i++)   cout<<" ";

textcolor(YELLOW);    if(level!=1) cprintf(" 滥哪