zbtree.cpp

实现一个精简型单用户SQL引擎(DBMS)MiniSQL

//  p[ItemOnNode + 1] = p[ItemOnNode];
  for(int i=ItemOnNode-1;i>=0;i--)
  {
    if(Compare(pPrimKey,k[i]) < 0)
    {
      p[i+1] = p[i];
      k[i+1] = k[i];
      continue;
    }
    else 
      break;
  }
  p[i+1] = pRec;
  k[i+1] = pPrimKey;
  ItemOnNode++;
}

// insert a key in the node which isn't a leaf
void ZBTree_Node::InsertKeyNotInLeaf(pKey_Attr pPrimKey,_F_FileAddr pRec)
{
  // the node is never empty
  for(int i=ItemOnNode-1;i>=0;i--)
  {
    if(Compare(pPrimKey,k[i]) < 0)
    {
      p[i+2] = p[i+1];
      k[i+1] = k[i];
      continue;
    }
    else 
      break;
  }
  p[i+2] = pRec;
  k[i+1] = pPrimKey;
  ItemOnNode++;
}
// delete a key in a leaf and adjust the node
void ZBTree_Node::DeleteKeyInLeaf(pKey_Attr pPrimKey)
{
  int i;
  for(i=0;i<ItemOnNode;i++)
  {
    if( Compare(pPrimKey,k[i]) == 0 )
      break;
  }
  DeleteKey(k[i]);  // delete the space of k[i]
  // adjust the node
  for(;i<ItemOnNode-1;i++)
  {
    p[i] = p[i+1];
    k[i] = k[i+1];
  }
  p[ItemOnNode-1].ulFilePageID = 0;
  p[ItemOnNode-1].uiOffset     = 0;
  k[ItemOnNode-1]            = NULL;
  ItemOnNode--;
}
// delete the key in the node, and automatic adjust the node
void ZBTree_Node::DeleteKeyNotInLeaf(pKey_Attr pPrimKey)
{
  int i;
  for(i=0;i<ItemOnNode;i++)
  {
    if( Compare(pPrimKey,k[i]) == 0 )
      break;
  }
  DeleteKey(k[i]);  // delete the space of k[i]
  // adjust the node
  for(;i<ItemOnNode-1;i++)
  {
    k[i]   = k[i+1];
    p[i+1] = p[i+2];
  }
  k[ItemOnNode-1]          = NULL;
  p[ItemOnNode].ulFilePageID = 0;
  p[ItemOnNode].uiOffset     = 0;
  ItemOnNode--;
}

// delete the space of the first key in the node
void ZBTree_Node::DeleteKeyV_()
{
    pKey_Attr head,temp;
    head = temp = k[0];
    for(int j=0;KeyInfo[j]!=0;j++)
    {
      switch(KeyInfo[j])
      {
        case 'i' :  // int 
                    head = head->next;
                    delete temp;
                    temp = head;
                    break;
        case 'f' :  // float
                    head = head->next;
                    delete temp;
                    temp = head;
                    break;
        case 'c' :  // char
                    delete  [] (head->value.pCharValue);
                    head = head->next;
                    delete temp;
                    temp = head;
                    while(isdigit(KeyInfo[++j])) ;  //skip digital number
                    j--;
                    break;
      }
    }
    for(int i=0;i<ItemOnNode-1;i++)
    {
      p[i] = p[i+1];
      k[i] = k[i+1];
    }
    p[ItemOnNode-1] = p[ItemOnNode];
    p[ItemOnNode].ulFilePageID = 0;
    p[ItemOnNode].uiOffset     = 0;
    k[ItemOnNode - 1]        = NULL;
    ItemOnNode--;
}

// delete the space of the key
void ZBTree_Node::DeleteKey(pKey_Attr Key)
{
  pKey_Attr head,temp;
  head = temp = Key;
  for(int j=0;KeyInfo[j]!=0;j++)
  {
    switch(KeyInfo[j])
    {
      case 'i' :  // int 
                  head = head->next;
                  delete temp;
                  temp = head;
                  break;
      case 'f' :  // float
                  head = head->next;
                  delete temp;
                  temp = head;
                  break;
      case 'c' :  // char
                  delete  [] (head->value.pCharValue);
                  head = head->next;
                  delete temp;
                  temp = head;
                  while(isdigit(KeyInfo[++j])) ;  //skip digital number
                  j--;
                  break;
    }
  }
}

