zbtree.h

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

/****************************************************************** 

** Filename : ZBtree.h

** Copyright (c) 2001-2002 Computer Science & Technology Zhejiang University 

** Editor   : zhousen(周森)

** Date     : 2001-12-18 To 2002-01-05

** Version  : 1.00

******************************************************************/

#ifndef ZBTREE_H
#define ZBTREE_H

#include "Glob_Var.h"
#include "buffer.h"
#include "Intepretor.h"

//-------------------------------ZBTree_Index---------------------------------
// the head of index file
// it contains the basic informatior used for b+ tree
typedef struct TIndex_Head
{
  _F_FileAddr FirstEmptyBlock;  // the address of the first empty block
  _F_FileAddr LastEmptyBlock;   // the address of the last empty block
  _F_FileAddr FirstNewBlock;    // the address of the first new block 
  _F_FileAddr root;             // the address of the root
  _F_FileAddr start;            // the address of the most left node
  int         KeyAttrNum;	    // the number of fields(attributes) in primary key
  int         KeySize;         	// sizeof(Key_Attr) * KeyAttrNum
  int         MaxItemNum;       // the max number of keys in a node
}Index_Head;

// this class defines some operation on the head of the index file
// such as write and read the head into memery 
class ZBTree_Index
{
  public:
    ZBTree_Index();      
     ~ZBTree_Index();
    void    Create_Head(char* KeyStr);   // produce the information in the IdxHead 
    void    WriteHeadToFile();           // write the information to the head of the file 
    void    ReadHeadFromFile();          // read  the information form the head of the file
    void    SetKeyInfo(char* Key_Info);  // calculate the Keysize and KeyAttrNum
    int     GetKeySize();                // get the size of a key
    int     GetKeyAttrNum();             // get the key attribute number in a key 
    int     GetMaxItemNum();             // get the max number of items in a key
    char*   GetKeyInfo();                // get the key information

    _F_FileAddr GetRoot();               // get the File Point of the root
    _F_FileAddr GetStartNode();          // get the File Point of the leftmost node
    _F_FileAddr GetFirstNewBlock();      // get the File Point of the fisrt new block
    _F_FileAddr GetFirstEmptyBlock();    // get the File Point of the fisrt empty block
    _F_FileAddr GetLastEmptyBlock();     // get the File Point of the last empty block
    
    Index_Head IdxHead;  // the head of the index file for B+ tree 
      
  private:     
    char*  KeyInfo;      // a string record the information of the key
}; 
//-------------------------------ZBTree_Index----------------------------------

//*****************************************************************************

//-------------------------------ZBTree_Node-----------------------------------

// the struct of node
// Next_Empty_Block|NodeType | ItemOnNode | p[0],k[0],p[1],k[1],...,p[MaxItem]
class ZBTree_Node
{
  public:
    ZBTree_Node();
    ~ZBTree_Node();
    void Reset();                           // set p[i] = NULL,ItemOnNode = 0
    void ReadNodeFromFile(_F_FileAddr ptr); // read the content of the node from the file  
    void WriteNodeToFile( _F_FileAddr ptr); // write the content of the node to the file
    void InsertKeyInLeaf(_F_FileAddr pRec,pKey_Attr pPrimKey);    // insert a key in leaf node
    void DeleteKeyInLeaf(pKey_Attr pPrimKey);                     // delete a key in leaf node
    void InsertKeyNotInLeaf(pKey_Attr pPrimKey,_F_FileAddr pRec); // insert a key in non-leaf node
    void DeleteKeyNotInLeaf(pKey_Attr pPrimKey);                  // delete a key in non-leaf node
    void DeleteKey(pKey_Attr Key);               // delete the space occupied by key
    void DeleteKeyV_();                          // delete the fisrt key in the non-leaf node 
    void CopyKey(pKey_Attr Key1,pKey_Attr Key2); //copy key1 from key2
    bool IsNotEnoughPt();                        // too small points
    int  Compare(pKey_Attr Key1,pKey_Attr Key2); // 1--'>'   0--'='    -1--'<'
    pKey_Attr CreateKey(pKey_Attr Key1);         // create a new key equal to key1
  
  public:
    _F_FileAddr *p;                // p[MaxItem+1]; the array of points who point to the son nodes
    _F_FileAddr Next_Empty_Block;  // point to the next empty block
    pKey_Attr *k;                  // k[MaxItem];   the point_array of Keys
    bool    IsLeaf;                // 1--Leaf 0--Not leaf
    int     ItemOnNode;            // the number of the valid Keys
    int     MaxItem;               // the max number of key in a node
    int     KeySize;               // the size of a key
    char*   KeyInfo;               // the information of attributes in a key
};


//-------------------------------ZBTree_Node-----------------------------------

//*****************************************************************************

//----------------------------------ZBTree--------------------------------------
// the biggest value of depth in the b+tree,which is impossible to reach 
const int DEPTH = 20;  

// this class defines all operation on b+ tree
class ZBTree
{
  public:
    ZBTree();
    ~ZBTree();
    void Create(char* KeyStr);              // create the index file and initialize it
    void GrantRoot(_F_FileAddr ptr);        // grant root to an existed node 
    void DeleteNodeInFile(_F_FileAddr ptr); // delete a node in the index file
    // search the primary key,and place its address into pKeyLoca 
    bool Search(pKey_Attr pPrimKey,pKey_Location pKeyLoca);
    void Insert(pKey_Attr pPrimKey,_F_FileAddr pRec);  
    void Delete(pKey_Attr pPrimKey,_F_FileAddr& pRec);
    void Delete_Entry(_F_FileAddr L,pKey_Attr pPrimKey,_F_FileAddr pRec); 
    void Insert_Entry(_F_FileAddr L,pKey_Attr pPrimKey,_F_FileAddr pRec);

    // set pL_ and ppPrimkey and pIsLeftOfL_
    void SetL_(_F_FileAddr L,_F_FileAddr* pL_,pKey_Attr* ppPrimKey_,bool* pIsLLeftOfL_);
    // merge the two node pNodeL and pNodeL_
    void Merge(ZBTree_Node* pNodeL,ZBTree_Node* pNodeL_,pKey_Attr pPrimKey_,bool IsLLeftOfL_);
    // swap the L and L_ the parent node of L
    void SwapVariables(_F_FileAddr L,_F_FileAddr L_);
    // replace the key equal to Key_ with Key in the node pointed by ptr  
    void ReplaceKey(_F_FileAddr ptr,pKey_Attr Key_,pKey_Attr Key);
    // redistribute the tree when it can't emerge the tree
    void ReDistribute(ZBTree_Node* pNodeL,ZBTree_Node* pNodeL_,pKey_Attr pPrimKey_,bool IsLLeftOfL_,_F_FileAddr L);
    // create a new root node ----  po | pPrimKey | p1
    void CreateNewRoot(_F_FileAddr p0,pKey_Attr pPrimKey,_F_FileAddr p1);
        
    bool CanMerge(ZBTree_Node* pNode,ZBTree_Node* pNode_);  // whethe the two node can merge
    bool IsRoot(_F_FileAddr ptr); // the ptr : 0 -- root address 1 -- non-root address
    bool IsEmpty();               // the tree: 0 -- empty   1 -- non-empty 
    
    _F_FileAddr Parent(_F_FileAddr ptr);              // get the parent node address
    _F_FileAddr GetCurRecAddr(Key_Location KeyLoca);  // get the record address
    _F_FileAddr CreateNodeInFile();                   // get an empty node in the index file   

    Key_Location MoveToNextKey(Key_Location KeyLoca); // get the next key address
    Key_Location GetStart();  // get the leftmost key address
    Key_Location GetEnd();    // get the rightmost key address 
    
  private:
    void SetPath();                 // set path to *.idx
    _F_FileAddr SearchPath[DEPTH];  // the path of a search operation
    
};

#endif   //ZBTREE_H