bplustree.cpp

有计算机图形学、图像处理、dbms、sniffer、中游俄罗斯外挂、othello、遗传算法、舌苔分析等程序。

// BplusTree.cpp: implementation of the CBplusTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Database.h"
#include "BplusTree.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CBplusTree::CBplusTree()
{
   m_sqt=m_root=NULL;
   ROOT=SQT=DB_NULL;
}

CBplusTree::CBplusTree(UINT main_id,BOOL D,BYTE KT,BYTE KN,WORD KL,UINT currentf)

{
    MainID=main_id;
	Dup=D;
	KeyType=KT;
	KeyNum=KN;
	KeyLength=KL;
	M=5;//4000/(2*sizeof(BYTE)+KeyLength+sizeof(PDB));//毛古古
	CurrentFile=currentf;
	m_sqt=m_root=NULL;
	ROOT=SQT=DB_NULL;
	m_uiKeyCount=0;
	m_uiEffectKey=0;
	m_dbFillDegree=0.0;
}


CBplusTree::~CBplusTree()
{
	
}

BTNODE * CBplusTree::GetRoot()
{
	return m_root;
}
PDB CBplusTree::GetSqt()
{
	return SQT;
}
//在pos处删除所有指定键
int CBplusTree::DeleteBTreeAll(KEY key, PDB pdbNode, int pos)
{
    int i=pos;
	bool end=false;
	BTNODE *pNode=CMemory::ReadIDXBlock(pdbNode,M,KeyType,KeyLength);
	if(Dup)
	{
		while(!end&&pNode)
		{
			for(;i<int(pNode->keynum)&&pNode->key[i]==key;++i)
			{
				if(pNode->pointer.address1.recptr[i]!=DB_NULL)
				{
					pNode->pointer.address1.recptr[i]=DB_NULL;
					
					--m_uiEffectKey;
				}
			}
			pNode->wtag=0x1;
			if(i<int(pNode->keynum))
				end=true;
			else
			{
				pNode=CMemory::ReadIDXBlock(pNode->pointer.address1.right
					,M,KeyType,KeyLength,pNode);//pNode.ReadBrother(f,RIGHT,M);
				i=0;
			}
		}
	}
	else
	{
	    pNode->pointer.address1.recptr[pos]=DB_NULL;
		pNode->wtag=0x1;
	}
	m_dbFillDegree=double(m_uiEffectKey)/double(m_uiKeyCount);
    return 0;
}
//只删除一个指定键
BOOL CBplusTree::DeletePtr(KEY key, PDB pdbNode, int pos, PDB recptr)
{
    int i=pos;
	if(i==-1)
		i=0;
	bool end=false;
	BTNODE *pNode=CMemory::ReadIDXBlock(pdbNode,M,KeyType,KeyLength);
	if(Dup)
	{
		while(!end&&pNode)
		{
			for(;i<int(pNode->keynum)&&pNode->key[i]<=key&&!end;++i)
			{
				if(pNode->pointer.address1.recptr[i]==recptr)//等于要删的记录
				{
					pNode->pointer.address1.recptr[i]=DB_NULL;
					
					--m_uiEffectKey;
					end=true;
				}
			}
			pNode->wtag=0x1;
			if(i<int(pNode->keynum))
				end=true;
			else if(!end)
			{
				pNode=CMemory::ReadIDXBlock(pNode->pointer.address1.right
					,M,KeyType,KeyLength,pNode);//pNode.ReadBrother(f,RIGHT,M);
				i=0;
			}
		}
	}
	else
	{
	    pNode->pointer.address1.recptr[pos]=DB_NULL;
		pNode->wtag=0x1;
	}
	m_dbFillDegree=double(m_uiEffectKey)/double(m_uiKeyCount);
    return 0;
}
int CBplusTree::InsertBTree(KEY key, PDB db_addr,PDB pdbNode,int pos)
{
    KEY x=key;//用于分割的关键值
    BTNODE *pApNode=NULL;
	BTNODE *pNode=CMemory::ReadIDXBlock(pdbNode,M,KeyType,KeyLength);
	BTNODE *trace;
	bool finished=false;
    BOOL bSP=0;
	
    unsigned int s=0;
	
    while(pNode&&!finished)
	{
        bSP=InsertKey(pNode,x,db_addr,pos,pApNode);
		if(bSP==-1)
			--m_uiKeyCount;
		if(bSP!=1)//不分裂,改变有效Key或总Key
		{
            finished=true;
		}
         
		else
		{
			pApNode=new BTNODE(pNode->tag,M,KeyType,KeyLength);
            pApNode->rtag=0x1;
			pApNode->DB_THIS=CMemory::AllocatePDB(this->CurrentFile,pApNode,INDEX_FILE);
			//还要分配pApNode->DB_THIS!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            s=  (M%2==0) ? (M/2) :  (M/2+1);//向上取整
            x=Split(pNode,s,pApNode);
			trace=pNode;
			pNode=CMemory::ReadIDXBlock(pNode->parent,M,KeyType,KeyLength,pNode);;
			if(pNode)
			{
				if(Dup)
					pos=Position(trace,pNode);
				else
                    pos=Position(x,pNode);
			}
		}
	}
	if(!finished)//T是空疏,或已分裂为两个根结点trace和pApNode
		NewRoot(trace,x,pApNode,db_addr);

	++m_uiEffectKey;
	++m_uiKeyCount;
	m_dbFillDegree=double(m_uiEffectKey)/double(m_uiKeyCount);
	return 0;
}

