📄 cmxbtree.cpp
字号:
#ifndef _CMXBTREE_CPP_20010925
#define _CMXBTREE_CPP_20010925
//以下内容是 CMXBTree 的实现
//所有代码由 邬稳 编写于 2001.9
//版权所有：深圳科迈通讯技术有限公司 2001.9
#include "cmxbtree.h"
//排序
//参数 A 已经是排好序的队列
//Key 指向要插入的元素
//0 1 2 3 4
//|-----|--30--|--75--|--85--|
// ^ nLo nHi
// |
// 可用空间
//假设 Key == 15
template <class RECTYPE>
void CMXBTree<RECTYPE>::QuickSortData(DATA_CONTAINER **A, int nLo, int nHi, DATA_CONTAINER *Key)
{
int i;
int iHi = nHi;
int iLo = nLo;
bool bLoop = true;
if( iHi == 0) //如果队列 A 中一个元素都没有
{
A[0] = Key;
return;
}
if( iHi - iLo == 1) //如果队列 A 中只有一个元素
{
bLoop = false; //不用进入下面的 while 循环
if( *(Key->pData) < *(A[iLo]->pData) )
i = iLo;
else i = iHi;
}
while( bLoop ) //队列 A 有两个或以上的元素时、才能进入 while 循环
{
//以下用二分法寻找可以插入的位置
//这个位置就放在 i 中
i = (iLo+iHi)/2;
if( (i == iLo) && ( i== iHi ) ) break;
if( *(Key->pData) < *(A[i-1]->pData) )
{
iHi = i - 1;
continue;
}
else
if( *(Key->pData) < *(A[i]->pData) )
{
break;
}
else iLo = i + 1;
}
int l;
if( i == nLo && i > 0) //在最左边插入，而且左边有空
{
A[i-1] = Key;
return ;
}
if( i == nHi && i < BTREE_DEGREE ) //在最右边插入，而且右边有空
{
A[i] = Key;
return;
}
//需要在中间的某个地方插入
if( nLo > 0 ) //左边有空，往左边推
{
for( l = 0; l < i-1 ; l ++)
A[l] = A[l+1];
A[i-1] = Key;
}
else //右边有空，往左边推
{
for( l = nHi-1; l >=i ; l --)
A[l+1] = A[l];
A[i] = Key;
}
}
//申请一个新的索引叶
//如果不够内存，返回 NULL
template <class RECTYPE>
CMXBTree<RECTYPE>::BTREE_INDEX_LEAF *CMXBTree<RECTYPE>::NewIndexLeaf( void )
{
BTREE_INDEX_LEAF *pTmp = new BTREE_INDEX_LEAF;
if ( !pTmp ) return NULL;
m_nNewIndexLeaf ++;
memset( pTmp, 0, sizeof( BTREE_INDEX_LEAF ) );
return pTmp;
}
template <class RECTYPE>
void CMXBTree<RECTYPE>::DeleteIndexLeaf( BTREE_INDEX_LEAF * pPtr )
{
m_nDelIndexLeaf ++;
if( pPtr ) delete pPtr;
}
//申请一个新的数据叶
//如果不够内存，返回 NULL
template <class RECTYPE>
CMXBTree<RECTYPE>::BTREE_DATA_LEAF *CMXBTree<RECTYPE>::NewDataLeaf( void )
{
BTREE_DATA_LEAF *pTmp = new BTREE_DATA_LEAF;
if ( !pTmp ) return NULL;
m_nNewDataLeaf ++;
memset( pTmp, 0, sizeof( BTREE_DATA_LEAF ) );
return pTmp;
}
template <class RECTYPE>
void CMXBTree<RECTYPE>::DeleteDataLeaf( BTREE_DATA_LEAF * pPtr )
{
m_nDelDataLeaf ++;
if( pPtr ) delete pPtr;
}
//申请一个新的 DataContainer
//如果不够内存，返回 NULL
template <class RECTYPE>
CMXBTree<RECTYPE>::DATA_CONTAINER *CMXBTree<RECTYPE>::NewDataContainer( void )
{
DATA_CONTAINER *pTmp = new DATA_CONTAINER;
if ( !pTmp ) return NULL;
m_nNewDataCon ++;
memset( pTmp, 0, sizeof( DATA_CONTAINER ) );
return pTmp;
}
template <class RECTYPE>
void CMXBTree<RECTYPE>::DeleteDataContainer( DATA_CONTAINER *pPtr )
{
m_nDelDataCon ++;
if( pPtr ) delete pPtr;
}
//申请一个新的 RECTYPE
//如果不够内存，返回 NULL
template <class RECTYPE>
RECTYPE *CMXBTree<RECTYPE>::NewRecType( void )
{
RECTYPE *pTmp = new RECTYPE;
if ( !pTmp ) return NULL;
m_nNewRecType ++;
//memset( pTmp, 0, sizeof( RECTYPE ) );
return pTmp;
}
template <class RECTYPE>
void CMXBTree<RECTYPE>::DeleteRecType( RECTYPE *pPtr )
{
m_nDelRecType ++;
if( pPtr ) delete pPtr;
}
//数据叶是否还有空位
//如果有空位则返回空位的位置 0 ~ BTREE_DEGREE - 1
//否则 返回 -1
template <class RECTYPE>
int CMXBTree<RECTYPE>::GetFreeElemInDataLeaf( BTREE_DATA_LEAF *pDataLeaf )
{
for ( int i = 0 ; i < BTREE_DEGREE ; i++ )
{
if ( ! pDataLeaf->pDataCont[i] ) return i;
}
return -1;
}
//数据叶存放了多少元素
//返回值 0 ~ BTREE_DEGREE
template <class RECTYPE>
int CMXBTree<RECTYPE>::GetTotalElemInDataLeaf( BTREE_DATA_LEAF *pDataLeaf )
{
for ( int i = 0 ; i < BTREE_DEGREE ; i++ )
{
if ( ! pDataLeaf->pDataCont[i] ) return i;
}
return BTREE_DEGREE;
}
//索引叶是否还有空位
//如果有空位则返回空位的位置 0 ~ BTREE_DEGREE - 1
//否则 返回 -1
template <class RECTYPE>
int CMXBTree<RECTYPE>::GetFreeElemInIndexLeaf( BTREE_INDEX_LEAF *pIndexLeaf )
{
for ( int i = 0 ; i < BTREE_DEGREE ; i++ )
{
if ( ! (pIndexLeaf->IndexKeys[i].pKey) ) return i;
}
return -1;
}
//索引叶存放了多少元素
//返回值 0 ~ BTREE_DEGREE
template <class RECTYPE>
int CMXBTree<RECTYPE>::GetTotalElemInIndexLeaf( BTREE_INDEX_LEAF *pIndexLeaf )
{
for ( int i = 0 ; i < BTREE_DEGREE ; i++ )
{
if ( ! (pIndexLeaf->IndexKeys[i].pKey) ) return i;
}
return BTREE_DEGREE;
}
//在索引叶中寻找可以插入Key的缝隙
//返回 0 ~ DEGREE 表示缝隙的位置
//返回 -1 表示B+Tree Error
template <class RECTYPE>
int CMXBTree<RECTYPE>::SeekInsertPoint( BTREE_INDEX_LEAF * pSearchIndexLeaf, RECTYPE & Key, bool *pKeyInIndex)
{
if( pSearchIndexLeaf == NULL ) return -1;
int i;
int nLo = 0 , nHi = BTREE_DEGREE;
while( true )
{
i = (nLo + nHi )/2;
if( i == nLo && i == nHi ) return i; //发现了
if( i == 0) //到了最左边
{
if( ! pSearchIndexLeaf->IndexKeys[0].pKey ) return -1;
if( Key < *(pSearchIndexLeaf->IndexKeys[0].pKey) )
return i;
else
{
nLo = i + 1;
continue;
}
}
//如果左边的元素空或者小于 Key
if( !pSearchIndexLeaf->IndexKeys[i-1].pKey || Key < *(pSearchIndexLeaf->IndexKeys[i-1].pKey) )
{
nHi = i - 1;
continue;
}
else
if( pSearchIndexLeaf->IndexKeys[i].pKey ) //右边有元素
{
if( *(pSearchIndexLeaf->IndexKeys[i].pKey) < Key ) //比右边的元素大一点
{
nLo = i +1;
continue;
}
else
if( Key < *(pSearchIndexLeaf->IndexKeys[i].pKey) ) //比右边的元素小一点
return i;
else
{
if( pKeyInIndex )
*pKeyInIndex = true;
return i + 1;
}
}
else //右边没有元素存在
return i;
}
//return -1;
}
//取得可以存放 Key 的数据叶
//返回数据叶的索引叶的缝隙
//返回 -1 表示B+Tree 出错
template <class RECTYPE>
int CMXBTree<RECTYPE>::GetDataLeaf( RECTYPE &Key, BTREE_INDEX_LEAF * &pSearchIndexLeaf, BTREE_DATA_LEAF * &pSearchDataLeaf, bool *pKeyInIndex )
{
int i;
//int nLo = 0 , nHi = BTREE_DEGREE;
while( true ) //一直循环
{
if( !pSearchIndexLeaf )
return -1;
if( pKeyInIndex && *pKeyInIndex )
i = 0;
else
i = SeekInsertPoint( pSearchIndexLeaf, Key, pKeyInIndex); //查询插入位置
if( i < 0 )
return -1;
void *pTmp;
if( i == 0 )
pTmp = pSearchIndexLeaf->pLeafLeft;
else pTmp = pSearchIndexLeaf->IndexKeys[i-1].pKeyRight;
if( pSearchIndexLeaf->cPointerType == DATA_LEAF_POINTER) //如果下面就是数据叶
{
pSearchDataLeaf = (BTREE_DATA_LEAF*)pTmp;
return i;
}
else
if( pSearchIndexLeaf->cPointerType == INDEX_LEAF_POINTER) //如果下面是索引叶
{
if( !pTmp )
return -1;
BTREE_INDEX_LEAF* pTmp2 = pSearchIndexLeaf;
pSearchIndexLeaf = (BTREE_INDEX_LEAF*)pTmp; //继续找下一个
pSearchIndexLeaf->pParent = pTmp2;
continue;
}
}
}
//查找索引叶在父节点的位置
template <class RECTYPE>
int CMXBTree<RECTYPE>::SeekParent( BTREE_INDEX_LEAF * pParentLeaf, BTREE_INDEX_LEAF * pIndexLeaf)
{
if ( pIndexLeaf == pParentLeaf->pLeafLeft ) return 0;
else
{
int l;
for( l = 0; l < BTREE_DEGREE; l ++ )
{
if( pIndexLeaf == pParentLeaf->IndexKeys[l].pKeyRight )
return l + 1;
}
//寻找不到，BTREE 错误
if ( l == BTREE_DEGREE )
return -1;
}
return -1;
}
//分裂索引叶
//这个函数被 InsertKey 调用，
//调用背景是在数据叶的索引叶满了之后，
//需要对索引叶进行分裂
template <class RECTYPE>
int CMXBTree<RECTYPE>::SplitIndexLeaf(BTREE_INDEX_LEAF * pCurIndexLeaf, //要容纳新 Key 的索引叶
INDEX_KEY NewKey, //新的 Key
int i ) //插入位置 0 ~ BTREE_DEGREE
{
INDEX_KEY TmpIndexKeys[BTREE_DEGREE + 1]; //能容纳所有 Key 的临时变量
int j;
int l;
SplitAgain:
memcpy(TmpIndexKeys, pCurIndexLeaf->IndexKeys, BTREE_DEGREE * sizeof( INDEX_KEY ));
for( l = BTREE_DEGREE; l > i; l-- )
{
TmpIndexKeys[l] = TmpIndexKeys[l-1];
}
TmpIndexKeys[i] = NewKey;
//如果自己就是根
if ( !pCurIndexLeaf->pParent )
{
//新增两个索引叶
BTREE_INDEX_LEAF *pIndexLeaf1 = NewIndexLeaf();
if( !pIndexLeaf1 ) return -2;
BTREE_INDEX_LEAF *pIndexLeaf2 = NewIndexLeaf();
if( !pIndexLeaf2 ) return -2;
int nCutPosition = (BTREE_DEGREE + 1)/2;
//给这两个索引叶赋值
for(l = 0 ; l < nCutPosition; l ++)
{
pIndexLeaf1->IndexKeys[l] = TmpIndexKeys[l] ;
}
pIndexLeaf1->pLeafLeft = pCurIndexLeaf->pLeafLeft;
pIndexLeaf1->cPointerType = pCurIndexLeaf->cPointerType;
pIndexLeaf1->pParent = pCurIndexLeaf;
for(l = nCutPosition + 1,j = 0 ; l < BTREE_DEGREE+1; l ++, j++)
{
pIndexLeaf2->IndexKeys[j] = TmpIndexKeys[l] ;
}
pIndexLeaf2->pLeafLeft = TmpIndexKeys[nCutPosition].pKeyRight;
pIndexLeaf2->cPointerType = pCurIndexLeaf->cPointerType;
pIndexLeaf2->pParent = pCurIndexLeaf;
//清空根的索引叶
memset(pCurIndexLeaf->IndexKeys, 0, BTREE_DEGREE * sizeof( INDEX_KEY ));
pCurIndexLeaf->IndexKeys[0].pKey = TmpIndexKeys[nCutPosition].pKey;
pCurIndexLeaf->IndexKeys[0].pKeyRight = pIndexLeaf2;
pCurIndexLeaf->pLeafLeft = pIndexLeaf1;
//最后才设置 POINTER TYPE
pCurIndexLeaf->cPointerType = INDEX_LEAF_POINTER;
return 0;
}
else
//父节点存在
{
int nIndexLoc;
//寻找 pCurIndexLeaf 在父节点的位置
BTREE_INDEX_LEAF *pParentIndex = pCurIndexLeaf->pParent;
nIndexLoc = SeekParent( pParentIndex, pCurIndexLeaf);
if( nIndexLoc < 0 )
return -1;
if ( nIndexLoc < BTREE_DEGREE ) //往右看有没有兄弟有空
{
BTREE_INDEX_LEAF *pIndexLeaf;
//右边有没有兄弟存在
if ( pParentIndex->IndexKeys[nIndexLoc].pKey )
{
//将右边的兄弟取下来
pIndexLeaf = (BTREE_INDEX_LEAF *)pParentIndex->IndexKeys[nIndexLoc].pKeyRight;
if ( ! pIndexLeaf )
return -1;
int nIndexLeafLoc = GetFreeElemInIndexLeaf( pIndexLeaf );
//右边的兄弟有空
if ( nIndexLeafLoc > -1 )
{
//挤出空间出来
for ( j = nIndexLeafLoc; j > 0; j--)
{
pIndexLeaf->IndexKeys[j] = pIndexLeaf->IndexKeys[j-1];
}
pIndexLeaf->IndexKeys[0].pKey = pParentIndex->IndexKeys[nIndexLoc].pKey;
pIndexLeaf->IndexKeys[0].pKeyRight = pIndexLeaf->pLeafLeft;
pIndexLeaf->pLeafLeft = TmpIndexKeys[BTREE_DEGREE].pKeyRight;
pParentIndex->IndexKeys[nIndexLoc].pKey = TmpIndexKeys[BTREE_DEGREE].pKey ;
pParentIndex->IndexKeys[nIndexLoc].pKeyRight = pIndexLeaf;
memcpy(pCurIndexLeaf->IndexKeys, TmpIndexKeys, BTREE_DEGREE * sizeof( INDEX_KEY ));
return 0;
}
}
}
if ( nIndexLoc > 0 ) //看看左边的索引叶
{
BTREE_INDEX_LEAF *pParentIndex = pCurIndexLeaf->pParent;
BTREE_INDEX_LEAF *pIndexLeaf;
if ( nIndexLoc == 1)
{
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -