cmxbtree.cpp

CMXBTree 的主要作用是在内存中建立一棵B+树

                pIndexLeaf = (BTREE_INDEX_LEAF *)pParentIndex->pLeafLeft;
                if ( !pIndexLeaf) 
                    return -1;
            }
            else pIndexLeaf = (BTREE_INDEX_LEAF *)pParentIndex->IndexKeys[nIndexLoc-2].pKeyRight;
            if ( ! pIndexLeaf ) 
                return -1;
            int nIndexLeafLoc = GetFreeElemInIndexLeaf( pIndexLeaf );
            //左边的兄弟有空
            if ( nIndexLeafLoc > -1 )
            {
                //占据左边兄弟的空位
                pIndexLeaf->IndexKeys[nIndexLeafLoc].pKey = pParentIndex->IndexKeys[nIndexLoc-1].pKey ;
                pIndexLeaf->IndexKeys[nIndexLeafLoc].pKeyRight = pCurIndexLeaf->pLeafLeft;
                
                //占据父节点腾出来的空位
                pParentIndex->IndexKeys[nIndexLoc-1].pKey = TmpIndexKeys[0].pKey;
                pParentIndex->IndexKeys[nIndexLoc-1].pKeyRight = pCurIndexLeaf;
                
                //把自己的值设置好
                pCurIndexLeaf->pLeafLeft = TmpIndexKeys[0].pKeyRight;
                memcpy( pCurIndexLeaf->IndexKeys, &TmpIndexKeys[1], BTREE_DEGREE * sizeof( INDEX_KEY ));


                return 0;


            }
        }

        //最后左右兄弟都没有空间了
        //看看父亲有没有
        int nCutPosition = (BTREE_DEGREE + 1)/2;
        int nIndexLeafLoc;

        if ( (nIndexLeafLoc = GetFreeElemInIndexLeaf( pCurIndexLeaf->pParent )) > -1 )
        {
            //父亲有空间
            //本索引叶需要拆分
            BTREE_INDEX_LEAF *pParentIndex = pCurIndexLeaf->pParent;
            BTREE_INDEX_LEAF *pIndexLeaf1 = NewIndexLeaf();
            if( !pIndexLeaf1 ) return -2;

            //先把在父节点中所需要的位置腾出来
            for ( l = nIndexLeafLoc; l > nIndexLoc ; l -- )
            {
                pParentIndex->IndexKeys[l] = pParentIndex->IndexKeys[l-1];
            }
            //占据父节点的空间
            pParentIndex->IndexKeys[nIndexLoc].pKey = TmpIndexKeys[nCutPosition].pKey;
            pParentIndex->IndexKeys[nIndexLoc].pKeyRight = pIndexLeaf1;
            
            //设置新的索引叶数据
            pIndexLeaf1->cPointerType = pCurIndexLeaf->cPointerType ;
            pIndexLeaf1->pLeafLeft = TmpIndexKeys[nCutPosition].pKeyRight;
            pIndexLeaf1->pParent = pParentIndex;

            //给这两个索引叶赋值
            for(l = nCutPosition + 1,j = 0 ; l < BTREE_DEGREE+1; l ++, j++)
            {
                pIndexLeaf1->IndexKeys[j] = TmpIndexKeys[l];
            }
            memset(pCurIndexLeaf->IndexKeys, 0, BTREE_DEGREE * sizeof( INDEX_KEY ));
            for(l = 0 ; l < nCutPosition; l ++)                
            {
                pCurIndexLeaf->IndexKeys[l] = TmpIndexKeys[l];
            }

            return 0;

        }
        
        //父节点也没有空位置了，只好交给爷爷节点
        //先拆分
        memset( pCurIndexLeaf->IndexKeys, 0, BTREE_DEGREE * sizeof( INDEX_KEY ) );
        memcpy( pCurIndexLeaf->IndexKeys, &TmpIndexKeys[0], nCutPosition* sizeof( INDEX_KEY ));
        BTREE_INDEX_LEAF *pIndexLeaf1 = NewIndexLeaf();
        if( !pIndexLeaf1 ) return -2;

        pIndexLeaf1->cPointerType = pCurIndexLeaf->cPointerType;
        pIndexLeaf1->pLeafLeft = TmpIndexKeys[nCutPosition].pKeyRight;
        memcpy( pIndexLeaf1->IndexKeys, &TmpIndexKeys[nCutPosition+1], (BTREE_DEGREE-nCutPosition)*sizeof( INDEX_KEY ));

        
        TmpIndexKeys[nCutPosition].pKeyRight = pIndexLeaf1;

        pCurIndexLeaf = pCurIndexLeaf->pParent;
        //pLeftLeaf = (void *)pCurIndexLeaf;
        //pRightLeaf = (void *)pIndexLeaf1;
        NewKey = TmpIndexKeys[nCutPosition];
        i = nIndexLoc;
        goto SplitAgain;
    }