// create a key equal to Key1,and automatic open a new space 
pKey_Attr ZBTree_Node::CreateKey(pKey_Attr Key1)
{
  pKey_Attr Key2,temp;
  for(int j=0; KeyInfo[j]!='\0';j++)
  {
    if(j == 0)    // the first node
      Key2 = temp = new Key_Attr;
    else
    {
      temp->next = new Key_Attr;
      temp       = temp->next;
    }
    switch(KeyInfo[j])
    {
      case 'i'  :  // int value  
                   temp->value.IntValue = Key1->value.IntValue;
                   temp->next           = NULL;
                   break;
      case 'f'  :  // float value 
                   temp->value.FloatValue = Key1->value.FloatValue;
                   temp->next           = NULL;
                   break;
      case 'c'  :  // string
                   int num = 0;
                   for( j=j+1; isdigit(KeyInfo[j]); j++)
                   {
                     num = num * 10 + KeyInfo[j] - '0';
                   }
                   j--;        // move the index back
                   num++;      // for '\0' which is the end of a string
                   char* pCharValue = new char [num];
                   char* str = Key1->value.pCharValue;
                   strcpy(pCharValue,str);
                   temp->value.pCharValue = pCharValue;
                   temp->next             = NULL;
                   break;                  
    }
    Key1 = Key1->next;  // move to the next node
  }  //KeyInfo[i] = '\0'
  return Key2;
}

// copy dest to source,source has its owner space
void ZBTree_Node::CopyKey(pKey_Attr source,pKey_Attr dest)
{
  for(int j=0;KeyInfo[j]!=0;j++)
  {
    switch(KeyInfo[j])
    { 
      case 'i' :  // int 
                  dest->value.IntValue = source->value.IntValue;
                  break;
      case 'f' :  // float
                  dest->value.FloatValue = source->value.FloatValue;
                  break;
      case 'c' :  // char
                  strcpy(dest->value.pCharValue,source->value.pCharValue);
                  while(isdigit(KeyInfo[++j])) ;  //skip digital number
                  j--;
                  break;
    }
    source = source->next;
    dest   = dest->next;
  }
}

bool ZBTree_Node::IsNotEnoughPt()
{
  int n = MaxItem + 1;  
  if( 0 == IsLeaf )  // it isn't a leaf
  {
    int m;
    if( !(n%2) )
      m = n/2 ;  // n = NodeL.MaxItem + 1
    else 
      m = n/2 + 1;
    if( (ItemOnNode + 1) < m)  // not enough points ,ItemOnNode+1 is the number of points
      return true;
    else 
      return false;
  }
  else // it is a leaf
  {
    int m;
    if( ! ((n-1)%2) )
      m = (n-1)/2 ;  // n = NodeL.MaxItem + 1
    else 
      m = (n-1)/2 + 1;
    if( ItemOnNode < m )  // not enough points
      return true;
    else 
      return false;
  }

}
//------------------------------------------------------------------------

//***************************ZBTree***************************************

//------------------------------------------------------------------------
ZBTree::ZBTree()
{
  _F_FileAddr temp;
  temp.ulFilePageID = 0;
  temp.uiOffset     = 0;
  for(int i=0;i<DEPTH;i++)
    SearchPath[i] = temp;
}

ZBTree::~ZBTree()
{

}

// create the head and the empty root
void ZBTree::Create(char* KeyStr)
{
  SetPath();                // set path to *.idx 
  ZBTree_Index Idx;
  Idx.Create_Head(KeyStr);  // file head
  Idx.WriteHeadToFile();
  ZBTree_Node root;         // first node ,also root,existed for ever 
  root.IsLeaf = 1;
  root.WriteNodeToFile(Idx.GetRoot());
}

// change the index head,make the parament as root 
void ZBTree::GrantRoot(_F_FileAddr ptr)
{
  ZBTree_Index idx;
  idx.ReadHeadFromFile();
  idx.IdxHead.root = ptr;
  idx.WriteHeadToFile();
}


