bplustree.cpp

B+树的演示程序

// BPlusTree.cpp

#include "BPlusTree.h"
#include "Node.h"
#include <iostream>
#include <time.h>

using namespace std;

BPlusTree::BPlusTree(int n/*=3*/)
{
	Node::SetMaxNum(n);
	my_root = new Leaf();
	my_crtNode = my_root;
	my_level = 1;
	my_node = 1; 
	my_key = 0;
	N = n;
	M = (N+1)/2;
}

BPlusTree::~BPlusTree()
{
	DelTree(my_root);
}

long* BPlusTree::Search(long key)
{
	int i;
	i = SearchKey(my_root,key,1);

	if(my_crtNode->k[i] == key)
		return (long*)((Leaf*)my_crtNode)->p[i];
	else
		return NULL;
}

int BPlusTree::Insert(long key,long* pkey)
{
	// Is there key in B+ tree ?
    if(Search(key))		return -1;

	int n = my_node;
	if(!InsertKey(key,(Node*)pkey,1))
        return -2;	// fail to split new node!
	my_key++;
	return (my_node - n);
}

int BPlusTree::Delete(long key)
{
	if(my_key == 0)		return -2;
	if(!Search(key))	return -1;

	int n;
	n = my_node;
    DeleteKey(key,1);
	my_key--;
	return (n - my_node);
}

void BPlusTree::Order(Node* root)
{
	Node* node;
	node = root;
	while(node->my_level > 1)
		node = node->p[0];
	do
	{
		for(int i=0;i<node->my_num;i++)
			cout << node->k[i]<<", ";
		node = (Node*)((Leaf*)node)->my_next;
	}while(node);
	return;
}

int BPlusTree::SearchKey(Node* node,long key,int level)
{
	int i;
	i = node->Search(key);
	my_crtNode = node;
    if(node->my_level > level)
		i = SearchKey(node->p[i],key,level);
	return i;
}

bool BPlusTree::InsertKey(long key,Node* pnode,int level)
{
	int i;
	i = SearchKey(my_root,key,level);

	if(my_crtNode->my_num < N)
	{
		my_crtNode->Insert(key,pnode,i);
		return true;
	}
	else
		return SplitNode(my_crtNode,key,pnode,level,i);
}

bool BPlusTree::SplitNode(Node* node,long key,Node* pnode,int level,int i)
{
	int m;
	Node* nnode = NULL;

	m = (i<M) ? 1 : 0;
	if(node->my_level == 1)
		nnode = (Node*)(new Leaf());
	else
		nnode = new Node(node->my_level);
	if(!nnode)	return false;

	node->SplitNode(nnode,m);

	my_node++;

    if(i < M)
		node->Insert(key,pnode,i);
	else
		nnode->Insert(key,pnode,i-M);

	if(node->my_level == my_level)
	{
		// 根结点时
		my_root = new Node(nnode->GetMinKey(),node,nnode,++my_level);
		my_node++;
		if(my_root)		return true;
		else			return false;
	}
	else	
		return InsertKey(nnode->GetMinKey(),nnode,level+1);
}

void BPlusTree::DeleteKey(long key,int level)
{
	int i,m;
	i = SearchKey(my_root,key,level);

	// 删除至根结点时
	if(level == my_level)
	{
		my_root->Delete(i);
		if( (my_root->my_num < 1) && (my_level > 1) )
		{
			Node* temp;
			temp = my_root->p[0];
			delete my_root;
			my_root = temp;
            my_level--;
			my_node--;
		}
		return;
	}
	m = (level == 1) ? M : (M-1);
	if(my_crtNode->my_num > m)
		my_crtNode->Delete(i);
	else
		JudgeNbrNode(my_crtNode,key,level,i);
	return;
}

