btree.cc

为数据库创建索引的B+树的算法实现。功能包括创建删除节点、条目等。最终将树递归打印于屏幕。（包含内存资源管理）

#include "btree.h"

int deg;	// degree
#define MaxPtrNum() (2*deg+2)
#define MaxKeyNum() (2*deg+1)

// init page pool by cachesize and degree
void InitByDegree(int cachesize,int _deg) {	
	deg=_deg;
	int BLK_SIZE=(2*deg+1)*KEY_SIZE+(2*deg+2)*PTR_SIZE;
	InitPagePool(cachesize,BLK_SIZE);
}

// routines for transforming between ptr. and int in leaf nodes
BTNode* ValueToPtr(int value) { return (BTNode*)value; }
int PtrToValue(BTNode* ptr) {	return (int)ptr; }

void printLeafEntry(int _key,int _value) {
	printf("(%d,%d)\n",_key,_value);	
}

// create a new BTNode
BTNode::BTNode(BTree* _bt,int _level) {	
	BlockAddr=GetNewBlock(block);	// allocated block 
 	bt=_bt;	level=_level;
	num_ptr=1;	// num_ptr=1 => no key for non-leaf nodes
		
	for (int i=0;i<MaxPtrNum();i++) setPtr(i,NULL); // set all ptr null
	setNextSib(NULL);	// auto check !, used after init
	if (level==0) bt->dnodes++; else bt->inodes++;
}

// get key of position "pos"  
int BTNode::getKey(int pos) {  //// pos= # in this node
	int _key=-1;
	int offset=PTR_SIZE+pos*(PTR_SIZE+KEY_SIZE);
	memcpy((void*)(&_key),BlockAddr+offset,KEY_SIZE);
	return _key;
}

// set key of position "pos"  
void BTNode::setKey(int pos,int _key) {
	int offset=PTR_SIZE+pos*(PTR_SIZE+KEY_SIZE);
	memcpy(BlockAddr+offset,(void*)(&_key),KEY_SIZE);
}

// get ptr. of position "pos"  
BTNode* BTNode::getPtr(int pos) {
	BTNode* _ptr=NULL;
	int offset=pos*(PTR_SIZE+KEY_SIZE);
	memcpy((void*)(&_ptr),BlockAddr+offset,PTR_SIZE);
	return _ptr;
}

// set ptr. of position "pos"  
void BTNode::setPtr(int pos,BTNode* _ptr) { 
	int offset=pos*(PTR_SIZE+KEY_SIZE);
	memcpy(BlockAddr+offset,(void*)(&_ptr),PTR_SIZE);
}

// get next silbing node
BTNode* BTNode::getNextSib() {
	if (isLeafNode())
		return getPtr(MaxPtrNum()-1);  
	else 
		return NULL;
}

// set next silbing node
void BTNode::setNextSib(BTNode* nextNode) {
	if (isLeafNode()) setPtr(MaxPtrNum()-1,nextNode);
}

// print current node with indentation level "indent"
// also print child node recursively with 1 more level of indentation
void BTNode::printNode(int indent) {
	char space[indent+1];
	space[indent]='\0';
	for (int i=0;i<indent;i++) space[i]=' ';
	
	printf("%s[Level %d, Block %d, LP %d]\n",space,level,block,num_ptr);
	if (isLeafNode()) {
		for (int i=0;i<getNumKey();i++) {
			int _key=getKey(i);
			int _value=PtrToValue(getPtr(i));
			printf("%s(%d,%d)\n",space,_key,_value);
		}
		return;
	}	
	for (int i=0;i<getNumKey();i++) {
		getPtr(i)->printNode(indent+1);
		printf("%s(%d)\n",space,getKey(i));
	}	
	if (getNumKey()>=0)
		getPtr(getNumKey())->printNode(indent+1);
}

// check if key is found in keys of current node, useful for duplicate checking
bool BTNode::isKeyFound(int _key) {
	// PLACE YOUR CODE HERE ...
	int i;
	for (i=0;i<=getNumKey()-1;i++){
        if (getKey(i)==_key) return true;
        
        }

	return false;
}

// remove entry in curent node, 2 cases for leaf and non-leaf respectively
void BTNode::removeEntry(entry& E) {
	// PLACE YOUR CODE HERE ...
	
}

// insert entry in curent node, 2 cases for leaf and non-leaf respectively
void BTNode::insertEntry(entry& E) {
	// PLACE YOUR CODE HERE ...
	int i,j,k;
		if(isLeafNode()){ //leafnode: put pointer before value
             for ( i=0; i<num_ptr-1;i++){
                 if (E.key<getKey(i))
                   break;
                 }
             k=1;
             for ( j=getNumKey();j>=0;j--){
                  if(j==i) { setKey(j, E.key);
                             setPtr(j, E.ptr);
                              }
                  else { setKey(j, getKey(num_ptr-1-k));
                         setPtr(j, getPtr(num_ptr-1-k));
                            k++;
                          }
                     }   }
         else{   //non leafnode: put pointer after value
             for ( i=0; i<num_ptr-1;i++){
                 if (E.key<getKey(i))
                   break;
                 }
             k=1;
             for ( j=getNumKey();j>=0;j--){
                  if(j==i) { setKey(j, E.key);
                             setPtr(j+1, E.ptr);
                              }
                  else { setKey(j, getKey(num_ptr-1-k));
                         setPtr(j+1, getPtr(num_ptr-k));
                            k++;
                          }
                     }    
              }               
         num_ptr++;
	
}