//    return 0;
}


//如果能在数据叶中找到 Key, 则 nIndex 存放的就是Key在pDataLeaf中
//存放的位置，取值 0 ~ BTREE_DEGREE - 1
//如果找不到，nIndex 存放的就是可以让 Key 在 pDataLeaf 中插入的位置
//取值 0 ~ BTREE_DEGREE
//算法采用二分法
template <class RECTYPE> CMXBTree<RECTYPE>::DATA_CONTAINER * 
CMXBTree<RECTYPE>::SeekInDataLeaf( 
                                  BTREE_DATA_LEAF *pDataLeaf, 
                                  RECTYPE &Key, 
                                  int *nIndex
                                  )
{
    if ( pDataLeaf == NULL ) return NULL;

    int nLo = 0, nHi = BTREE_DEGREE - 1;
    int i;

    while( true )
    {
        //if( nLo > nHi ) return NULL;
        i = ( nLo + nHi ) / 2;        
        if(! pDataLeaf->pDataCont[i] || Key < *(pDataLeaf->pDataCont[i]->pData) )
        {
            nHi = i - 1;
            if( nLo > nHi )
            {
                if( nIndex ) *nIndex = nHi + 1;
                return NULL;
            }
            continue;
        }
        else 
        if( *(pDataLeaf->pDataCont[i]->pData) < Key ) 
        {
            nLo = i + 1;
            if( nLo > nHi )
            {
                if( nIndex ) *nIndex = nLo;
                return NULL;
            }
            continue;
        }
        else
        {
            if( nIndex ) *nIndex = i; 
            return  pDataLeaf->pDataCont[i] ;
        }
    }
//    return NULL;
}

//删除 DATA_CONTAINER 链表，包括 RECTYPE *
template <class RECTYPE>
int CMXBTree<RECTYPE>::DeleteDataContainerTrain( DATA_CONTAINER *pHead )
{
    DATA_CONTAINER *pTmp;
    while( pHead )
    {
        if( pHead->pData )
            DeleteRecType( pHead->pData );
        else return -1;
        pTmp = pHead->pNext;
        DeleteDataContainer( pHead );
        pHead = pTmp;
    }
    return 0;
}

