mybplustree.cpp

B+树的演示程序

// MyBPlusTree.cpp : 实现文件
//

#include "stdafx.h"
#include "MyBPlusTree.h"
#include "MyControl.h"

// MyBPlusTree

MyBPlusTree::MyBPlusTree()
{	
	m_levels = 0;
	m_nodes = 0; 
	m_keys = 0;
	m_root = NULL;
	m_current = NULL;
	N = MINIMUS_NUMBER_OF_NODE;
	M = (N+1)/2;
}

MyBPlusTree::~MyBPlusTree()
{
	if(m_root)
		DeleteTree();
}

void MyBPlusTree::SetParent(void* pParent)
{
	m_pParent = pParent;
}
// MyBPlusTree 成员函数
bool MyBPlusTree::Create(int n/*=MINIMUS_NUMBER_OF_NODE*/)
{
	if( (n<MINIMUS_NUMBER_OF_NODE) || (n > MAXIMUM_NUMBER_OF_NODE) )
		return false;
	MyNode::SetMaxNumber(n);
	N = n;
	M = (N+1)/2;
	m_root = new MyLeaf();
	if(!m_root)
		return false;
	if(!m_root->Create())
		return false;
	m_current = m_root;
	m_levels++;
	m_nodes++;
	return true;
}
long* MyBPlusTree::Search(long key)				// if Null , there isn't this key
{
	int i;
	if( (!m_root) || (!m_current) )
		return NULL;
	i = SearchKey(m_root,key,1);

	if(m_current->k[i] == key)
		return (long*)m_current->p[i];
	else
		return NULL;
	// Draw search key: (MyNode*) m_current->m_itype = 1; node.i .
}
int MyBPlusTree::SearchKey(MyNode* node,long key,int level)
{
	int i;
	i = node->Search(key);
	m_current = node;
    if(node->m_level > level)
		i = SearchKey((MyNode*)node->p[i],key,level);
	return i;
}