int BPlusTree::JudgeNbrNode(Node* node,long key,int level,int i)
{
	int j,m;
	long temp;
	Node* lnode = NULL;
	Node* rnode = NULL;
	j = SearchKey(my_root,key,level+1);
	//current node is the father node ,he has 2-3 children: lnode, node, rnode.
	m = (level == 1) ? 1 : 0;

	if(j > 0)
	{
		// 左相邻结点有可移动的键值
		lnode = my_crtNode->p[j-1];
		if(lnode->my_num > M-1+m)
		{
			node->Delete(i);
			temp = node->GetMinKey();

			node->GetKeyFromLeft(lnode);

			Update(temp,level+1);
			return 1;
		}
	}
	if(j < my_crtNode->my_num)
	{
		// 右相邻结点有可移动的键值
		rnode = my_crtNode->p[j+1];
		if(rnode->my_num > M-1+m)
		{
			node->Delete(i);
			
			node->GetKeyFromRight(rnode);

			Update(rnode->GetMinKey(),level+1);
			return 2;
		}
	}

	// 左右都无可移动键值
	
	node->Delete(i);

	if(lnode)
	{
		// 有左相邻结点时，将该结点与左邻结点合并，将该结点向左移
		temp = lnode->UniteRight(node);
		if(node->my_level == 1)
			delete (Leaf*)node;
		else
			delete node;
	}
	else
	{
		// 有右相邻结点时，将该结点与右邻结点合并，将右结点移入该结点
		temp = node->UniteRight(rnode);
		if(rnode->my_level == 1)
			delete (Leaf*)rnode;
		else
			delete rnode;
	}
	
	my_node--;

	DeleteKey(temp,level+1);
	return -1; 
}

void BPlusTree::Update(long key,int level)
{
	int i;
	i = SearchKey(my_root,key,level);

	if(i == 0)	i++;
	my_crtNode->k[i-1] = my_crtNode->GetMinKey(i);

	if(level < my_level)
		Update(key,level+1);
	return;
}

void BPlusTree::DelTree(Node* node)
{
	if(my_level == 1)
	{
		delete node;
		return;
	}
	int i,j,m;	
	m = node->my_level;
	j = node->my_num;
	Node** pnode = new Node*[N+1];

	if(m > 1)
		for(i=0;i<j+1;i++)
			pnode[i] = node->p[i];	

	cout << "\t\tfree node : [";
	for(i=0;i<j-1;i++)
		cout << node->k[i]<<",";
	cout << node->k[i] << "]\n";
	
	if(node->my_level == 1)
        delete (Leaf*)node;
	else
		delete node;

	if(m > 1)
		for(i=0;i<j+1;i++)
			DelTree(pnode[i]);
	delete [] pnode;
	return ;
}

void BPlusTree::Display()
{
	cout<<"\nNow B+ tree has "<<my_level<<" level, "<<my_node<<" nodes, "<<my_key<<"keys!"<<endl;
	DisplayNode(my_root);
	cout<<endl<<endl;
}
void BPlusTree::DisplayNode(Node* node)
{
	if(my_key == 0)
	{
		cout<<"B+ tree have none key! Please insert some one. \n";
		return;
	}
	int i;
	for(i=5;i>node->my_level;i--)
		cout<<"\t";
	cout<<"[";
	for(i=0;i<node->my_num-1;i++)
		cout<<node->k[i]<<",";
	cout<<node->k[i]<<"]\n";

	if(node->my_level > 1)
		for(i=0;i<node->my_num+1;i++)
			DisplayNode(node->p[i]);
	return;
}