//在索引叶内删除元素
//是 SplitIndexLeaf 的反操作
//被 DeleteKey 调用
//其中参数 q 就是要删除的第几个索引
template <class RECTYPE>
int CMXBTree<RECTYPE>::RemoveIndexKey( BTREE_INDEX_LEAF *pSearchIndexLeaf, int q )
{

RemoveAgain:
    
    int nIndexLeafLoc2;
    int j,l;
    int nIndexLeafLoc1 = GetTotalElemInIndexLeaf( pSearchIndexLeaf );

    if( !pSearchIndexLeaf->pParent ) //自己就是根
    {
        if( nIndexLeafLoc1 == 1 ) //只有最后一个元素
        {
            m_pRoot = (BTREE_INDEX_LEAF *)pSearchIndexLeaf->pLeafLeft;
            m_pRoot->pParent = NULL;
            DeleteIndexLeaf( pSearchIndexLeaf );
        }
        else
        {
            for( l = q; l < nIndexLeafLoc1 - 1; l++ )
            {
                pSearchIndexLeaf->IndexKeys[l] = pSearchIndexLeaf->IndexKeys[l+1];
            }
            pSearchIndexLeaf->IndexKeys[nIndexLeafLoc1 - 1].pKey = NULL;
            pSearchIndexLeaf->IndexKeys[nIndexLeafLoc1 - 1].pKeyRight = NULL;
        }
        return 0;
    }

    for( j = q; j < nIndexLeafLoc1-1; j++ )
    {
        pSearchIndexLeaf->IndexKeys[j] = pSearchIndexLeaf->IndexKeys[j+1];
    }
    pSearchIndexLeaf->IndexKeys[nIndexLeafLoc1-1].pKey = NULL;
    pSearchIndexLeaf->IndexKeys[nIndexLeafLoc1-1].pKeyRight = NULL;

    //占用了多少个
    nIndexLeafLoc1 --;
    if( nIndexLeafLoc1 >= BTREE_DEGREE /2 ) return 0; //数据叶元素个数还够

    int i;
    //寻找 pSearchIndexLeaf 在父节点的位置
    BTREE_INDEX_LEAF *pParentIndex = pSearchIndexLeaf->pParent;
    i = SeekParent( pParentIndex, pSearchIndexLeaf);
    if( i < 0 ) 
        return -1;

    BTREE_INDEX_LEAF *pIndexLeaf;

    //看看能不能和兄弟联合
    if( i < BTREE_DEGREE ) //看看右边的兄弟
    {
        //到底有没有右边的兄弟？
        if( pParentIndex->IndexKeys[i].pKey )
        {
            pIndexLeaf = (BTREE_INDEX_LEAF *)pParentIndex->IndexKeys[i].pKeyRight;
            if( !pIndexLeaf ) return -1;
            nIndexLeafLoc2 = GetTotalElemInIndexLeaf( pIndexLeaf );
            if( nIndexLeafLoc1 + nIndexLeafLoc2 + 1 <= BTREE_DEGREE )
            {
                //可以联合
                pSearchIndexLeaf->IndexKeys[nIndexLeafLoc1].pKey = pParentIndex->IndexKeys[i].pKey;
                pSearchIndexLeaf->IndexKeys[nIndexLeafLoc1].pKeyRight = pIndexLeaf->pLeafLeft;
                
                memcpy( &pSearchIndexLeaf->IndexKeys[nIndexLeafLoc1+1],
                        pIndexLeaf->IndexKeys,  nIndexLeafLoc2*sizeof(INDEX_KEY));
                DeleteIndexLeaf( pIndexLeaf );

                pSearchIndexLeaf = pParentIndex;
                q = i;
                goto RemoveAgain;
            }   
        }
    }

    if( i > 0 ) //看看左边的兄弟
    {
        if ( i == 1)
            pIndexLeaf = (BTREE_INDEX_LEAF *)pParentIndex->pLeafLeft;
        else 
            pIndexLeaf = (BTREE_INDEX_LEAF *)pParentIndex->IndexKeys[i-2].pKeyRight;
        if ( ! pIndexLeaf ) return -1;
        nIndexLeafLoc2 = GetTotalElemInIndexLeaf( pIndexLeaf );
        if( nIndexLeafLoc1 + nIndexLeafLoc2 + 1 <= BTREE_DEGREE )
        {
            //可以联合
            pIndexLeaf->IndexKeys[nIndexLeafLoc2].pKey = pParentIndex->IndexKeys[i-1].pKey;
            pIndexLeaf->IndexKeys[nIndexLeafLoc2].pKeyRight = pSearchIndexLeaf->pLeafLeft;

            memcpy( &pIndexLeaf->IndexKeys[nIndexLeafLoc2+1],
                    pSearchIndexLeaf->IndexKeys,  nIndexLeafLoc1*sizeof(INDEX_KEY));
            
            BTREE_INDEX_LEAF *pTmp = pParentIndex;
            DeleteIndexLeaf( pSearchIndexLeaf );
            pSearchIndexLeaf = pTmp;
            q = i-1;
            goto RemoveAgain;
        }
    }

    //如果不能联合，就开始旋转
    if ( i > 0 ) //看看左边的数据叶
    {
        if ( i == 1)
            pIndexLeaf = (BTREE_INDEX_LEAF *)pParentIndex->pLeafLeft;
        else 
            pIndexLeaf = (BTREE_INDEX_LEAF *)pParentIndex->IndexKeys[i-2].pKeyRight;
        if ( ! pIndexLeaf ) return -1;
        int nIndexLeafLoc = GetTotalElemInIndexLeaf( pIndexLeaf );
        //左边的兄弟有没有多余的
        if ( nIndexLeafLoc > BTREE_DEGREE/2 )
        {
            for( j = 0; j < nIndexLeafLoc1; j++)
                pSearchIndexLeaf->IndexKeys[j+1] = pSearchIndexLeaf->IndexKeys[j];
            
            pSearchIndexLeaf->IndexKeys[0].pKey  = pParentIndex->IndexKeys[i-1].pKey;
            pSearchIndexLeaf->IndexKeys[0].pKeyRight = pSearchIndexLeaf->pLeafLeft;
            pSearchIndexLeaf->pLeafLeft = pIndexLeaf->IndexKeys[nIndexLeafLoc-1].pKeyRight;
            pParentIndex->IndexKeys[i-1].pKey = pIndexLeaf->IndexKeys[nIndexLeafLoc-1].pKey;
            
            pIndexLeaf->IndexKeys[nIndexLeafLoc-1].pKey = NULL;
            pIndexLeaf->IndexKeys[nIndexLeafLoc-1].pKeyRight = NULL;

            return 0;
        }
    }

    if ( i < BTREE_DEGREE ) //看看右边的数据叶
    {
        if ( pParentIndex->IndexKeys[i].pKey )
        {
            pIndexLeaf = (BTREE_INDEX_LEAF *)pParentIndex->IndexKeys[i].pKeyRight;
            if ( ! pIndexLeaf ) return -1;
            int nIndexLeafLoc = GetTotalElemInIndexLeaf( pIndexLeaf );
            //右边的兄弟有多余的元素
            if ( nIndexLeafLoc > BTREE_DEGREE/2 )
            {
                pSearchIndexLeaf->IndexKeys[nIndexLeafLoc1].pKey = pParentIndex->IndexKeys[i].pKey;
                pSearchIndexLeaf->IndexKeys[nIndexLeafLoc1].pKeyRight = pIndexLeaf->pLeafLeft;
                pIndexLeaf->pLeafLeft = pIndexLeaf->IndexKeys[0].pKeyRight;
                pParentIndex->IndexKeys[i].pKey = pIndexLeaf->IndexKeys[0].pKey;
                
                for ( j = 0; j < nIndexLeafLoc-1; j++)
                    pIndexLeaf->IndexKeys[j] = pIndexLeaf->IndexKeys[j+1];

                pIndexLeaf->IndexKeys[nIndexLeafLoc-1].pKey = NULL;
                pIndexLeaf->IndexKeys[nIndexLeafLoc-1].pKeyRight = NULL;

                return 0;
            }
        }
    }
    return -1;
}