// Destroy BTNode 
BTNode::~BTNode() {
	if (level==0) bt->dnodes--; else bt->inodes--;
	FreeBlock(block);
}

// Create a new BTree
BTree::BTree() {
	dnodes=inodes=0;	// must be before BTNode creation !
	root=new BTNode(this,0);
}

// find a leaf entry with specified key
// if found, return true and set the value found; otherwise, return false
bool BTree::find(int _key,int& _value) {
	// PLACE YOUR CODE HERE ...
	BTNode* current;
	current=root;
//	int current_level=level;
	bool find2; //in non-leaf node, find a key > searching key.
               //in leaf node, find the searching key
	for(int i=root->level;i>=0;i-- ){
            if (i!=0){  //if not leaf, search range recursively
                  find2=false;    
                  for (int j=0;j<(current->num_ptr)-1;j++){
                      if (_key<current->getKey(j))
                         {current=current->getPtr(j); find2=true ;break;}
                         }        
                  if(find2==false) current=current->getPtr((current->num_ptr)-1);        
                              }
            else{  //if leaf node, look up for the value, return corresponding result
                 find2=false;
                 for (int j=0;j<(current->num_ptr)-1;j++){   
                    if (_key==current->getKey(j))
                       {_value=PtrToValue(current->getPtr(j));find2=true;break;}
                       }
          //       if(find) printf("find %d\t",_key);
          //       else printf("not find %d\t",_key);
                 return find2;
                }
           
    }
	
//	return false;
}

// print leaf entries in the specified key range (inclusive)
int BTree::printRange(int minkey,int maxkey) {	
	int num_result=0;
	// PLACE YOUR CODE HERE ...
	BTNode* current;
	current=root;
//	int current_level=level;
	bool find,stop=false; //in non-leaf node, find a key > searching key.
               //in leaf node, find the searching key
	for(int i=root->level;i>=1;i-- ){ //search in the non leaf nodes
                  find=false;
                  for (int j=0 ;j<(current->num_ptr)-1;j++){
                      if (minkey<current->getKey(j))
                         {current=current->getPtr(j); find=true ;break;}
                         }        
                  if(find==false) current=current->getPtr((current->num_ptr)-1);        
                            
    }//current becomes the pointer to leaf node
    for(int i=1;i<=dnodes&&stop==false;i++){//search in leaf node in a row
        for (int j=0;stop==false&&j<(current->num_ptr)-1;j++){   
                  if ((minkey<=current->getKey(j))&&(maxkey>=current->getKey(j)))
                       {printLeafEntry(current->getKey(j),PtrToValue(current->getPtr(j))); num_result++;}
                  else if (maxkey<current->getKey(j))
                       stop=true;
                       }
        current=current->getNextSib();
        
        }
	return num_result;
}

/*	insert entry into tree
	if not enough memory (i.e. available pages < tree height+1), return false
	N.B.: tree height can be found by 1+root->level
	
	Otherwise, return the result
	of calling "bool BTree::insert(BTNode* node,entry& E,entry& newE)"	*/
bool BTree::insert(int _key,int _value) {
	// PLACE YOUR CODE HERE ...
	if(getNumBlockAvail()<((root->level)+2)) return false;
	struct entry E={true, _key, ValueToPtr(_value)};
    struct entry newE={false, 0 , NULL};
	
	return (insert(root, E, newE ));
	
	
	return false;
}

/* insert the entry E into a leaf entry
   insert in a recursive manner recursively

   if node spliting occurs, set newE in use (and other fields of newE)
   so that the parent will insert the entry
   
   if newE is in use, insert newE into current node	*/
