cmxbtree.cpp

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

        }
    }

    if( i > 0 ) //看看左边的兄弟
    {
        if ( i == 1)
            pDataLeaf = (BTREE_DATA_LEAF *)pSearchIndexLeaf->pLeafLeft;
        else 
            pDataLeaf = (BTREE_DATA_LEAF *)pSearchIndexLeaf->IndexKeys[i-2].pKeyRight;
        if ( ! pDataLeaf ) return -1;
        nDataLeafLoc2 = GetTotalElemInDataLeaf( pDataLeaf );

        if( nDataLeafLoc1 + nDataLeafLoc2 <= BTREE_DEGREE )
        {
            if( nIndexLeafLoc == 1) //父节点只有最后一个元素
            {
                DATA_CONTAINER* pTmp[BTREE_DEGREE];
                memcpy( pTmp, pSearchDataLeaf->pDataCont, nDataLeafLoc1*sizeof(DATA_CONTAINER*));
                memcpy( pSearchDataLeaf->pDataCont,
                        pDataLeaf->pDataCont,  nDataLeafLoc2*sizeof(DATA_CONTAINER*));
                memcpy( &pSearchDataLeaf->pDataCont[nDataLeafLoc2],
                        pTmp,  nDataLeafLoc1*sizeof(DATA_CONTAINER*));
                
                pSearchIndexLeaf->IndexKeys[i-1].pKey = pSearchDataLeaf->pDataCont[0]->pData;

                pSearchIndexLeaf->pLeafLeft = NULL;
                DeleteDataLeaf( pDataLeaf );
                return 0;
            }
            else
            {
                //可以联合

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

                return 0;
            }
        }
    }

    //如果不能联合，就开始旋转

    if ( i > 0 ) //看看左边的数据叶
    {
        if ( i == 1)
            pDataLeaf = (BTREE_DATA_LEAF *)pSearchIndexLeaf->pLeafLeft;
        else 
            pDataLeaf = (BTREE_DATA_LEAF *)pSearchIndexLeaf->IndexKeys[i-2].pKeyRight;
        int nDataLeafLoc;
        if ( ! pDataLeaf )  return -1;

        nDataLeafLoc = GetTotalElemInDataLeaf( pDataLeaf );
        //左边的兄弟有没有多余的
        if ( nDataLeafLoc > BTREE_DEGREE/2 )
        {
            for( j = 0; j < nDataLeafLoc1; j++)
                pSearchDataLeaf->pDataCont[j+1] = pSearchDataLeaf->pDataCont[j];
            
            pSearchDataLeaf->pDataCont[0] = pDataLeaf->pDataCont[nDataLeafLoc-1];
            pDataLeaf->pDataCont[nDataLeafLoc-1] = NULL;
            pSearchIndexLeaf->IndexKeys[i-1].pKey =pSearchDataLeaf->pDataCont[0]->pData;
            return 0;
        }
    }

    if ( i < BTREE_DEGREE ) //看看右边的数据叶
    {
        if ( pSearchIndexLeaf->IndexKeys[i].pKey )
        {
            pDataLeaf = (BTREE_DATA_LEAF *)pSearchIndexLeaf->IndexKeys[i].pKeyRight;
            if ( ! pDataLeaf ) return -1;
            int nDataLeafLoc = GetTotalElemInDataLeaf( pDataLeaf );
            //右边的兄弟有空
            if ( nDataLeafLoc > BTREE_DEGREE/2 )
            {
                pSearchDataLeaf->pDataCont[nDataLeafLoc1] = pDataLeaf->pDataCont[0];
                
                int j;
                for ( j = 0; j < nDataLeafLoc-1; j++)
                    pDataLeaf->pDataCont[j] = pDataLeaf->pDataCont[j+1];

                pDataLeaf->pDataCont[nDataLeafLoc-1] = NULL;
                pSearchIndexLeaf->IndexKeys[i].pKey = pDataLeaf->pDataCont[0]->pData;

                return 0;
            }
        }
    }
    return -1;
}