//在B+Tree 中删除 Key
//InsertKey 的反操作
template <class RECTYPE>
int CMXBTree<RECTYPE>::DeleteKey( RECTYPE &Key )
{
    //搜索中当前的索引叶
    BTREE_INDEX_LEAF *pSearchIndexLeaf  = m_pRoot;
    //搜索中当前的数据叶
    BTREE_DATA_LEAF  *pSearchDataLeaf   = NULL;

    bool bKeyInIndex = false;

    int i = GetDataLeaf( Key, pSearchIndexLeaf, pSearchDataLeaf, &bKeyInIndex );
    if ( i < 0 ) return -1;
    if( !pSearchDataLeaf ) return 1; //找不到Key

    int q,j;

    //SeekInDataLeaf( pSearchDataLeaf, Key, &q );
    //if( q == BTREE_DEGREE ) return 1; //表示该 Key 不存在
    if( bKeyInIndex )
        q = 0;
    else
    {
        if( SeekInDataLeaf( pSearchDataLeaf, Key, &q ) == NULL ) 
            return 1;
    }
    
    int nIndexLeafLoc = GetTotalElemInIndexLeaf( pSearchIndexLeaf );

    //如果索引叶有父亲，而且元素个数少于一半，则B+TREE出错
    if( nIndexLeafLoc < BTREE_DEGREE/2 && pSearchIndexLeaf->pParent ) return -1;
    
    //占用了多少个元素
    int nDataLeafLoc1 = GetTotalElemInDataLeaf( pSearchDataLeaf );

    //把父节点更新
    if( q == 0 ) //数据叶的最左边的元素
    {
        if( i > 0 ) //不是索引叶的最左边
        {
            if( pSearchDataLeaf->pDataCont[1] )
                pSearchIndexLeaf->IndexKeys[i-1].pKey = pSearchDataLeaf->pDataCont[1]->pData ;
        }
        else
        {   //索引叶的最左边
            BTREE_INDEX_LEAF *pIndexLeaf = pSearchIndexLeaf->pParent;
            while( pIndexLeaf )
            {
                for( j = 0; j < BTREE_DEGREE; j++ )
                {
                    if( pIndexLeaf->IndexKeys[j].pKey == pSearchDataLeaf->pDataCont[0]->pData )
                    {
                         pIndexLeaf->IndexKeys[j].pKey = pSearchDataLeaf->pDataCont[1]->pData ;
                         break;
                    }
                }
                if( j == BTREE_DEGREE ) 
                    pIndexLeaf = pIndexLeaf->pParent;
                else break;
            }
        }
    }

    //先把数据元素删除
    if( DeleteDataContainerTrain( pSearchDataLeaf->pDataCont[q] ) < 0 ) return -1;
    //移动数据
    

    int nDataLeafLoc2;

    for( j = q; j < nDataLeafLoc1-1; j++ )
    {
        pSearchDataLeaf->pDataCont[j] = pSearchDataLeaf->pDataCont[j+1];
    }
    pSearchDataLeaf->pDataCont[nDataLeafLoc1-1] = NULL;
    
    nDataLeafLoc1 --;
    if( nDataLeafLoc1 >= BTREE_DEGREE /2 ) return 0; //数据叶元素个数还够

    m_bMadeList  = false; //如果已经 MakeList 了，就只好在 Make 一次

    //如果只剩下一个索引叶，而且索引叶只有一个元素，而且索引叶的 pLeafLeft 是空
    if( nIndexLeafLoc == 1 && ! pSearchIndexLeaf->pLeafLeft )
    {
        if( nDataLeafLoc1 == 0 ) 
        {
            //B+TREE 的最有一个元素都消失了
            DeleteDataLeaf( pSearchDataLeaf );
            DeleteIndexLeaf( pSearchIndexLeaf );
            m_pRoot = NULL;
        }
        return 0;
    }
    
    BTREE_DATA_LEAF *pDataLeaf;
    //看看能不能和兄弟联合
    if( i < BTREE_DEGREE ) //看看右边的兄弟
    {
        //到底有没有右边的兄弟？
        if( pSearchIndexLeaf->IndexKeys[i].pKey )
        {
            pDataLeaf = (BTREE_DATA_LEAF *)pSearchIndexLeaf->IndexKeys[i].pKeyRight;
            if( !pDataLeaf ) return -1;
            nDataLeafLoc2 = GetTotalElemInDataLeaf( pDataLeaf );
            if( nDataLeafLoc1 + nDataLeafLoc2 <= BTREE_DEGREE )
            {
                if( nIndexLeafLoc == 1) //父节点只有最后一个元素
                {
                    DATA_CONTAINER* pTmp[BTREE_DEGREE];
                    memcpy( pTmp, pDataLeaf->pDataCont, nDataLeafLoc2*sizeof(DATA_CONTAINER*));
                    memcpy( pDataLeaf->pDataCont,
                            pSearchDataLeaf->pDataCont,  nDataLeafLoc1*sizeof(DATA_CONTAINER*));
                    memcpy( &pDataLeaf->pDataCont[nDataLeafLoc1], pTmp, nDataLeafLoc2*sizeof(DATA_CONTAINER*));
                    pSearchIndexLeaf->pLeafLeft = NULL;
                    DeleteDataLeaf( pSearchDataLeaf );
                    pSearchIndexLeaf->IndexKeys[i].pKey = pDataLeaf->pDataCont[0]->pData;
                    return 0;
                }
                else
                {
                    //可以联合

                    memcpy( &pSearchDataLeaf->pDataCont[nDataLeafLoc1],
                            pDataLeaf->pDataCont,  nDataLeafLoc2*sizeof(DATA_CONTAINER*));
                    DeleteDataLeaf( pDataLeaf );
                    if( RemoveIndexKey( pSearchIndexLeaf, i ) < 0 ) return -1;
 
                    return 0;
                }
            }