int main(void)
{
	int i,	// 选择命令标识
		j,	// 用于循环
		n,	// 记录手动输入数据的个数
		nr,	// 记录随机数的个数
		m,	// 记录功能函数和返回值
		num;// N值
	long k;	// 记录要删除的值
	i=j=n=nr=m=0;
	num = 3;
	long a[15] = {5,60,53,45,12,3,54,55,1,2,7,6,4,8,10};	// 预存数
	long b[MAXRANDKEY];		// 随机数
	long c[MAXENTERKEY];	// 手动输入数

	system("CLS");
	cout << "\t\tWelcome !\n\tThis is a small program to try the work progress of B+ tree.\n\n\tMake by zrf(07041177).\n";

	cout << "first you should create a new B+ tree.\n Please enter the N of B+ tree(3--100) :";
	cin >> num;
	while (num < 3 || num > 100)
	{
		cout << "You enter an incorrect number. Please try again (3-100):";
		cin >> num;
	}
	BPlusTree* tree = new BPlusTree(num);
	cout << "You have already create a " << num << "maximum number B+ tree now.";
	do
	{
		cout << "\n\n\nThe fuction of the program:(1-6)\n";
		cout << "\t1.\tInsert a key;\n";
		cout << "\t2.\tDelete a key;\n";
		cout << "\t3.\tSort the Key of B+ tree;\n";
		cout << "\t4.\tDisplay the B+ btree;\n";
		cout << "\t5.\tInsert some prepared key:{5,60,53,45,12,3,54,55,1,2,7,6,4,8,10}\n";
		cout << "\t6.\tInsert some randam ( 1 - 160 ) key: \n";
		cout << "\t7.\tDelete the B+ tree and create a new one.\n";
		cout << "\t8.\tExit the program.\n";
		cout << "Please enter your choise:(1-8) ";	
		cin >> i;;
		switch(i)
		{
		case 1:			
			if(n > MAXENTERKEY)
			{
				cout << "Sorry you have got the limit .You can't enter anyone else .\n Please try another fuction.";
				break;
			}
			cout << "\t\tFuction 1.\n\tEnter the key(long) to insert: ";
			cin >> c[n];
			j = tree->Insert(c[n],&c[n]);
			if(j == -2)
				cout << "Fail to malloc the memory of new node!\n";
			else if(j == -1)
				cout << "This key is in the B+ tree now! Please try another one.\n";
			else if(j >= 0)
			{
				cout << "OK! and insert the key cause "<<c[n]<<" new nodes.\n";
				tree->Display();
			}
			n++;
			break;
		case 2:
			cout << "\t\tFuction 2.\n\tEnter the key(long) to delete: ";
			cin >> k;
			j = tree->Delete(k);
			if(j == -2)
				cout << "Sorry!There is none key in the B+ tree.\nPlease insert someone.\n";
			if(j == -1)
				cout << "Sorry! There isn't "<< k <<" in the B+ tree.\n";
			else if(j >= 0)
			{
				cout << "OK! and delete the key cause "<< j <<" delete nodes.\n",j;
				tree->Display();
			}
			break;
		case 3:
			cout << "\t\tFuction 3.\n\tNow sort the key of the B+ tree: \n\t";
			tree->Order(tree->my_root);
			break;
		case 4:
			tree->Display();
			break;
		case 5:	
			for(j=0;j<15;j++)
			{
				cout << "  Now insert "<< a[j] <<"." << endl;

				m = tree->Insert(a[j],&a[j]);
				if(m == -2)
					cout << "Fail to malloc the memory of new node!\n";
				else if(m == -1)
					cout << "This key is in the B+ tree now! Please try another one.\n";
				else if(m >= 0)
				{
					cout << "OK! and insert the key cause "<< a[j] <<" new nodes.\n";
					tree->Display();
				}

				tree->Display();
				cout << "\n\n\n================================================\n\n\n";
			}
			break;
		case 6:
			cout << "Please enter the number of (1-160)randam key: (1-1024)";
			cin >> k;
			srand( (unsigned)time( NULL ) );
			for(j=1;j<k;j++)
			{
				nr++;
				if(nr > MAXRANDKEY)
				{
					cout << "Sorry you have got the limit .You can't insert anyone random else .\n Please try another fuction.";
					break;
				}
				b[nr] = rand()%160;
				cout << "  Now insert "<< b[nr] <<"." << endl;
				
				m = tree->Insert(b[nr],&b[nr]);
				if(m == -2)
					cout << "Fail to malloc the memory of new node!\n";
				else if(m == -1)
					cout << "This key is in the B+ tree now! Please try another one.\n";
				else if(m >= 0)
					cout << "OK! and insert the key cause "<< b[nr] <<" new nodes.\n";

				tree->Display();
				cout << "\n\n\n================================================\n\n\n";
			}
			break;
		case 7:
				cout << "Now Delete B+ tree:"<<endl;
				delete tree;
				cout << "Delete B+ tree successful."<<endl;
				cout <<endl<<"Now please enter the maximum number of the new B+ tree (3--100):";
				cin >> num;
				while (num < 3 || num > 100)
				{
					cout << "You enter an incorrect number. Please try again (3-100):";
					cin >> num;
				}
				tree = new BPlusTree(num);
				n = nr = 0;
				cout << "You have already create a " << num << "maximum number B+ tree now.";
			break;
		case 8:
			break;
		case 9:
			for(int i=0;i<nr+1;i++)
			{
				cout << "\tnow delete "<<b[i];
				tree->Delete(b[i]);
				tree->Display();
				cout << "\n\n\n================================================\n\n\n";
			}
			break;
		default:
			printf("Range EEROR! Please re-enter!");
			break;
		}
	}while(i != 8);

	cout << "Now Delete B+ tree." << endl;
    delete tree;

	return 0;
}