int MyBPlusTree::Insert(long key,long* pkey)	// return number of new node , -1 already this key ,-2 memory error
{
	// Is there key in B+ tree ?
    if(Search(key))		return -1;

	int n = m_nodes;
	if(!InsertKey(key,(MyNode*)pkey,1))
        return -2;	// fail to split new node!
	m_keys++;
	return (m_nodes - n);
}
bool MyBPlusTree::InsertKey(long key,MyNode* pnode,int level)
{
	int i;
	if( (!m_root) || (!m_current) )
		return false;
	i = SearchKey(m_root,key,level);

	// Draw Insert key: m_itype; (MyNode*) m_current, (MyNode*)/(long*) pnode .
	((MyControl*)m_pParent)->m_bSleep = true;
	if(m_current->m_level == 1)
		((MyControl*)m_pParent)->Display(m_current->k[0],m_current->m_level,10,(void*)pnode);
	else
		((MyControl*)m_pParent)->Display(((MyNode*)m_current->p[i])->k[0],m_current->m_level-1,11,(void*)pnode);

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

bool MyBPlusTree::SplitNode(MyNode* node,long key,MyNode* pnode,int level,int i)
{
	int m;
	MyNode* nnode = NULL;
	if(node->m_level == 1)
		nnode = new MyLeaf();
	else
		nnode = new MyBranch(node->m_level);
	if(!nnode) return false;
	if(!nnode->Create())	return false;
	m_nodes++;
	m = (i<M) ? 1 : 0;

	node->SplitNode(nnode,m);

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

	// Draw Split Node: node->m_itype = 2; MyNode* node,MyNode* nnode .
	((MyControl*)m_pParent)->m_bSleep = true;
	((MyControl*)m_pParent)->Display(node->k[0],node->m_level,13,(void*)nnode);

	if(node->m_level == m_levels)
	{
		// 根结点时
		m_root = new MyBranch;
		if(!m_root)		return false;
		if(!m_root->CreateRoot(nnode->GetMinKey(),node,nnode))
			return false;		
		m_levels++;
		m_nodes++;
		
		// Draw New Root: m_root->m_itype = 1;
		((MyControl*)m_pParent)->m_bSleep = true;
		((MyControl*)m_pParent)->Display(nnode->k[0],nnode->m_level,12);
		return true;
	}
	else	
		return InsertKey(nnode->GetMinKey(),nnode,level+1);
}
int MyBPlusTree::Delete(long key)				// return number of del node , -1 none this key , -2 there is no key in B+key
{
	if(m_keys == 0)		return -2;
	if(!Search(key))	return -1;

	int n;
	n = m_nodes;
    DeleteKey(key,1);
	m_keys--;
	return (n - m_nodes);
}
void MyBPlusTree::DeleteKey(long key,int level)
{
	int i,m;
	i = SearchKey(m_root,key,level);
	//MyNode* tnode;

	// 删除至根结点时
	if(level == m_levels)
	{
		/*
		tnode = m_current;
		((MyControl*)m_pParent)->m_bSleep = true;
		((MyControl*)m_pParent)->Display(m_root->k[0],m_root->m_level,20,NULL,i);
		m_current = tnode;
		if( (m_root->m_n = 1) && (m_levels > 1) )
		{
			tnode = m_current;
			 ((MyControl*)m_pParent)->m_bSleep = true;
			 ((MyControl*)m_pParent)->Display(m_root->k[0],m_root->m_level,21);
			m_current = tnode;
		}*/
		m_root->Delete(i);
		if( (m_root->m_n < 1) && (m_levels > 1) )
		{
			MyNode* temp;
			temp = (MyNode*)m_root->p[0];
			m_root->Release();
			delete m_root;
			m_root = temp;
            m_levels--;
			m_nodes--;
			// Draw delete root: m_root;
		}
		return;
	}
	m = (level == 1) ? M : (M-1);
	// Draw delete key: m_current,i .

	/*
	tnode = m_current;
	((MyControl*)m_pParent)->m_bSleep = true;
	((MyControl*)m_pParent)->Display(m_current->k[0],m_current->m_level,20,NULL,i);
	m_current = tnode;
	*/

	if(m_current->m_n > m)
		m_current->Delete(i);	
	else
		JudgeNbrNode(m_current,key,level,i);
	return;
}

int MyBPlusTree::JudgeNbrNode(MyNode* node,long key,int level,int i)
{
	int j,m;
	long temp;
	MyNode* lnode = NULL;
	MyNode* rnode = NULL;
	j = SearchKey(m_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 = (MyNode*)m_current->p[j-1];
		if(lnode->m_n > M-1+m)
		{
			node->Delete(i);
			temp = node->GetMinKey();

			// Draw get key from left: node
			node->GetKeyFromLeft(lnode);			

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

			// Draw get key from Right: node
			node->GetKeyFromRight(rnode);
			

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

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

	if(lnode)
	{
		// 有左相邻结点时，将该结点与左邻结点合并，将该结点向左移
		// Draw unite with left: lnode
		temp = lnode->UniteRight(node);
		if(node)
		{
			node->Release();
			delete node;
		}
	}
	else
	{
		// 有右相邻结点时，将该结点与右邻结点合并，将右结点移入该结点
		// Draw unite with right: node
		temp = node->UniteRight(rnode);
		if(rnode)
		{
			rnode->Release();
			delete rnode;
		}
	}
	
	m_nodes--;

	DeleteKey(temp,level+1);
	return -1; 
}
void MyBPlusTree::Update(long key,int level)
{
	int i;
	i = SearchKey(m_root,key,level);

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

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

void MyBPlusTree::DeleteTree()
{
	if(m_keys == 0)
		return ;
	DelTree(m_root);
	m_root = NULL;
	m_current = NULL;
	m_levels = 0;
	m_nodes = 0;
	m_keys = 0;
}
void MyBPlusTree::DelTree(MyNode* node)
{
	if(m_levels == 1)
	{
		m_root->Release();
		delete m_root;
		m_root = NULL;
		return;
	}
	int i,j,m;	
	m = node->m_level;
	j = node->m_n;
	MyNode** pnode = new MyNode*[N+1];

	if(m > 1)
		for(i=0;i<j+1;i++)
			pnode[i] = (MyNode*)node->p[i];
	if(node)
	{		
		node->Release();
        delete node;
	}

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