多路搜索树B树

二叉搜索树可以看作是2路的搜索树，也就是每个节点只有2个子节点，如果将这种情况推广，也就是说每个节点可以有多个（≧2）个节点，那么这种树就可以称为是多路树，结合搜索树的特点，节点左侧的大于右侧，这也就是B树。
B树的定义：
①每个节点x中存储的关键字个数为n（在二叉树中，每个节点只包含一个关键字）；每个节点中关键字按照升序排列，即x.key1≦x.key2≦…x.key3；如果该节点为叶子节点，那么节点属性x.leaf为true，否则为false。
②非叶子节点（或称作内部节点）的孩子数量为n+1，有n+1个指向孩子的指针；叶子节点没有孩子。
③非叶子节点的关键字和叶子孩子的关键字
④每个叶子节点具有相同的深度，即树的高度h。
⑤每个节点所包含的关键字个数有上界和下界。用树的最小度数d（d≧2）进行描述，除根节点以外，其余节点中包含的关键字数量n满足：d-1≦n≦2d-1；当一个节点恰好有2d-1个关键字，就说该节点是满的。

B树结构图

// 关键字类型
#define KeyType int
// 关键字的最大数量
#define N 3

// B树节点结构体
typedef struct BTreeNode
{
    int keyNum=0;                 // 节点中关键字的数量
    KeyType key[N];               // 存储关键字的数组
    struct BTreeNode *sub[N+1];   // 指向子节点的指针数组
    boolean isleaf=false;         // 当前节点是否为叶子节点，false：不是，true：是
}BTreeNode, *pBTreeNode;

B树的高度：
如果n≧1，那么对于任意一棵包含n个关键字、高度为h、最小度数d≧2的B树T，有

h ≦ logd(n+1)/2

这个我们很容易通过之前对二叉树的分析得出。
B树的查找：
查找的方式和二叉搜索树基本上类似，只不过在每个节点上多了一些比较而已，也就是多路分支选择，可采取递归的方式进行查询：

// B树查询结果结构体
typedef struct
{
    BTreeNode *pointer;           // 指向节点的指针
    int pos;                  // 关键字在数组中的索引
}BTreeSearchResult;

/**
 * 查找节点
 * T : 根节点
 * k ：节点key值
 * return : 查询的结果
 */
BTreeSearchResult SearchBTree( BTreeNode T, KeyType k )
{
    BTreeNode temp = T;
    BTreeSearchResult res;
    int i = 0;

    // 循环查找
    while ((i < temp->keyNum) && (k > temp->key[i])) {
        i++;
    }

    // 找到结果
    if ((i < T->keyNum) && (k == temp->key[i])) {
        res.pointer = temp;
        res.i = i;
        return res;
    } else if (temp->isleaf) { // 叶子节点
        return NULL
    } else { // 递归查找
        ReadDisk(temp->sub[i])
        return SearchBTree(temp->sub[i], key)
    }
}

B树的插入：
为确保B树在插入一个新的关键字后，仍旧是一棵合法的B树，我们就不能像二叉树中插入节点那样，直接创建一个节点并作为某个节点的子节点直接插入，而是要将关键字插入到已经存在的叶子节点中去。这里要注意的是插入到B树的叶子节点，不是非叶子节点，也不是创建一个新的叶子节点。其具体步骤是：自定向下遍历，根据关键字的大小选择相应的分支，继续向下遍历，直到找到相应的叶子节点。然后判断叶子节点是否已满，如果未满，就直接插入到相应的关键字位置。如果节点已满，就需要对节点进行分裂，其做法是将中间的节点提出来，然后加入到父节点中，父节点的两个指针分别指向分裂的两个节点。现在有个问题是，如果父节点也已经满了，我们需要对父节点进行分裂，因此为了使问题变得简单，我们自顶向下的遍历过程中就对所有已经满的节点进行分裂，确保在分裂一个节点时其父节点不是满的。

/**
 * 写入磁盘
 * 写入的节点 : 节点指针
 */
void WriteDisk( pBTreeNode n ){

    // 这里为了演示，循环输出关键字的数值
    int i = N;

    printf("写入磁盘：\n");
    while ( i-- ) {
        printf("%c ", n->key[i]);
    }
    printf("\n");
}

