bptree.cpp

用c语言实现的一个小型dbms

}

///////////////////////////////////////////////////////////////////////////////////////////////
// insert a key in the node which isn a leaf
void BPTreeNode::insertKeyInLeaf(_F_FileAddr pRec,pKey_Attr pPrimKey) {
  if( 0 == ItemOnNode )  // The node is empty
  {
    p[0] = pRec;
    k[0] = pPrimKey;
  }
//  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 BPTreeNode::insertKeyNotLeaf(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 BPTreeNode::deleteKeyInLeaf(pKey_Attr pPrimKey) {
  int i;
  for(i=0;i<ItemOnNode;i++)
  {
    if( compare(pPrimKey,k[i]) == 0 )
      break;
  }
  deleteKeySpace(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 BPTreeNode::deleteKeyNotLeaf(pKey_Attr pPrimKey) {
  int i;
  for(i=0;i<ItemOnNode;i++)
  {
    if( compare(pPrimKey,k[i]) == 0 )
      break;
  }
  deleteKeySpace(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 BPTreeNode::deleteFirstKey() {
    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 BPTreeNode::deleteKeySpace(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 BPTreeNode::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;
}

///////////////////////////////////////////////////////////////////////////////////////////////
bool BPTreeNode::isNotEnoughPoints() {
  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;
  }

}
////////////////////////////////////////////////////////////////////////////////////////////////////

/*=========================================================================
=========                 definition for BPTree               =============
=========================================================================*/

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

//destructor

BPTree::~BPTree() {

}

////////////////////////////////////////////////////////////////////////////////////////////////////

void BPTree::setPath() {
	char address[256];
	strcpy(address, CurLocation);
	strcat(address, CurRelationName);
	strcat(address, ".idx");
	_M_File test = Buffer[address]; 
}

////////////////////////////////////////////////////////////////////////////////////////////////////

void BPTree::create(char *KeyStr) {
	setPath();
	BPTree_Index idx;
	idx.createHead(KeyStr);
	idx.writeHeadToFile();

	BPTreeNode root;
	root.IsLeaf = 1;
	root.writeNodeToFile(idx.getRoot());
}

////////////////////////////////////////////////////////////////////////////////////////////////////

void BPTree::createNewRoot(_F_FileAddr p0, pKey_Attr pPrimKey, _F_FileAddr p1) {
	_F_FileAddr Newroot;
	Newroot = createNodeInFile();
	BPTree_Index idx;
	idx.readHeadFromFile();
	idx.IdxHead.root = Newroot;
	idx.writeHeadToFile();

	BPTreeNode Root;
	Root.IsLeaf = 0;
	Root.ItemOnNode = 1;
	Root.p[0] = p0;
	Root.p[1] = p1;
	Root.k[0] = pPrimKey;
	Root.writeNodeToFile(Newroot);
}

////////////////////////////////////////////////////////////////////////////////////////////////////

void BPTree::grantRoot(_F_FileAddr pfa) {
	BPTree_Index idx;
	idx.readHeadFromFile();
	idx.IdxHead.root = pfa;
	idx.writeHeadToFile();
}

///////////////////////////////////////////////////////////////////////////////////////////////////

void BPTree::deleteNodeInFile(_F_FileAddr pfa) {
	BPTree_Index idx;
	idx.readHeadFromFile();
	//make the first empty block point to the new delete block
	if(idx.IdxHead.FirstEmptyBlock.ulFilePageID == 0) {
		idx.IdxHead.FirstEmptyBlock = pfa;
		idx.IdxHead.LastEmptyBlock  = pfa;
	}
	else {
    // make the last empty block point to the new delete block
    BPTreeNode NextNode;
	NextNode.readNodeFromFile(idx.IdxHead.LastEmptyBlock);
    NextNode.Next_Empty_Block = pfa;
    NextNode.writeNodeToFile(idx.IdxHead.LastEmptyBlock);
    // change the index head 
    idx.IdxHead.LastEmptyBlock = pfa;
	}
	idx.writeHeadToFile();
}

///////////////////////////////////////////////////////////////////////////////////////////////////
//--
bool BPTree::search(pKey_Attr pPrimKey, pKey_Location pKeyLoca) {
	setPath();
	BPTree_Index idx;
	idx.readHeadFromFile();
	_F_FileAddr pfa = idx.getRoot();

	BPTreeNode Node;
	for(int level=0; level<DEPTH; level++) {
		Node.readNodeFromFile(pfa);
		SearchPath[level] = pfa;
		//not leaf
		if(Node.IsLeaf == 0) {
			for(int i=0; i<=Node.ItemOnNode; i++) {
				if(i == Node.ItemOnNode) {
					pfa = Node.p[i];
					break;
				}
				else if(Node.compare(pPrimKey, Node.k[i]) < 0) {
					pfa = Node.p[i];
					break;
				}
				else if(Node.compare(pPrimKey,Node.k[i]) >= 0)
					continue;
			}
		}
		else {
			//is leaf
			for(int j=0; j<=Node.ItemOnNode; j++) {
				if(j == Node.ItemOnNode) {
					pKeyLoca->ptr = pfa;
					pKeyLoca->offset = Node.MaxItem;
					return false;
				}
				else if(Node.compare(pPrimKey, Node.k[j]) == 0) {
					pKeyLoca->ptr = pfa;
					pKeyLoca->offset = j;
					return true;
				}
				else if( Node.compare(pPrimKey,Node.k[j]) > 0 )  // pPrimKey > k[i]
					continue;
				else {
					pKeyLoca->ptr    = pfa;
					pKeyLoca->offset = j;
					return false;
				}
			}
		}
	}
	throw 1028;
}

///////////////////////////////////////////////////////////////////////////////////////////////////
//--
bool BPTree::isRoot(_F_FileAddr pfa) {
	return SearchPath[0] == pfa;
}

///////////////////////////////////////////////////////////////////////////////////////////////////
//--
bool BPTree::isEmpty() {
	Key_Location KeyLoca;
//	cout<<"begin isEmpty()"<<endl;//=======//
	KeyLoca = getStart();
	BPTreeNode FirstNode;
	FirstNode.readNodeFromFile(KeyLoca.ptr);
//	cout<<"end isEmpty()"<<endl;  //=====//
	if(FirstNode.ItemOnNode == 0)
		return true;
	return false;
}

///////////////////////////////////////////////////////////////////////////////////////////////////
//--
Key_Location BPTree::moveToNextKey(Key_Location KeyLoca) {
	Key_Location temp;
	BPTreeNode node; 
	node.readNodeFromFile(KeyLoca.ptr);
	
	if( node.MaxItem == KeyLoca.offset ) {
		if(node.p[node.MaxItem].ulFilePageID == 0)
			temp.ptr.ulFilePageID = 0;
		else {
			// get the address of the first key in the next node 
			BPTreeNode NextNode;
			NextNode.readNodeFromFile(node.p[node.MaxItem]);
			temp.ptr = node.p[node.MaxItem];
			temp.offset = 0;
		}
		return temp;
	}

	int i = KeyLoca.offset + 1;
	// the next key is empty or full
	if( 0 == node.p[i].ulFilePageID || node.MaxItem == i) {
		i = node.MaxItem;  // the last p[MaxItem]
		if( 0 == node.p[i].ulFilePageID ) 
			temp.ptr.ulFilePageID = 0;
		else {
			BPTreeNode NextNode;
			NextNode.readNodeFromFile(node.p[i]);
			temp.ptr = node.p[i];
			temp.offset = 0;
		}
	}
	else {
		// the address of the next key in the current node 
		temp.ptr = KeyLoca.ptr;
		temp.offset = KeyLoca.offset + 1;
	}
	return temp;
}

///////////////////////////////////////////////////////////////////////////////////////////////////
//this method returns the address of the first key in the leftest leaf node
//--
Key_Location BPTree::getStart() {
	BPTree_Index idx;
	idx.readHeadFromFile();
	_F_FileAddr ptr = idx.getRoot();
  
    for( ; ; ) {
		BPTreeNode Node;
		Node.readNodeFromFile(ptr);
		if( 1 == Node.IsLeaf ) {
			Key_Location temp;
			temp.ptr = ptr;
			temp.offset = 0;
			return temp;
		}
		else
			ptr = Node.p[0];
	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////
//--
_F_FileAddr BPTree::getParent(_F_FileAddr ptr) {
	for(int i=0; SearchPath[i].ulFilePageID != 0; i++) {
		if(SearchPath[i] == ptr)
			return SearchPath[i-1];  
	}
	throw 1022;
}