bptree.h

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

#ifndef _BPTREE_H
#define _BPTREE_H

#include "Glob_Var.h"
#include "Buffer.h"
#include "Intepretor.h"

using namespace std;

const int DEPTH = 20;

////////////////////////////////////////////////////////////////////
// 索引文件头信息

typedef struct {
	_F_FileAddr  FirstEmptyBlock;
	_F_FileAddr  LastEmptyBlock;
	_F_FileAddr  FirstNewBlock;
	_F_FileAddr  root;
	_F_FileAddr  start;
	
	int         KeyAttrNum;
	int         KeySize; 
	int         MaxItemNum; 
} Index_Head;

/////////////////////////////////////////////////////////////////////
//管理索引文件的类

class BPTree_Index {
public:
	Index_Head IdxHead; //the head of the index file for B+ tree
	char *KeyInfo;

public:
	BPTree_Index();
	~BPTree_Index();

	void createHead(char *Keystr);
	void writeHeadToFile();
	void readHeadFromFile();
	void setKeyInfo(char *Keystr);

	int getKeySize(); 
	int getKeyAttrNum();
	int getMaxItemNum();
	char* getKeyInfo();

	_F_FileAddr getRoot();
	_F_FileAddr getStartNode();
	_F_FileAddr getNewBlock();
	_F_FileAddr getFirstEmptyBlock();
	_F_FileAddr getLastEmptyBlock();
};

///////////////////////////////////////////////////////////////////
// 管理树节点的类
// 节点的基本结构: NextEmptyBlock | IsLeaf | ItemOnNode | p[0],k[0],...,p[MaxItemNum] 

class BPTreeNode {
public:
	bool IsLeaf;
	int ItemOnNode;
	int MaxItem;
	int KeySize;
	char *KeyInfo;

public:
	pKey_Attr *k;  //the array of pointers to son nodes
	_F_FileAddr *p;  //the array of pointers to struct including key values
	_F_FileAddr Next_Empty_Block;  //pointer to the next empty block

public:
	BPTreeNode();
	~BPTreeNode();

	void initialize();
	void readNodeFromFile(_F_FileAddr pf);
	void writeNodeToFile(_F_FileAddr pf);

	void insertKeyInLeaf(_F_FileAddr pRec, pKey_Attr pPrimaryKey);
	void deleteKeyInLeaf(pKey_Attr pPrimaryKey);
	void insertKeyNotLeaf(pKey_Attr pPrimKey, _F_FileAddr pRec);
    void deleteKeyNotLeaf(pKey_Attr pPrimKey); 
	void deleteKeySpace(pKey_Attr Key);
	void deleteFirstKey();
	bool isNotEnoughPoints();
	int  compare(pKey_Attr Key1, pKey_Attr Key2); 
	pKey_Attr createKey(pKey_Attr Key); 

};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 管理B+树的类

class BPTree {
private:
    void setPath();  // set path to *.idx
    _F_FileAddr SearchPath[DEPTH];
  
 public:
    BPTree();
    ~BPTree();
    void create(char* KeyStr);  
    void grantRoot(_F_FileAddr ptr); 
    void deleteNodeInFile(_F_FileAddr ptr);

	Key_Location moveToNextKey(Key_Location KeyLoca);
    Key_Location getStart(); 
    Key_Location getEnd(); 

	bool isRoot(_F_FileAddr ptr); 
    bool isEmpty(); 

    bool search(pKey_Attr pPrimKey, pKey_Location pKeyLoca);
    void insert(pKey_Attr pPrimKey, _F_FileAddr pRec); 
	void insert_entry(_F_FileAddr L, pKey_Attr pPrimKey, _F_FileAddr pRec);
    void myDelete(pKey_Attr pPrimKey, _F_FileAddr& pRec);
    void delete_entry(_F_FileAddr L, pKey_Attr pPrimKey, _F_FileAddr pRec); 

	_F_FileAddr getParent(_F_FileAddr ptr);   
    _F_FileAddr getCurRecAddr(Key_Location KeyLoca); 
    _F_FileAddr createNodeInFile();   
	
	bool canCoalesce(BPTreeNode* pNode, BPTreeNode* pNode_);
    void coalesce(BPTreeNode* pNodeL, BPTreeNode* pNodeL_, pKey_Attr pPrimKey_, bool IsLLeftOfL_);
    void swapVariables(_F_FileAddr L, _F_FileAddr L_);
    void setNb(_F_FileAddr L, _F_FileAddr* pL_, pKey_Attr* ppPrimKey_, bool* pIsLLeftOfL_);
    void reDistribute(BPTreeNode* pNodeL, BPTreeNode* pNodeL_, pKey_Attr pPrimKey_, bool IsLLeftOfL_, _F_FileAddr L); 
    void replaceKey(_F_FileAddr ptr, pKey_Attr Key_, pKey_Attr Key);  
	void createNewRoot(_F_FileAddr p0, pKey_Attr pPrimKey, _F_FileAddr p1);
 
};

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


#endif //~