//在pos之后插入新键(pos+1处)
BOOL CBplusTree::InsertKey(BTNODE *pNode,KEY x,PDB db_addr,int pos,BTNODE *pApNode)//用了N
{
	int i;
	unsigned int keynum=pNode->keynum;
    
	pNode->wtag=0x1;
	if(pNode->pointer.address1.recptr[pos+1]==DB_NULL)//不用腾出位置,keynum不变!!!!
	{
		pNode->key[pos+1]=x;
		if(pNode->tag==TERMINAL)
		    pNode->pointer.address1.recptr[pos+1]=db_addr;
		return -1;//有效Key增加,总Key不增加
	}

	//腾出位置
	for(i=keynum-1;i>=pos+1;--i)
	{
		pNode->key[i+1]=pNode->key[i];
		if(pNode->tag==TERMINAL)
            pNode->pointer.address1.recptr[i+1]=pNode->pointer.address1.recptr[i];
		else if(pNode->tag==NO_TERMINAL)
			pNode->pointer.ptr[i+2]=pNode->pointer.ptr[i+1];
	}
	
	//插入pos+1处
	pNode->key[pos+1]=x;
	if(pNode->tag==TERMINAL)
		pNode->pointer.address1.recptr[pos+1]=db_addr;
	else if(pNode->tag==NO_TERMINAL)//??????
	{
		pApNode->parent=pNode->DB_THIS;
		pNode->pointer.ptr[pos+2]=pApNode->DB_THIS;
    }
	//勿忘
	++pNode->keynum;
	if(pNode->keynum<=M)
		return 0;//有效Key和总Key都增加
	else
		return 1;//溢出
}
CResult CBplusTree::SearchBTree(KEY key)
{
	BTNODE *pNode=m_root;

	if(!m_root)
		return CResult(false,NULL);

	if(key.type==MIN_VALUE)
		return CResult(false,SQT,0,0);
	if(Dup)//允许重复
	{
		int i;
		bool found=false;
		int recptr=-1;//指向记录的数据库指针
		
		while(!(pNode->tag))//不是终端结点
		{
			for(i=0;i<int(pNode->keynum)&&key>pNode->key[i];++i);
		
			if(i>=int(pNode->keynum)||key<pNode->key[i])
				--i;
            else if(key==pNode->key[i])
				if(pNode->key[i].plus==1)//是烂键
                    --i;
			pNode=CMemory::ReadIDXBlock(pNode->pointer.ptr[i+1],M,KeyType,KeyLength,pNode);
		}
		//查叶结点，insert在res.pos处，delete,searchAll从res.recptr处开始
		for(i=0;i<int(pNode->keynum)&&key>=pNode->key[i];i++)
		{
			if(pNode->key[i]==key&&pNode->pointer.address1.recptr[i]!=DB_NULL&&!found)
			{
				found=true;
				recptr=i;//此时因为允许Dup,recptr是记录在结点的pos
			}
			if(pNode->key[i]==key&&pNode->pointer.address1.recptr[i]==DB_NULL)
			{
				recptr=(recptr==-1) ? i:recptr;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!9.30改
				break;
			}
		}
		if(i>0&&pNode->pointer.address1.recptr[i-1]==DB_NULL)//if将返回的pos的recptr是-1
			return CResult(found,pNode->DB_THIS,recptr,i-2);
		else
			return CResult(found,pNode->DB_THIS,recptr,i-1);
	}
	
	else
	{
		int low,high,mid;
		while(!(pNode->tag))//不是终端结点
		{
			low=0;
			high=pNode->keynum-1;
			
			while(low<=high)
			{
				mid=(low+high)/2;
				if(key==pNode->key[mid])
				{
					pNode=CMemory::ReadIDXBlock(pNode->pointer.ptr[mid+1],M,KeyType,KeyLength,pNode);
					//->pointer.ptr[mid+1];//等于key,找大于等于key的指针
					break;
				}
				else if(key<pNode->key[mid])
					high=mid-1;
				else
					low=mid+1;
			}
			if(low>high)//没找到
				pNode=CMemory::ReadIDXBlock(pNode->pointer.ptr[high+1],M,KeyType,KeyLength,pNode);
			//->pointer.ptr[high+1];
		}
		low=0;
		high=pNode->keynum-1;
		while(low<=high)
		{
			mid=(low+high)/2;
			if(key==pNode->key[mid])
			{
				if(pNode->pointer.address1.recptr[mid]==DB_NULL)
					return CResult(false,pNode->DB_THIS,-1,mid-1);
				else
					return CResult(true, pNode->DB_THIS,pNode->pointer.address1.recptr[mid],mid);
			}
			else if(key<pNode->key[mid])
				high=mid-1;
			else
				low=mid+1;
		}
		if(high>=0)
		{
			if(pNode->pointer.address1.recptr[high]==DB_NULL)
				return CResult(false,pNode->DB_THIS,-1,high-1);
		}
		return CResult(false,pNode->DB_THIS,-1,high);//????????
	}
}

//非叶结点:保留s个键(0...s-1号键保留,s+1...(keynum-1)号移动,s号键用于分割)
//叶结点:0...s-1号保留,s...(keynum-1)号键移动
//返回用于分割的关键字s
KEY CBplusTree::Split(BTNODE *pNode, unsigned int s, BTNODE *pApNode)//改变right和keynum
{
    unsigned int i;
	unsigned int j;
	unsigned int keynum=pNode->keynum;
	BTNODE *child=NULL;