2023-12-18 C语言实现一个最简陋的B-Tree

---

点击 <C 语言编程核心突破> 快速C语言入门

---

---

前言

要解决问题: 实现一个最简陋的B-Tree, 研究B-Tree的性质. 对于B树, 我是心向往之, 因为他是数据库的基石, 描述语言好像很容易理解, 但不造个轮子就不能彻底弄明白, 于是, 造个轮子.

想到的思路: 根据AI给的代码架子进行修改, 现在AI是个好东西, 虽说给的代码不一定靠谱, 但是debug一下, 还能深入了解, 总之是很有用.

其它的补充: 有一份C++ 的B-Tree, 是通过算法4的java代码移植的, 但是C++ 的内存管理教育了我, 太难整了, 于是一气之下, 全改为智能指针, 头疼的事就解决了. 也是很简陋的代码, 只有增查, 没有删改, 就暂时不提供了.

---

一、C语言B-Tree

基本架构:

为了适应不同的B-Tree节点, 通过宏BTREE_ORDER_SIZE 规定子节点的数量, 使用typedef int keyOfBTree;定义节点的key类型, 以适应不同需求.

BTreeNode的结构中, 对于值和子节点存储, 直接使用数组, 而不是指针, 好处是初始化的时候比较容易, free的时候也不容易出错, 毕竟都是数组, delete BTreeNode直接就完事了, 不用一个个的删除值, 省时间.

不好之处, 可能是自由度和空间利用度受限, 毕竟到最后叶子节点, 不管用不用子节点, 都要开辟子节点数组内存, 有一点点浪费.

打印节点内容以及释放树, 是用的递归, 毕竟这个用递归太容易了.

代码中最复杂的是分裂节点和向树中插入值, 需要慢慢体会, 多琢磨也不是太难.

至于删除节点和更改节点, 这里没有实现.

BTree.h头文件.

#ifndef BTREE_
#define BTREE_

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// B树的阶数，决定每个节点的孩子数量
#define BTREE_ORDER_SIZE 6

// 比较函数指针类型
typedef int (*cmpFuncPtr)(void *, void *);

// 定义B树的key类型, 利于泛型
typedef int keyOfBTree;

// 打印函数指针类型
typedef void (*printFun)(keyOfBTree);

// B树的节点结构
typedef struct BTreeNode
{
    keyOfBTree keys[BTREE_ORDER_SIZE - 1];      // 关键字数组
    struct BTreeNode *childs[BTREE_ORDER_SIZE]; // 孩子节点指针数组
    uint32_t num; // 当前节点中的关键字数量
    int is_leaf;  // 是否为叶子节点
} BTreeNode;

typedef BTreeNode *BTree;

// 创建节点
BTreeNode *createNode(int is_leaf);

// 查找关键字在节点中的索引位置
int searchKeyIndex(BTreeNode *node, keyOfBTree key, cmpFuncPtr cmp);

// 插入关键字到节点中的指定位置
void insertKey(BTreeNode *node, keyOfBTree key, cmpFuncPtr cmp);

// 分裂一个满节点，将中间的关键字提升为父节点，并创建两个新的子节点
void splitNode(BTreeNode *parent, int child_index);

// 在B树中插入关键字
void insert(BTreeNode **root, keyOfBTree key, cmpFuncPtr cmp);

// 打印B树的关键字
void printBTree(BTreeNode *node, printFun printKey, int left, int *cnt);

// 释放BTree
void freeBTree(BTreeNode **node);

#endif

BTree.c实现.

#include "BTree.h"

// 创建节点
BTreeNode *createNode(int is_leaf)
{
    BTreeNode *node = (BTreeNode *)malloc(sizeof(BTreeNode));
    memset(node, 0, sizeof(BTreeNode));
    node->is_leaf = is_leaf;
    return node;
}

// 查找关键字在节点中的索引位置
int searchKeyIndex(BTreeNode *node, keyOfBTree key, cmpFuncPtr cmp)
{
    int index = 0;
    while (index < node->num && cmp(&key, &(node->keys[index])) > 0)
    {
        index++;
    }
    return index;
}

// 插入关键字到节点中的指定位置
void insertKey(BTreeNode *node, keyOfBTree key, cmpFuncPtr cmp)
{
    int index = (int)node->num - 1;
    while (index >= 0 && cmp(&key, &(node->keys[index])) < 0)
    {
        node->keys[index + 1] = node->keys[index];
        index--;
    }
    node->keys[index + 1] = key;

    node->num++;
}