//向B+Tree 中插入 Key
template <class RECTYPE>
int CMXBTree<RECTYPE>::InsertKey( RECTYPE & Key )
{
    //搜索中当前的索引叶
    BTREE_INDEX_LEAF *pSearchIndexLeaf  = m_pRoot;
    //搜索中当前的数据叶
    BTREE_DATA_LEAF  *pSearchDataLeaf   = NULL;
    
    
    if ( !pSearchIndexLeaf )  //B+Tree 的最原始状态，连根都没有
    {
        //生成根
        pSearchIndexLeaf    = NewIndexLeaf();
        if ( !pSearchIndexLeaf ) return -2;
        pSearchDataLeaf     = NewDataLeaf(); 
        if ( !pSearchDataLeaf ) return -2;
        
        pSearchIndexLeaf->IndexKeys[0].pKeyRight = pSearchDataLeaf;
        RECTYPE *pTmp = NewRecType();
        if( !pTmp ) return -2;

        DATA_CONTAINER *pDataCont = NewDataContainer();
        if( !pDataCont ) return -2;
        pDataCont->pData = pTmp;


        *pTmp = Key;
        pSearchIndexLeaf->cPointerType = DATA_LEAF_POINTER;
        pSearchIndexLeaf->IndexKeys[0].pKey = pTmp;
        pSearchDataLeaf->pDataCont[0] = pDataCont;

        m_pRoot = pSearchIndexLeaf;
        return 0;
    }
    //查找可以容纳 Key 的数据叶
    bool bKeyInIndex = false;
    int i = GetDataLeaf( Key, pSearchIndexLeaf, pSearchDataLeaf, &bKeyInIndex );

    if ( i < 0 ) 
        return -1; //B+Tree 错误
    if( !pSearchDataLeaf )
    {
        //来到这里的唯一可能性就是
        //索引叶的最左指针为 NULL
        //而且这棵树只有一个索引叶和一个数据叶
        pSearchDataLeaf = NewDataLeaf(); //就给它一个新的
        if( !pSearchDataLeaf ) return -2;

        pSearchIndexLeaf->pLeafLeft = pSearchDataLeaf;
    }

    //在数据叶中查找 Key 是否存在
    DATA_CONTAINER *pDataCont ;
    if( bKeyInIndex )
        pDataCont = pSearchDataLeaf->pDataCont[0];
    else
        pDataCont = SeekInDataLeaf( pSearchDataLeaf, Key, NULL);
    if( pDataCont )
    {
        //存在！
        //建立 Key 链表
        while ( pDataCont->pNext )
            pDataCont = (DATA_CONTAINER *)pDataCont->pNext;

        DATA_CONTAINER *pDataCont2 = NewDataContainer();
        if( !pDataCont2) return -2; //没有内存
        pDataCont->pNext = pDataCont2;
        pDataCont2->pProv = pDataCont;
        pDataCont2->pData = NewRecType();
        if( !pDataCont2->pData ) return -2;
        *(pDataCont2->pData) = Key;
        //return 0;
        return 1; //表示该Key已经存在
    }

//InsertAgain:
    //如果数据叶有空位置
    int nDataLeafLoc = GetFreeElemInDataLeaf( pSearchDataLeaf );

    if ( nDataLeafLoc > -1  )
    {
        //数据叶有空位置
        DATA_CONTAINER *pTmp = NewDataContainer();
        if( !pTmp ) return -2; 
        pTmp->pData = NewRecType();
        if( !pTmp->pData ) return -2;
        *(pTmp->pData) = Key;
        QuickSortData( pSearchDataLeaf->pDataCont, 0, nDataLeafLoc, pTmp );                
    }
    else
    {
        //如果数据叶已经满了，看看他的兄弟有没有空间
        if ( i > 0 ) //看看左边的数据叶
        {
            BTREE_DATA_LEAF *pDataLeaf;
            if ( i == 1)
            {
                pDataLeaf = (BTREE_DATA_LEAF *)pSearchIndexLeaf->pLeafLeft;
                if ( !pDataLeaf) 
                {
                    pDataLeaf = NewDataLeaf();
                    if( !pDataLeaf ) return -2;

                    pSearchIndexLeaf->pLeafLeft = pDataLeaf;
                }
            }
            else pDataLeaf = (BTREE_DATA_LEAF *)pSearchIndexLeaf->IndexKeys[i-2].pKeyRight;
            if ( ! pDataLeaf ) 
                return -1;
            int nDataLeafLoc = GetFreeElemInDataLeaf( pDataLeaf );
            //左边的兄弟有空
            if ( nDataLeafLoc >= 0 )
            {
                //开始把数据从右往左旋转
                pDataLeaf->pDataCont[nDataLeafLoc] = pSearchDataLeaf->pDataCont[0];

                DATA_CONTAINER *pTmp = NewDataContainer();
                if( !pTmp) return -2;
                pTmp->pData = NewRecType();
                if( !pTmp->pData ) return -2;

                *(pTmp->pData) = Key;

                QuickSortData( pSearchDataLeaf->pDataCont, 1, BTREE_DEGREE, pTmp);

                pSearchIndexLeaf->IndexKeys[i-1].pKey = pSearchDataLeaf->pDataCont[0]->pData;

                return 0;
            }
        }

        if ( i < BTREE_DEGREE ) //看看右边的数据叶
        {
            BTREE_DATA_LEAF *pDataLeaf;
            if ( pSearchIndexLeaf->IndexKeys[i].pKey )
            {
                pDataLeaf = (BTREE_DATA_LEAF *)pSearchIndexLeaf->IndexKeys[i].pKeyRight;
                if ( ! pDataLeaf ) 
                    return -1;
                int nDataLeafLoc = GetFreeElemInDataLeaf( pDataLeaf );
                //右边的兄弟有空
                if ( nDataLeafLoc > -1 )
                {
                    //开始把数据从左往右旋转
                    int j;
                    //pDataLeaf->pDataCont[nDataLeafLoc] = pSearchDataLeaf->pDataCont[0];

                    //先腾出空间
                    for ( j = nDataLeafLoc; j > 0; j--)
                        pDataLeaf->pDataCont[j] = pDataLeaf->pDataCont[j-1];

                    //到底应不应该把 Key 移动
                    //就得看看数据叶的最后一个元素的大小
                    if ( *(pSearchDataLeaf->pDataCont[BTREE_DEGREE-1]->pData) < Key )
                    {
                        pDataLeaf->pDataCont[0] = NewDataContainer();
                        if( !pDataLeaf->pDataCont[0]) return -2;

                        pDataLeaf->pDataCont[0]->pData = NewRecType();
                        if( !pDataLeaf->pDataCont[0]->pData ) return -2;

                        *(pDataLeaf->pDataCont[0]->pData) = Key;
                        pSearchIndexLeaf->IndexKeys[i].pKey = pDataLeaf->pDataCont[0]->pData;
                    }
                    else
                    {
                        pDataLeaf->pDataCont[0] = pSearchDataLeaf->pDataCont[BTREE_DEGREE-1];

                        DATA_CONTAINER *pTmp = NewDataContainer();
                        if( !pTmp ) return -2;
                        pTmp->pData = NewRecType();
                        if( !pTmp->pData) return -2;

                        *(pTmp->pData) = Key;

                        QuickSortData( pSearchDataLeaf->pDataCont,0, BTREE_DEGREE-1,pTmp );

                        pSearchIndexLeaf->IndexKeys[i].pKey = pDataLeaf->pDataCont[0]->pData;
                    }
                    return 0;
                }
            }
        }
        
        m_bMadeList = false;

        //左右兄弟都没有空间
        //只好把数据叶拆分成两个
        BTREE_DATA_LEAF *pDataLeaf = NewDataLeaf();
        if( !pDataLeaf ) return -2;

        INDEX_KEY   NewKey;
        int j,k,l;
        for ( j = (BTREE_DEGREE / 2), k = 0; j < BTREE_DEGREE; j++, k++)
        {
            pDataLeaf->pDataCont[k] = pSearchDataLeaf->pDataCont[j];
            pSearchDataLeaf->pDataCont[j] = NULL;
        }
        //数据叶拆分后，新增的 Key 应该放在那一方.
        if ( Key < *(pDataLeaf->pDataCont[0]->pData) )
        {

            DATA_CONTAINER *pTmp = NewDataContainer();
            if( !pTmp ) return -2;

            pTmp->pData = NewRecType();
            if( !pTmp->pData ) return -2;

            *(pTmp->pData) = Key;
            QuickSortData( pSearchDataLeaf->pDataCont, 0, BTREE_DEGREE / 2, pTmp);
        }
        else
        {
            DATA_CONTAINER *pTmp = NewDataContainer();
            if( !pTmp ) return -2;

            pTmp->pData = NewRecType();
            if( !pTmp->pData ) return -2;

            *(pTmp->pData) = Key;
            QuickSortData( pDataLeaf->pDataCont, 0, k, pTmp);

        }

        //要插入到索引叶的 NewKey
        NewKey.pKey = pDataLeaf->pDataCont[0]->pData;
        NewKey.pKeyRight = pDataLeaf;

        //数据叶没有空位，看看索引叶有没有
        int nIndexLeafLoc = GetFreeElemInIndexLeaf( pSearchIndexLeaf );
        if ( nIndexLeafLoc > -1 )
        {
            //索引叶有空位
            for ( l = nIndexLeafLoc; l > i ; l -- )
            {
                pSearchIndexLeaf->IndexKeys[l] = pSearchIndexLeaf->IndexKeys[l-1];
            }
            pSearchIndexLeaf->IndexKeys[i] = NewKey;
        }
        else
        //数据叶和索引叶都没有空位置
        {
            if ( SplitIndexLeaf(pSearchIndexLeaf, 
                                NewKey, i ) < 0 ) 
            return -1;

        }
    }
    
    return 0;
}

