cmxbtree 类使用说明.txt

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

            CMXBTree 类使用说明
=============================================================

1、概述
-------
    CMXBTree 的主要作用是在内存中建立一棵B+树，主要针对数据
量较大，查询频繁的数据，例如话单分离中局向的查询、配置文件
中的设置查询等。总之，CMXBTree 可被视作一个在内存中的数据库
使用。其特点是：短小精悍。


2、使用 CMXBTree 类
-------------------
    CMXBTree 被定义为一个模板(C++ Template)，定义格式是：
    CMXBTree< RECTYPE > bt;
    
    例如，如果要想 定义一个 int 的 B+Tree 可写作：
    CMXBTree< int > btInt;
    
    注意：模板中的 RECTYPE 必须支持两个操作符：
        小于(<) 和 赋值(=)


3、CMXBTree 所支持的方法
------------------------

[1]、增加树中的元素
    int InsertKey( RECTYPE &Key ); 
    入口参数是要插入的 元素 的引用，主要目的是为了`快`。
    返回值：
    0   表示正常
    -1  表示 B+Tree 出错，即 CMXBTree 有 BUG
    -2  申请不到内存，内存不足
    
[2]、删除树中的元素
    int DeleteKey( RECTYPE &Key );
    入口参数是要删除的 元素 的引用，主要目的是为了`快`。
    返回值：
    1   表示要删除的 Key 不在树中
    0   表示正常删除
    -1  表示 B+Tree 出错，即 CMXBTree 有 BUG

[3]、在树中搜索某个 Key
    RECTYPE *SearchKey( RECTYPE & Key, 
        RECTYPE **pLessThan = NULL, 
        RECTYPE **pGreaterThan = NULL 
        );
    入口参数：
    Key：要查找的 Key 的引用
    pLessThan： 当该参数不为 NULL 时，不管能不能在树中找到Key
                它返回比 Key 小的元素中最大的一个元素的指针，如果
                这个指针是 NULL，表示 Key 在树中的值最小，没有
                别的元素比它小。

    pGreaterThan： 当该参数不为 NULL 时，不管能不能在树中找到Key
                它返回比 Key 大的元素中最小的一个元素的指针，如果
                这个指针是 NULL，表示 Key 在树中的值最大，没有
                别的元素比它大。                

    返回值：
        如果树中存在于 Key 的值相等的元素，则返回该元素的指针，
        否则，返回 NULL        

[4]、继续搜索具有同样 Key 的元素（与SearchKey配合使用）
        RECTYPE *SearchNextKey( void );
        
    当我们使用 SearchKey 查找到一个满足条件的元素后，可以用该方法
    继续搜索下一个符合同样条件的元素。由于采用了队列，该方法的返回
    将`飞快`。
    返回值：与 SearchKey 相同


[5]、无条件返回树中的第一个元素（也就是树中最小的元素）
    RECTYPE *GetFirstKey( void );
    返回值：指向树中的第一个元素的指针，如果是 NULL，表示该树已空。

[6]、无条件返回树中的下一个元素（与 GetFirstKey 配合使用）
    RECTYPE *GetNextKey( void );
    这个方法所返回的元素一定是从小到大排列的。
    返回值：指向树中的第一个元素的指针，如果是 NULL，表示该树已空。

[7]、把数砍掉
    int DestroyTree( void )
    把数连根拔起、释放内存
    返回值
    0   表示正常
    -1  表示 B+Tree 出错，即 CMXBTree 有 BUG


4、使用例子
-----------

    //先定义一棵树，元素类型是：CMXString
    //注：CMXString 是我定义的一个专门处理字符串的类
    //    它支持 小于操作符(<) 和 赋值操作符(=)
    CMXBTree<CMXString> bt;
    
    //定义需要的变量及指针
    CMXString str2, str, *pStr, *pStr1, *pStr2;

    //这是局向
    char* pszStr = " 8517 8519  8610 8611 8615 8620 8625 8630 8635 "
                    "8640 8645 8650 8655 8660 8665 8540 8541 8542 "
                    "8670 8672 8675 8677 8682 8684 8686 8621 "
                    "8690 8691 8692 8693 8694 8697 85186";
    str = pszStr;
    str2 = str.GetFirstToken(" "); //以空格为分隔符，把 pszStr 一个个地切开
    while( !str2.IsEmpty() )  //如果还没有到字符串的末尾
    {
        if( str2.Length() > 0 ) //如果两个空格间有东西，
            bt.InsertKey( str2 ); //把 str2 插入
        str2 = str.GetNextToken( ); //取下一个局向
    }   
    
    //来到这里表示树已建成
    //接下来，我们把树的所有元素按照从小到大的顺序排列出来
    pStr = bt.GetFirstKey();
    while( pStr )
    {
        printf("[%s]", pStr->C_str() );
        pStr = bt.GetNextKey();
    }

    printf("\n");
    
    //看看字符串 "85186" 是否存在
    str2 = "85186";
    pStr = bt.SearchKey( str2, &pStr1, &pStr2 );
    if( pStr )
        printf("[%s] is in the tree\n", *pStr );
    else
        printf("Cannot find [%s]\n", *pStr );

    //看看电话号码 8677123 是否在这个局中
    
    str2 = "8677123"
    pStr = bt.SearchKey( str2, &pStr1, &pStr2 );
    if( pStr1 ) 
    {
        if( pStr1 && str2.FindFirst( *pStr1 ) == str2 ) //*pStr1 应该就是 8667
            printf("Yes!\n");
    }
    //如果 pStr1 为 NULL ，表示 str2 比所有的局向数据小，
    //则表示 str2 一定不在局向内
    
这段代码的输出结果将是：
[8517][85186][8519][8540][8541][8542][8610][8611][8615][8620][8621][8625][8630][
8635][8640][8645][8650][8655][8660][8665][8670][8672][8675][8677][8682][8684][86
86][8690][8691][8692][8693][8694][8697]
[85186] is in the tree
Yes!