// delete a node in the index file and manage the empty blocks 
void ZBTree::DeleteNodeInFile(_F_FileAddr ptr)
{
  ZBTree_Index idx;
  idx.ReadHeadFromFile();

  if( 0 == idx.IdxHead.FirstEmptyBlock.ulFilePageID )  // the index has no empty block
  {
    idx.IdxHead.FirstEmptyBlock = ptr;
    idx.IdxHead.LastEmptyBlock  = ptr;
  }
  else
  {
    // make the last empty block point to the new delete block
    ZBTree_Node NextNode;
    NextNode.ReadNodeFromFile(idx.IdxHead.LastEmptyBlock);
    NextNode.Next_Empty_Block = ptr;
    NextNode.WriteNodeToFile(idx.IdxHead.LastEmptyBlock);
    // change the index head 
    idx.IdxHead.LastEmptyBlock = ptr;
  }
  idx.WriteHeadToFile();
}

// search the address of the primary key,return the position in pKeyLoca
// if it can't find the pPrimKey,make the pkeyLoca just greater than
// the location of pPrimKey and return false.Otherwise,make pKeyLoca
// equal to the location of pPrimKey and return true. 
bool ZBTree::Search(pKey_Attr pPrimKey,pKey_Location pKeyLoca)
{
   SetPath();  // set path to *.idx
   ZBTree_Index idx;
   idx.ReadHeadFromFile();
   _F_FileAddr ptr = idx.GetRoot();
   
   ZBTree_Node Node;
   for(int level=0;level<DEPTH;level++)
   {
     Node.ReadNodeFromFile(ptr);
     SearchPath[level] = ptr;  // save the path of search

     int i;
     if( 0 == Node.IsLeaf )   // it isn't a leaf
     {
       for(i=0;i<=Node.ItemOnNode;i++)
       {
         if(Node.ItemOnNode == i)  // the end of a node 
         {
           ptr = Node.p[i];
           break;
         }
         else if( Node.Compare(pPrimKey,Node.k[i]) < 0 ) // track into the left subtree
         {
           ptr = Node.p[i];
           break;
         }
         else if( Node.Compare(pPrimKey,Node.k[i]) >= 0) // track into the right subtree
           continue;
       }
     }

     else // it is a leaf
     {
       for(i=0;i<=Node.ItemOnNode;i++)
       {
         if(Node.ItemOnNode == i)  // can't find the key
         {
           pKeyLoca->ptr    = ptr;
           pKeyLoca->offset = Node.MaxItem;  //It is a mark *********
           return false;
         }
         else if( Node.Compare(pPrimKey,Node.k[i]) == 0 ) // find the key
         {
           pKeyLoca->ptr    = ptr;
           pKeyLoca->offset  = i;
           return true;
         }
         else if( Node.Compare(pPrimKey,Node.k[i]) > 0 )  // pPrimKey > k[i]
           continue;
         else  // pPrimKey < k[i],it alse means the key isn't existed
         {
           pKeyLoca->ptr    = ptr;
           pKeyLoca->offset = i;
           return false;
         }
       }
     }
   }
   throw 1028;
}

// whether the tree is empty
bool ZBTree::IsEmpty()
{
  Key_Location KeyLoca;
  KeyLoca = GetStart();
  ZBTree_Node FirstNode;
  FirstNode.ReadNodeFromFile(KeyLoca.ptr);
  if( 0 == FirstNode.ItemOnNode )  // the tree is empty
    return true; // no record
  return false;
}

// whether the node is root or not
bool ZBTree::IsRoot(_F_FileAddr ptr)
{
  return (SearchPath[0] == ptr);
}

bool ZBTree::CanMerge(ZBTree_Node* pNode,ZBTree_Node* pNode_)
{
  if( pNode->IsLeaf ) // a leaf
    return (pNode->ItemOnNode + pNode_->ItemOnNode <= pNode->MaxItem);
  else  // not a leaf,   because of pPrimKey_
    return (pNode->ItemOnNode + pNode_->ItemOnNode < pNode->MaxItem);   
}

