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

发布时间:2023年12月18日

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


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


前言

要解决问题: 实现一个最简陋的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编辑器中实现可视化, 看随着输入, 树的分裂成长.

BTree
41
BTree
41 467
BTree
41 334 467
BTree
41 334 467 500
BTree
41 169 334 467 500
BTree
334
41 169
467 500 724
BTree
334
41 169
467 478 500 724
BTree
334
41 169
358 467 478 500 724
BTree
334 478
41 169
358 467
500 724 962
BTree
334 478
41 169
358 464 467
500 724 962
BTree
334 478
41 169
358 464 467
500 705 724 962
BTree
334 478
41 145 169
358 464 467
500 705 724 962
BTree
334 478
41 145 169 281
358 464 467
500 705 724 962
BTree
334 478
41 145 169 281
358 464 467
500 705 724 827 962
BTree
334 478 724
41 145 169 281
358 464 467
500 705
827 961 962
BTree
334 478 724
41 145 169 281
358 464 467
491 500 705
827 961 962
BTree
334 478 724
41 145 169 281
358 464 467
491 500 705
827 961 962 995
BTree
334 478 724
41 145 169 281
358 464 467
491 500 705
827 942 961 962 995
BTree
334 478 724 961
41 145 169 281
358 464 467
491 500 705
827 827 942
962 995
BTree
334 478 724 961
41 145 169 281
358 436 464 467
491 500 705
827 827 942
962 995
BTree
334 478 724 961
41 145 169 281
358 391 436 464 467
491 500 705
827 827 942
962 995
BTree
334 478 724 961
41 145 169 281
358 391 436 464 467
491 500 604 705
827 827 942
962 995
BTree
334 478 724 961
41 145 169 281
358 391 436 464 467
491 500 604 705
827 827 902 942
962 995
BTree
334 478 724 961
41 145 153 169 281
358 391 436 464 467
491 500 604 705
827 827 902 942
962 995
BTree
153 334 478 724 961
41 145
169 281 292
358 391 436 464 467
491 500 604 705
827 827 902 942
962 995
BTree
478
153 334 436
41 145
169 281 292
358 382 391
464 467
724 961
491 500 604 705
827 827 902 942
962 995
BTree
478
153 334 436
41 145
169 281 292
358 382 391 421
464 467
724 961
491 500 604 705
827 827 902 942
962 995
BTree
478
153 334 436
41 145
169 281 292
358 382 391 421
464 467
724 961
491 500 604 705 716
827 827 902 942
962 995
BTree
478
153 334 436
41 145
169 281 292
358 382 391 421
464 467
604 724 961
491 500
705 716 718
827 827 902 942
962 995
BTree
478
153 334 436
41 145
169 281 292
358 382 391 421
464 467
604 724 961
491 500
705 716 718
827 827 895 902 942
962 995
BTree
478
153 334 436
41 145
169 281 292
358 382 391 421
447 464 467
604 724 961
491 500
705 716 718
827 827 895 902 942
962 995
BTree
478
153 334 436
41 145
169 281 292
358 382 391 421
447 464 467
604 724 895 961
491 500
705 716 718
726 827 827
902 942
962 995

总结

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


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


文章来源:https://blog.csdn.net/m0_54206076/article/details/135050727
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。