/**
 * 读入磁盘
 * 返回值：读入的节点
 */
void ReadDisk( pBTreeNode* n ){
    // 这里为了演示，循环输出关键字的数值
    int i = N;

    printf("写入磁盘：\n");
    while ( i-- ) {
        printf("%c ", (*n)->key[i]);
    }
    printf("\n");
}

/**
 * 插入一个关键字
 * T : 根节点
 * k ：关键字key值
 * return : 查询的结果 0：成功 ，-1：失败
 */
int InsertBTree( pBTreeNode tree,  KeyType k)
{
    pBTreeNode newnode,
               np = *tree;
    // 节点为空
    if ( NULL == np ) {
        // 从内存中分配一个节点
        newnode = (pBTreeNode)malloc(sizeof(BTreeNode));
        // 默认为叶子节点
        newnode.isleaf = true;
        // 关键字数量为0
        newnode.keyNum = 0;
        // 树指针指向根节点
        *T = newnode;
        // 写入磁盘
        WriteDisk(newnode);

        // 直接返回
        return 0;
    }

    // 遍历寻找插入位置，检查节点是否已满
    // 如果已满需要进行分裂
    if ( np.keyNum == N ) {
        // 创建一个新节点
        newnode = (pBTreeNode)malloc(sizeof(BTreeNode));
        newnode.isleaf = false;
        newnode.keyNum = 0;
        newnode.sub[0] = np;
        // 重新定义为根
        np = newnode;
        // 分裂原节点
        SplitBTree( np, 0 );
        insertNotFullNodeBTree( np, k );
    } else {// 如果未满，直接插入
        insertNotFullNodeBTree( np, k );
    }

    return 0;
}
/**
 * 分裂节点
 * np : 节点
 * i : 待分裂的子节点索引
 * return : 分裂结果 0：成功，-1：失败
 */
int SplitBTree( BTreeNode &np, int i)
{
    int j,m;
    // 裂开之后的左半部分
    pBTreeNode nl = np.sub[i];
    // 裂开之后的右半部分
    pBTreeNode nr = CreateBTreeNode();

    // 找到中间关键字
    m = (N+1) / 2;
    // 移动关键字
    for ( j = 0; j < N-m; j++ ) {
        nr.key[j] = nl.key[m+j];
    }
    // 如果是非叶子节点，还需要移动子节点
    if ( !nl.isleaf) {
        for ( j = 0; j < N-m; j++ ) {
            nr.sub[j] = nl.sub[m+j];
        }
    }

    // 更新左部分数量
    nl.keyNum = m-1;

    // 更新指针
    for ( j = np.keyNum; j > i; j-- ) {
        np.sub[j] = np.sub[j-1];
    }
    // 设置指向分裂出来的右半部分
    np.sub[i] = nr;
    // 更新关键字
    for ( j = np.keyNum; j > i; j-- ) {
        np.key[j] = np.key[j-1];
    }
    // 设置提取出来的关键字
    np.key[i] = nl.key[m-1];
    // 更新父节点关键字数量
    np.keyNum++;

    return 0;
}

/** 
 * 插入关键字到未满节点中
 * np : 节点
 * i : 待分裂的子节点索引
 * return : 插入结果 0：成功，-1：失败
 */
int insertNotFullNodeBTree( BTreeNode &np, int k )
{
    int i = np.keyNum;// 节点的关键字数量

    // 如果是叶子节点，选择合适的位置插入
    if ( np.isleaf ) {
        while ( i-- && np.key[i] > k ) {
            np.key[i] = np.key[i-1];
        }
        // 找到位置
        np.key[i] = k;
        np.keyNum++;
        // 写入磁盘
        WriteDisk(np);

        return 0;

    } else {// 寻找指定的非叶子节点，递归插入

        while ( i-- && np.key[i] > k );

        // 找到位置，递归插入，送入的是节点的地址
        ReadDisk( &np.sub[i] );

        // 如果节点已满，需要进行分裂
        if (np.sub[i].keyNum == N ) {
            SplitBTree(np.sub[i], i);
            // 分裂之后，再对待插入关键字和提取上来的关键字作大小比较
            if ( k > np.key[i] ) {
                i++;
            }
        }
        // 此时递归插入关键字到未满节点中
        insertNotFullNodeBTree( np.sub[i], k );
    }
}