?? 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 + -