btree.hpp

一个简单的b tree 实现代码

#define M 2
/* B 树的阶，即非根节点中键的最小数目。 
* 有些人把阶定义为非根节点中子树的最大数目。 
*/


#include <string>
  using namespace std;
//#define key_string 1
#ifdef key_string
typedef string typekey;


#else
typedef long int typekey;
#endif

typedef struct btnode {    /* B-Tree 节点 */
    int d;    /* 节点中键的数目 */ 
	typekey k[2*M+1];    /* 键 */
	typekey min;
	char *v[2*M+1];    /* 值 */
	struct btnode *p[2*M+1];    /* 指向子树的指针 */
} node, *btree;
/*
* 每个键的左子树中的所有的键都小于这个键，
* 每个键的右子树中的所有的键都大于等于这个键。 
* 叶子节点中的每个键都没有子树。 
*/ 

/* 当 M 等于 1 时也称为 2-3 树 
*    +----+----+
*    | k0 | k1 |                     
*  +-+----+----+--- 
*  | p0 | p1 | p2 | 
*  +----+----+----+
*/ 


class   tree 
{
	private: 
	 
	  	
 		  char *InsValue; /* 与要插的键相对应的值 */ 
 		  
 		  int btree_disp; /* 查找时找到的键在节点中的位置 */  
			 int flag; /* 节点增减标志 */ 
			 int btree_level  ; /* 多路树的高度 */ 
			 int btree_count  ; /* 多路树的键总数 */ 
			 int node_sum  ;  /* 多路树的节点总数 */ 
			 int level; /* 当前访问的节点所处的高度 */ 
			 btree NewTree; /* 在节点分割的时候指向新建的节点 */ 
			 typekey InsKey; /* 要插入的键 */ 
 		     typekey pop_key;
 		  
			int print_tree(btree t, int);


  public:
	    		tree();
			~tree(); 
				btree root;

	  btree search(typekey, btree,int*);
			btree insert(typekey,btree);
			btree insert(typekey,btree,char*);
			btree delete_n(typekey,btree);
			int height(btree);
			int count( );
			double payload(btree);
			btree deltree(btree);

			  void InternalInsert(typekey, btree);
			  btree InternalInsert(typekey, btree,char*,int);
			  void InsInNode(btree, int);
			   void InsInLeafNode(typekey, char*,btree, int);
			   void InsInIndexNode( btree,btree, int);


			  btree	SplitLeafNode(typekey key,char*,btree nt,btree t, int d ) ;
			  btree	SplitNode(typekey key,char*,btree nt,btree t, int d ) ;
			  btree NewRoot(btree);
			 btree NewRoot(btree,btree);
			  void InternalDelete(typekey, btree,int);
			  void InternalDelete1(typekey, btree,int);
			  /*void JoinNode(btree, int);
			  void MoveLeftNode(btree t, int);
			  void MoveRightNode(btree t, int);*/
			  float use_rate(btree );
			  void DelFromNode(btree t, int);
			  btree MergeNode(btree t1,btree t2,int);
			  btree MergeLeafNode(btree t1,btree t2,int,int);
			  btree MergeLeafNodeBack(btree t1,btree t2,int,int);
			  btree FreeRoot(btree);
				int print();
			  btree delall(btree,int);
			  void Error(int,typekey);

			  btree RebuildIndexNode(btree t) ;
	  	
	  	
};