bplustree.cpp

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

	BTNODE *rbrth=NULL;
    KEY ret=pNode->key[s];
	
	pNode->wtag=0x1;
	pApNode->wtag=0x1;
    if(pNode->tag==TERMINAL&&pNode->key[s-1]==ret)
	    ret.plus=1;	
	if(pNode->tag==TERMINAL)
	{
		for(i=s,j=0;i<keynum;i++,j++)
		{
			pApNode->key[j]=pNode->key[i];
			pApNode->pointer.address1.recptr[j]=pNode->pointer.address1.recptr[i];
		}
		pNode->keynum=s;
        pApNode->keynum=keynum-s;

		//pNode->pointer.address1.right;
		rbrth=CMemory::ReadIDXBlock(pNode->pointer.address1.right,M,KeyType,KeyLength,pNode);
		if(rbrth)
		{
			rbrth->wtag=0x1;
			pApNode->pointer.address1.right=rbrth->DB_THIS;//rbrth
		}
		else
			pApNode->pointer.address1.right=DB_NULL;
	
		pApNode->pointer.address1.left=pNode->DB_THIS;//pNode;
		if(rbrth)
            rbrth->pointer.address1.left=pApNode->DB_THIS;//pApNode;
        pNode->pointer.address1.right=pApNode->DB_THIS;//pApNode;
	}
    else if(pNode->tag==NO_TERMINAL)
	{
		for(i=s+1,j=0;i<keynum+1;i++,j++)
		{
			pApNode->pointer.ptr[j]=pNode->pointer.ptr[i];
			//改变parent,代价大
			child=CMemory::ReadIDXBlock(pApNode->pointer.ptr[j],M,KeyType,KeyLength,pApNode);
			//pApNode->pointer.ptr[j];
			child->parent=pApNode->DB_THIS;
		}
        for(i=s+1,j=0;i<keynum;i++,j++)//用了N
		    pApNode->key[j]=pNode->key[i];
		
		pNode->keynum=s;
		pApNode->keynum=keynum-1-s;
	}
	return ret;
}
//若返回pos,则应该插的地方是pos+1,用于Dup
int CBplusTree::Position(BTNODE *pNode, BTNODE *parent)
{
    ASSERT(Dup&&parent);
    int i;
	for(i=0;i<int(parent->keynum+1);++i)//遍历所有指针(数量是keynum+1)
	{
	    if(parent->pointer.ptr[i]==pNode->DB_THIS)
			break;
	}
	ASSERT(i<int(parent->keynum+1));
	return (i-1);
}
//若返回pos,则应该插的地方是pos+1,用于非Dup
int CBplusTree::Position(KEY key, BTNODE *pNode)
{
	ASSERT(Dup==0);
	
	int low,high,mid;
	low=0;
	high=pNode->keynum-1;
	while(low<=high)
	{
		mid=(low+high)/2;
		if(key==pNode->key[mid])
			return mid;
		else if(key<pNode->key[mid])
			high=mid-1;
		else
			low=mid+1;
	}
	return high;
}
//key_db_addr只在没有根结点时使用
void CBplusTree::NewRoot(BTNODE *pNode, KEY key, BTNODE *pApNode,PDB key_db_addr)
{
	BTNODE *newRoot;
	
	if(!m_root)
	{
	    newRoot=new BTNODE(TERMINAL,M,KeyType,KeyLength);
		newRoot->rtag=0x2;//不能被替换
		//newRoot->wtag=0x1;
		newRoot->DB_THIS=CMemory::AllocatePDB(this->CurrentFile,newRoot,INDEX_FILE);
		
        newRoot->keynum=1;     
		newRoot->key[0]=key;
		newRoot->pointer.address1.recptr[0]=key_db_addr;//暂时
		m_root=newRoot;
		m_sqt=newRoot;
		ROOT=newRoot->DB_THIS;
		SQT=newRoot->DB_THIS;
		return;
	}
    else
	{
        newRoot=new BTNODE(NO_TERMINAL,M,KeyType,KeyLength);
		newRoot->rtag=0x2;//不能被替换
		//newRoot->wtag=0x1;
		newRoot->DB_THIS=CMemory::AllocatePDB(this->CurrentFile,newRoot,INDEX_FILE);
		//还要分配DB_THIS!!!!!!!!!!!!!!!!!!
		
		newRoot->keynum=1;
		newRoot->key[0]=key;//???????
		newRoot->pointer.ptr[0]=pNode->DB_THIS;
		newRoot->pointer.ptr[1]=pApNode->DB_THIS;
		pNode->rtag=0x1;//不再是根结点,可以被替换了
		pNode->wtag=pApNode->wtag=0x1;
		pNode->parent=pApNode->parent=newRoot->DB_THIS;
		m_root=newRoot;
		ROOT=newRoot->DB_THIS;
		return;
	}
}
unsigned short CBplusTree::GetM()
{
	return M;
}
/*CBplusTree & CBplusTree::operator =(CBplusTree &T)
{
	if(m_root)
	    delete m_root;
    m_root=T.GetRoot();
	m_sqt=T.GetSqt();
	m_uiKeyCount=T.m_uiKeyCount;
	m_uiEffectKey=T.m_uiEffectKey;
	m_dbFillDegree=T.m_dbFillDegree;
	M=T.GetM();
	Dup=T.Dup;
	return *this;
}*/
//B树主文件                       
                                
//UINT	ID
//BYTE  DUP
//BYTE	KeyType
//BYTE	KeyNum
//WORD  KeyLength
//WORD 	M 
//PDB	ROOT
//PDB	SQT 
//unsigned int m_uiKeyCount;
//unsigned int m_uiEffectKey;
//UINT  currentFile//当前文件号