// merge the two node pNodeL and pNodeL_
void ZBTree::Merge(ZBTree_Node* pNodeL,ZBTree_Node* pNodeL_,pKey_Attr pPrimKey_,bool IsLLeftOfL_)
{
  if( 0 == pNodeL->IsLeaf )  // it isn't a leaf
  {
    if(IsLLeftOfL_)  // L < L_
    {
      int i;
      int j = pNodeL->ItemOnNode + 1; // include pPrimKey_
      // move the the right ,offset is (ItemOnNode+1)
      pNodeL_->p[pNodeL_->ItemOnNode + j] = pNodeL_->p[pNodeL_->ItemOnNode];
      for(i=pNodeL_->ItemOnNode-1;i>=0;i--)
      {
        pNodeL_->k[i + j] = pNodeL_->k[i];
        pNodeL_->p[i + j] = pNodeL_->p[i];
      }
      // assign V' to the pNodeL_
      pNodeL_->k[j-1] = pPrimKey_;
      pNodeL_->p[j-1] = pNodeL->p[pNodeL->ItemOnNode];
      // move all elements in pNodeL to pNodeL_
      for(i=0;i<pNodeL->ItemOnNode;i++)
      {
        pNodeL_->p[i] = pNodeL->p[i];
        pNodeL_->k[i] = pNodeL->k[i];
      }
      // set ItemOnNode in pNodeL_
      pNodeL_->ItemOnNode = pNodeL_->ItemOnNode + pNodeL->ItemOnNode + 1;
      pNodeL->Reset(); // set k[i] = NULL and ItemOnNode = 0 in pNodeL
    }
    else // L > L_
    {
      int j =  pNodeL_->ItemOnNode + 1; // include pPrimKey_
      pNodeL_->k[pNodeL_->ItemOnNode] = pPrimKey_; 
      for(int i=0;i<pNodeL->ItemOnNode;i++)
      {
        pNodeL_->p[i+j] = pNodeL->p[i];
        pNodeL_->k[i+j] = pNodeL->k[i];
      }
      pNodeL_->p[i+j]   = pNodeL->p[i];
      pNodeL_->ItemOnNode = pNodeL_->ItemOnNode + pNodeL->ItemOnNode + 1;
      pNodeL->Reset();
    }
  }
  else  // it is a leaf
  {
    if(IsLLeftOfL_)  // L < L_
    {
      int j = pNodeL->ItemOnNode;
      for(int i=0;i<pNodeL_->ItemOnNode;i++)
      {
        pNodeL->p[i+j] = pNodeL_->p[i];
        pNodeL->k[i+j] = pNodeL_->k[i];
      }
      pNodeL->ItemOnNode += pNodeL_->ItemOnNode;
      pNodeL->p[pNodeL->MaxItem] = pNodeL_->p[pNodeL_->MaxItem];  // L.p[n] = L_.p[n]
      pNodeL_->Reset();
    }
    else // L > L_
    {
      int j = pNodeL_->ItemOnNode;
      for(int i=0;i<pNodeL->ItemOnNode;i++)
      {
        pNodeL_->p[i+j] = pNodeL->p[i];
        pNodeL_->k[i+j] = pNodeL->k[i];
      }
      pNodeL_->ItemOnNode += pNodeL->ItemOnNode;
      pNodeL_->p[pNodeL_->MaxItem] = pNodeL->p[pNodeL->MaxItem];  // L_.p[n] = L.p[n] 
      pNodeL->Reset();  // make all k[i] NULL and ItemOnNode = 0 
    }
  }
  
}

// swap the points in the parent node
void ZBTree::SwapVariables(_F_FileAddr L,_F_FileAddr L_)
{
  ZBTree_Node ParentNode;
  ParentNode.ReadNodeFromFile( Parent(L) );
  int m,n;
  // find the indexes of L and L_ 
  for(int i=0;i <= ParentNode.ItemOnNode;i++)
  {
    if( ParentNode.p[i] == L )
      m = i;
    if( ParentNode.p[i] == L_ )
      n = i;
  }
  // swap L and L_
  _F_FileAddr temp;
  temp = ParentNode.p[m];
  ParentNode.p[m] = ParentNode.p[n];
  ParentNode.p[n] = temp;

  ParentNode.WriteNodeToFile( Parent(L) );
}

// get the parent _F_FileAddr of the parament according to the search path
_F_FileAddr ZBTree::Parent(_F_FileAddr ptr)
{
  for(int i=0;SearchPath[i].ulFilePageID != 0;i++)
  {