// 分裂一个满节点，将中间的关键字提升为父节点，并创建两个新的子节点
void splitNode(BTreeNode *parent, int child_index)
{
    BTreeNode *child = parent->childs[child_index];

    BTreeNode *new_node = createNode(child->is_leaf);
    new_node->num = BTREE_ORDER_SIZE / 2 - 1;

    for (int i = 0; i < new_node->num; i++)
    {
        new_node->keys[i] = child->keys[BTREE_ORDER_SIZE / 2 + i];
    }

    if (!child->is_leaf)
    {
        for (int i = 0; i < BTREE_ORDER_SIZE / 2; i++)
        {
            new_node->childs[i] = child->childs[BTREE_ORDER_SIZE / 2 + i];
        }
    }

    child->num = BTREE_ORDER_SIZE / 2 - 1;

    for (int i = (int)parent->num; i > child_index; i--)
    {
        parent->childs[i + 1] = parent->childs[i];
    }

    parent->childs[child_index + 1] = new_node;

    for (int i = (int)parent->num - 1; i >= child_index; i--)
    {
        parent->keys[i + 1] = parent->keys[i];
    }

    parent->keys[child_index] = child->keys[BTREE_ORDER_SIZE / 2 - 1];
    parent->num++;
}

// 在B树中插入关键字
void insert(BTreeNode **root, keyOfBTree key, cmpFuncPtr cmp)
{
    BTreeNode *node = *root;

    // 如果根节点为空，则创建新的根节点
    if (node == NULL)
    {
        *root = createNode(1);
        insertKey(*root, key, cmp);
        return;
    }

    // 如果根节点已满，则需要创建一个新的根节点
    if (node->num == BTREE_ORDER_SIZE - 1)
    {
        BTreeNode *new_root = createNode(0);
        new_root->childs[0] = node;
        *root = new_root;
        splitNode(new_root, 0);
        insert(root, key, cmp); // 递归插入
        return;
    }

    // 如果根节点既非空也未满，直接插入
    while (1)
    {
        int index = searchKeyIndex(node, key, cmp);
        if (node->is_leaf)
        {
            insertKey(node, key, cmp);
            break;
        }

        if (node->childs[index]->num == BTREE_ORDER_SIZE - 1)
        {
            splitNode(node, index);
            if (cmp(&key, &(node->keys[index])) > 0)
            {
                index++;
            }
        }
        node = node->childs[index];
    }
}

// 打印B树的关键字
void printBTree(BTreeNode *node, printFun printKey, int left, int *cnt)
{
    if (node)
    {
        printf("%c%.2d([", "ABCDEFG"[left++], ++*cnt);
        for (int i = 0; i < node->num; i++)
        {
            printKey(node->keys[i]);
        }
        printf("]);\n");

        if (!node->is_leaf)
        {
            int leftL = left - 1;
            int cntL = *cnt;
            for (int i = 0; i <= node->num; i++)
            {
                printf("%c%.2d==>", "ABCDEFG"[leftL], cntL);
                printBTree(node->childs[i], printKey, left, cnt);
            }
            printf("\n");
        }
    }
}

// 释放BTree
void freeBTree(BTreeNode **node)
{
    if (*node)
    {
        // 非叶子节点必有子节点, 递归删除子节点
        if (!(*node)->is_leaf)
        {
            // 子节点的数量不会大于key数量加1, 所以不用free child数组中所有节点;
            for (int i = 0; i <= (*node)->num; i++)
            {
                freeBTree(&((*node)->childs[i]));
            }
        }

        free(*node);
        *node = NULL;
    }
}

测试用例

#include "BTree.h"
#include <stdlib.h>

#define SIZE 32

void printKey(keyOfBTree key)
{
    printf("%d\t", key);
}

int cmpInt(const int *lhs, const int *rhs)
{
    return *lhs - *rhs;
}

int main()
{
    int arr[SIZE];
    for (int i = 0; i != SIZE; ++i)
    {
        arr[i] = rand() % 1000;
    }

    // 创建一个空的B树
    BTree root = NULL;

    // 依次插入关键字
    for (int j = 0; j != SIZE; ++j)
    {
        insert(&root, arr[j], (cmpFuncPtr)cmpInt);

        printf("```mermaid\ngraph TD;\nsubgraph BTree\n");
        int cnt = 0;

        // 打印B树
        printBTree(root, printKey, 0, &cnt);

        printf("end\n```\n\n");
    }

    // 释放内存
    freeBTree(&root);

    return 0;
}

二、可视化

通过运行测试用例, 导出mermaid文本, 可以在markdown编辑器中实现可视化, 看随着输入, 树的分裂成长.

---

总结

通过以上的代码, 基本可以粗略了解B-Tree的性质, 就是树高增长缓慢, 单节点可以存储非常多的值, 查询速度优秀, 更贴近硬盘优化, 我们常见的数据库, mysql, sqlite, postgresql的基础都是B-Tree以及其变种, B+Tree, 了解底层, 期待更好的理解数据库, 在进行数据库设置时, 可以进行贴近底层的思考.

---

点击 <C 语言编程核心突破> 快速C语言入门

---