btree.h

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

#ifndef __BTREE
#define __BTREE

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "pagemgr.h"

class BTree;
class BTNode;

#define KEY_SIZE sizeof(int)

#define PTR_SIZE sizeof(BTNode*)

struct entry {
	bool useEntry;	// only used in recursive insert and remove algorithms
					// true means the child passes entries to be inserted/removed in current level
					
	int key;		// key of the entry
	
	BTNode* ptr;	// ptr field of the entry
					// can hold a type casted int. value
};

void InitByDegree(int cachesize,int _deg);	// initialize page pool



// converting a value to ptr type (for leafnode)
BTNode* ValueToPtr(int value);

// converting ptr type to a value (for leafnode)
int PtrToValue(BTNode* ptr);


// BTNode

class BTNode {
private:
	char* BlockAddr;	// address to the page block being used
	BTree* bt;			// pointer to B+ -tree
public:
	int num_ptr; 	// # of used ptr entries
	int level;  	// level in the tree , 0 for leaf node
	int block;   	// disc block
	
    BTNode(BTree* _bt,int _level);			// constructor
    
    int getNumKey() { return (num_ptr-1);} 	// # of used keys
    
    int getKey(int pos);				// get key at position "pos"
	
	void setKey(int pos,int _key);		// set key at position "pos"
	
	BTNode* getPtr(int pos);			// get ptr. at position "pos"
	
	void setPtr(int pos,BTNode* _ptr);	// set ptr. at position "pos"
    
    BTNode* getNextSib();				// get next sibling node
    
    void setNextSib(BTNode* nextNode);	// set next sibling node
    
    bool isLeafNode() {return (level==0);}	// check if it is leaf
    
    void printNode(int indent);		// print node recursively
    
    void insertEntry(entry& E);		// insert the entry E 
    
    void removeEntry(entry& E);    	// remove entry with the key E.key
    
    bool isKeyFound(int _key); 		// check if key found, for duplicate checking        
    
    virtual ~BTNode();		// destructor
};


// BTree

class BTree {
public:
    BTNode* root;	// root-node
    
    int dnodes,inodes;	// # of data and internal nodes
private:
	// insert entry recursively
    bool insert(BTNode* node,entry& E,entry& newE);		
    
    // remove entry recursively
    bool remove(BTNode* parent,int NodePtrPos,entry& E,entry& oldE);
    
    // delete the tree recursively
	void destroy(BTNode* node);
public:
    BTree();       // constructor
    
    bool find(int _key,int& _value);	// find entry with specified key
    
    // print entries in the specified key range (inclusive)
    // , and return the number of results
    int printRange(int minkey,int maxkey);
    
    // insert entry (_key,_value) into tree
    // true if success, false otherwise
    bool insert(int _key,int _value);	
    
    // remove entry with specified key
    // true if success, false otherwise    
    bool remove(int _key);    
    
    // print the tree by printing the root
    void printTree() { root->printNode(0); }    
    
    virtual ~BTree();	// destructor
};

#endif // __BTREE