//向B+Tree 中查找 Key
//返回 NULL，表示查找不到，否则返回符合条件的 RECTYPE*
// pLessThan 如果不为NULL，返回时存放的就是比 Key 小的 RECTYPE*
// pGreaterThan 如果不为NULL，返回时存放的就是比 Key 大的 RECTYPE*
template <class RECTYPE>
RECTYPE* CMXBTree<RECTYPE>::SearchKey( RECTYPE & Key, SEARCH_KEY *pSK, RECTYPE **pLessThan, RECTYPE **pGreaterThan )
{
    if( pSK )
        memset( pSK, 0, sizeof(SEARCH_KEY) );

    if( ( pSK || pLessThan || pGreaterThan) && MakeDataList() < 0 ) //先做列表
    {
        if( pLessThan ) *pLessThan = NULL;
        if( pGreaterThan ) *pGreaterThan = NULL;
        return NULL;
    }
    //搜索中当前的索引叶
    BTREE_INDEX_LEAF *pSearchIndexLeaf  = m_pRoot;
    //搜索中当前的数据叶
    BTREE_DATA_LEAF  *pSearchDataLeaf   = NULL;
    BTREE_DATA_LEAF  *pSearchDataLeaf2;
    DATA_CONTAINER *pSearchResult;

    RECTYPE* pRet;
    
    bool KeyInIndex = false;
    if ( (GetDataLeaf( Key, pSearchIndexLeaf, pSearchDataLeaf, &KeyInIndex )) < 0 ) return NULL;
    if ( pSearchDataLeaf == NULL ) 
    {
        //唯一的可能性是 pSearchIndexLeaf 的 pLeftLeaf 为 NULL
        if( pLessThan ) *pLessThan = NULL;
        if( pGreaterThan ) *pGreaterThan = pSearchIndexLeaf->IndexKeys[0].pKey;
        return NULL;
    }
    
    int i;
    if ( KeyInIndex )
    {
        //索引叶中已经有了Key了
        pSearchResult = pSearchDataLeaf->pDataCont[0];
        i = 0;
    }
    else
        pSearchResult = SeekInDataLeaf( pSearchDataLeaf,Key, &i);

    if( pSK )
    {
        pSK->m_pSearchResultOrig = pSearchResult;
        pSK->m_pSearchDataLeaf = pSearchDataLeaf;

        pSK->m_GetKey.m_nDataElemIndex = i;
        pSK->m_GetKey.m_pProv = pSearchDataLeaf;
        pSK->m_GetKey.m_DataCont = pSearchResult;

    }

    if( pSearchResult == NULL ) //在数据叶中没有该 Key
    {
        if( i == 0) 
        {
            if( pLessThan ) 
            {
                if( pSearchDataLeaf->pProv )
                {
                    pSearchDataLeaf2 = pSearchDataLeaf->pProv;
                    int j = GetTotalElemInDataLeaf( pSearchDataLeaf->pProv );
                    *pLessThan = pSearchDataLeaf2->pDataCont[j-1]->pData;
                }
                else *pLessThan = NULL;
            }
            if( pGreaterThan )
                *pGreaterThan =  pSearchDataLeaf->pDataCont[0]->pData;
        }
        else
        {
            if( pLessThan ) 
                *pLessThan = pSearchDataLeaf->pDataCont[i-1]->pData;

            if( pGreaterThan )
            {
                if( i < BTREE_DEGREE && pSearchDataLeaf->pDataCont[i] )
                    *pGreaterThan =  pSearchDataLeaf->pDataCont[i]->pData;
                else
                {
                    if( pSearchDataLeaf->pNext )
                    {
                        pSearchDataLeaf2 = pSearchDataLeaf->pNext;
                        *pGreaterThan =  pSearchDataLeaf2->pDataCont[0]->pData;
                    }
                    else *pGreaterThan = NULL;
                }
            }
        }
        return NULL;
    }
    else
    {
        if( i == 0)
        {
            if( pLessThan ) 
            {
                if( pSearchDataLeaf->pProv )
                {
                    pSearchDataLeaf2 = pSearchDataLeaf->pProv;
                    int j = GetTotalElemInDataLeaf( pSearchDataLeaf->pProv );
                    *pLessThan = pSearchDataLeaf2->pDataCont[j-1]->pData;
                }
                else *pLessThan = NULL;
            }