B树与B+树

B树

限制：所有的叶子节点在同一层

定义

B树，B-,B+树

B/B-树为同一东西

btree:所有节点存储数据

b+tree:叶子节点存储数据，内节点索引

难点：

1.根节点分叉

2.节点分裂，先分裂再添加

#include <stdio.h>
#include <stdlib.h>
#define SUB_M 3 // SUB_M = m/2
// 节点定义
typedef struct btree_node
{
    // int keys[SUB_M * 2 - 1];                 // 5
    int *keys;
    struct btree_node *childrens[SUB_M * 2]; // 6
    int num;
    int leaf;
} btree_node;
// 树定义
typedef struct btree
{
    btree_node *root;
} btree;

/*
根节点分裂，一个分三个
合并
借位
*/
btree_node *btree_create_node(int leaf)
{
    btree_node *node = (btree_node *)calloc(1, sizeof(btree_node));
    if (node == NULL)
        return NULL;
    node->leaf = leaf;
    node->keys = (int *)calloc(SUB_M * 2 - 1, sizeof(int));
    // node->childrens = (btree_node **)calloc(SUB_M * 2, sizeof(btree_node *));
    for (int i = 0; i < SUB_M * 2; i++)
    {
        node->childrens[i] = (btree_node *)calloc(1, sizeof(btree_node));
    }

    node->num = 0;
    return node;
}
void btree_destory_node(btree_node *node)
{
    if (node == NULL)
        return;
    free(node->keys);
    for (int i = 0; i < SUB_M * 2; i++)
    {
        free(node->childrens[i]);
    }
    free(node);
}
/**分裂
 * x为分裂的父节点，i为分裂节点对于父节点的位置
 */
void btree_split_child(btree *T, btree_node *x, int idx)
{
    btree_node *y = x->childrens[idx];
    btree_node *z = btree_create_node(y->leaf);
    z->num = SUB_M - 1;
    for (int j = 0; j < SUB_M - 1; j++)
    {
        z->keys[j] = y->keys[j + SUB_M];
    }
    if (y->leaf == 0) // 内节点
    {
        for (int i = 0; i < SUB_M; i++)
        {
            z->childrens[i] = y->childrens[i + SUB_M];
        }
    }
    int i = 0;
    y->num = SUB_M;
    for (i = x->num; i >= idx + 1; i--)
    {
        x->childrens[i + 1] = x->childrens[i];
    }
    x->childrens[i + 1] = z;
    for (i = x->num - 1; i >= idx; i--)
    {
        x->keys[i + 1] = x->keys[i];
    }
    x->keys[i] = y->keys[SUB_M];
    x->num++;
}
void btree_insert(btree *T)
{
    btree_node *r = T->root;
    if (r->num == SUB_M * 2 - 1)
    {
        btree_node *node = btree_create_node(0);
        T->root = node;
        node->childrens[0] = r;
        btree_split_child(T, node, 0);
    }
}
void btree_merge(btree *T, btree_node *x, int idx)
{
    btree_node *left = x->childrens[idx];
    btree_node *right = x->childrens[idx + 1];

    left->keys[left->num] = x->keys[idx];
    int i = 0;
    for (i = 0; i < right->num; i++)
    {
        left->keys[i + SUB_M] = right->keys[i];
    }
    if (!left->leaf)
    {
        for (i = 0; i < SUB_M; i++)
        {
            left->childrens[i + SUB_M] = right->childrens[i];
        }
    }
    left->num += SUB_M;
    btree_destory_node(right);
    for (i = idx + 1; i < x->num; i++)
    {
        x->keys[i - 1] = x->keys[i];
        x->childrens[i] = x->childrens[i + 1];
    }
}

int main()
{
    return 0;
}