bool BTree::insert(BTNode* node,entry& E,entry& newE) {
	// PLACE YOUR CODE HERE ...
	
	BTNode* temp_sib; //used to store sibling info when spliting
	int value,i,j,k;
	
	if (E.key==18457)
	  int x=0;
	
	if(node->isLeafNode()) {
          BTNode* L=node;
         if (find(E.key,value))  return false;
         if (L->num_ptr<MaxPtrNum())  {//has room, just insert
               L->insertEntry(E);
               newE.useEntry=false;
               return true;                                                     
                                     }                 
         else{    //no room, split
             BTNode* L2=new BTNode(this, 0);
             BTNode* temp_sib;
             temp_sib=L->getNextSib();
              
             for ( i=0; i<MaxPtrNum()-1;i++){
                 if (E.key<L->getKey(i))
                   break;
                 }//find the position supposed to inserted
             if (i<=deg){           //split the node.  //should be in the first node, start moving      
                 for ( j=deg; j<MaxPtrNum()-1;j++){
                    L2->setKey(j-deg, L->getKey(j));
                    L2->setPtr(j-deg, L->getPtr(j));
                    }
                 L2->num_ptr=deg+2;
                 k=1;
                 for ( j=deg;j>=0;j--){
                     if(j==i) { L->setKey(j, E.key);
                                L->setPtr(j, E.ptr);
                              }
                     else { L->setKey(j, L->getKey(deg-k));
                            L->setPtr(j, L->getPtr(deg-k));
                            k++;
                          }
                     }                  
                 L->num_ptr=deg+2;
                         }
             else {// should be in the second node, start moving
                 L->num_ptr=deg+2;
                 k=1;
                 for ( j=deg;j>=0;j--){
                     if(j==i-deg-1) { L2->setKey(j, E.key);
                                L2->setPtr(j, E.ptr);
                              }
                     else { L2->setKey(j, L->getKey(MaxKeyNum()-k));
                            L2->setPtr(j, L->getPtr(MaxKeyNum()-k));
                            k++;
                          }
                     }                  
                 L2->num_ptr=deg+2;                  
                  }
                  
             newE.key=L2->getKey(0);//assign newE with the first pair of data in the second node
             newE.ptr=L2;
             newE.useEntry=true;
             L->setNextSib(L2);
             L2->setNextSib(temp_sib);
             if(L->level==root->level){//if it's a root, creat a new root to replace it
                    BTNode* newroot=new BTNode(this, L->level+1);
                    newroot->setPtr(0, L);
                    newroot->setKey(0, newE.key);
                    newroot->setPtr(1, newE.ptr); 
                    newroot->num_ptr=2;
                    root=newroot;                 
                                     }  
             return true;               
              }                 
                
                              }
     else{ // not leaf
          BTNode*  N=node; 
         bool HasLeafInserted;
         int midkey;
         
         for ( j=0 ;j<N->num_ptr-1;j++)
             if (E.key<N->getKey(j)) break;
         HasLeafInserted=insert(N->getPtr(j),E,newE);
         if(newE.useEntry==false) return HasLeafInserted;
         if (N->num_ptr<MaxPtrNum()) {//has room, just insert it
               N->insertEntry(newE);
               newE.useEntry=false;
               return HasLeafInserted;                                          
                                    }
         else{//no room, split
            midkey=N->getKey(deg);
            BTNode* N2=new BTNode(this, N->level); 
            
            for(i=deg+1;i<=2*deg;i++){// move the latter half portion to the second node
                  N2->setKey(i-deg-1,N->getKey(i));
                  N2->setPtr(i-deg-1,N->getPtr(i));                   
                                      }
            N2->setPtr(i-deg-1,N->getPtr(i)); 
            N->num_ptr=deg+1; // change the number of pointer used in the first node
            N2->num_ptr=deg+1;
            if(midkey>newE.key)// insert newE into a node, depending on the value vs value of midkey
                  N->insertEntry(newE); 
            else  N2->insertEntry(newE);
            newE.key=midkey;
            newE.ptr=N2;
            newE.useEntry=true;
            if(N->level==root->level){//if it's root, create a new root
                    BTNode* newroot=new BTNode(this, N->level+1);
                    newroot->setPtr(0, N);
                    newroot->setKey(0, newE.key);
                    newroot->setPtr(1, newE.ptr); 
                    newroot->num_ptr=2;
                    root=newroot;                 
                                    }  
            return HasLeafInserted;              
              } 
          
          
          }
	
	return false;
}

/*	remove leaf entry with specified key from tree
	return the result
	of calling "bool BTree::remove(BTNode* parent,int NodePtrPos,entry& E,entry& oldE)"	*/
bool BTree::remove(int _key) {
	// PLACE YOUR CODE HERE ...
	
	return false;
}

/* remove the leaf entry with key as E.key
   remove in a recursive manner recursively
   
   if half full constraint violated, set oldE in use (and other fields of newE)
   so that the parent will remove the related entry
   
   if oldE is in use, remove entry with key as oldE.key from current node	*/
bool BTree::remove(BTNode* parent,int NodePtrPos,entry& E,entry& oldE) {
	// PLACE YOUR CODE HERE ...
	
	return false;
}

// destroy the tree recursively
void BTree::destroy(BTNode* node) {
	if (node==NULL) return;	
	if (!node->isLeafNode()) {
    	for (int i=0;i<node->num_ptr;i++) {	// clear
    		BTNode* childNode=node->getPtr(i);
    		if (childNode!=NULL) destroy(childNode);
    	}
	}	
	delete node;
}

// free any used resouces
BTree::~BTree() {
	destroy(root);
}