BOOL CBplusTree::Construct(UINT FileNo)
{
	CString s;
	s.Format("D:\\DB\\%d.mdx",FileNo);
	CFile f(LPCTSTR(s),CFile::modeReadWrite);
    
	f.SeekToBegin();
    f.Read(&MainID,sizeof(UINT));//==FileNo
	f.Read(&Dup,sizeof(BOOL));
	f.Read(&KeyType,sizeof(BYTE));
	f.Read(&KeyNum,sizeof(BYTE));
	f.Read(&KeyLength,sizeof(WORD));
	f.Read(&M,sizeof(WORD));
	f.Read(&ROOT,sizeof(PDB));
	if(ROOT==DB_NULL)
		m_root=NULL;
	else
	{
		m_root=CMemory::ReadIDXBlock(ROOT,M,KeyType,KeyLength);
		m_root->rtag=2;//不能被替换
	}
	f.Read(&SQT,sizeof(PDB));
	if(SQT==DB_NULL)
		m_sqt=NULL;
	else
	{
		m_sqt=CMemory::ReadIDXBlock(SQT,M,KeyType,KeyLength);
	    m_sqt->rtag=2;
	}
	f.Read(&m_uiKeyCount,sizeof(UINT));
	f.Read(&m_uiEffectKey,sizeof(UINT));
	m_dbFillDegree=0.0;
	f.Read(&CurrentFile,sizeof(UINT));
	return TRUE;
}

BOOL CBplusTree::WriteBack(CMultiIdx *multi_idx,WORD multi_num)
{
	CString filename;
    filename.Format("D:\\DB\\%d.mdx",this->MainID);//主文件
	CFile f(filename,CFile::modeReadWrite);
	f.SeekToBegin();

	f.Write(&MainID,sizeof(UINT));//4
	f.Write(&Dup,sizeof(BOOL));//4
	f.Write(&KeyType,sizeof(BYTE));//1
	f.Write(&KeyNum,sizeof(BYTE));//1
	f.Write(&KeyLength,sizeof(WORD));//2
	f.Write(&M,sizeof(WORD));//2
	f.Write(&ROOT,sizeof(PDB));//8
	f.Write(&SQT,sizeof(PDB));//8
	f.Write(&m_uiKeyCount,sizeof(UINT));//4
	f.Write(&m_uiEffectKey,sizeof(UINT));//4
	f.Write(&CurrentFile,sizeof(UINT));//4
    //以上有42字节

	/*//8.21发现的bug,9.31根结点和XX已经不可能已经被CMemory写回(0x2)
	if(m_root)
	    this->m_root->WriteDisk();
	if(m_sqt)
	    this->m_sqt->WriteDisk();*/
    if(multi_num!=0)
	{
		WORD i;
		ASSERT(multi_idx);
		for(i=0;i<multi_num;i++)
		{
			f.Write(&multi_idx[i].Dup,sizeof(BYTE));
			f.Write(&multi_idx[i].AttrNo[0],sizeof(WORD));
			f.Write(&multi_idx[i].AttrNo[1],sizeof(WORD));
		}
	}
	
	return TRUE;
}

CBuffer * CBplusTree::SearchAll(KEY key, CResult *res, BOOL Dup)
{
	if(!res)
		return NULL;
	PDB pdbNode=res->pdbNode;
	int pos=0;
	if(Dup)
		pos=res->recptr;
	else
		pos=res->pos;
	BTNODE *pNode=CMemory::ReadIDXBlock(pdbNode,M,KeyType,KeyLength);
    CBuffer *buffer=new CBuffer(200,100);
	
	int i=pos;
	if(i==-1)
		i=0;
	bool end=false;
	
	while(!end&&pNode)
	{
		for(;i<int(pNode->keynum)&&pNode->key[i]==key;++i)
		{
			if(pNode->pointer.address1.recptr[i]!=DB_NULL)
			{
				buffer->Append(pNode->pointer.address1.recptr[i]);
			}
		}
		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;
		}
	}
	
	return buffer;
}

CBuffer * CBplusTree::SearchScope(KEY key1, KEY key2,PDB pdbNode,bool flag1,bool flag2
								  , int pos)
//若无上限，key2.type==MAX_VALUE
//若无下限，key1.type==MIN_VALUE
//key与MAX_VALUE,MIN_VALUE恒等
//flag表示等于
{
	BTNODE *pNode=CMemory::ReadIDXBlock(pdbNode,M,KeyType,KeyLength);
    CBuffer *buffer=new CBuffer(200,100);
	int i=pos;
	if(i==-1)
		i=0;
	bool end=false;
	
	
	while(!end&&pNode)
	{
		//从pos开始查找
		for(;i<int(pNode->keynum)&&!end;++i)
		{
			if(pNode->key[i]==key1)
			{
				if(flag1&& (pNode->pointer.address1.recptr[i]!=DB_NULL) )
				{
					buffer->Append(pNode->pointer.address1.recptr[i]);
				}
			}
			else if(pNode->key[i]==key2)
			{
				if(flag2 && (pNode->pointer.address1.recptr[i]!=DB_NULL) )
				{
					buffer->Append(pNode->pointer.address1.recptr[i]);
				}
				else if(!flag2)
				{
					end=true;
				}
			}
			else if(pNode->key[i]>key1&&pNode->key[i]<key2)
			{
				if(pNode->pointer.address1.recptr[i]!=DB_NULL)
				    buffer->Append(pNode->pointer.address1.recptr[i]);
			}
			else if(pNode->key[i]>key2)
			{
				end=true;
			}
		}
		if(!end)
		{
			pNode=CMemory::ReadIDXBlock(pNode->pointer.address1.right
				,M,KeyType,KeyLength,pNode);//pNode.ReadBrother(f,RIGHT,M);
			i=0;
		}
	}
    
	return buffer;   
}