基本的 B 树和 B+ 树操作的代码

news/2025/3/3 20:28:05/

假设 B 树节点的最大键数为 M，而 B+ 树节点的最大键数为 N（N >= M）。
// B 树节点结构
typedef struct BTreeNode {
    int is_leaf;                // 是否为叶子节点
    int num_keys;               // 当前节点存储的键的数量
    int keys[M-1];              // 存储的键数组
    struct BTreeNode *children[M];  // 子节点指针数组
} BTreeNode;

// B+ 树节点结构
typedef struct BPlusTreeNode {
    int is_leaf;                // 是否为叶子节点
    int num_keys;               // 当前节点存储的键的数量
    int keys[N-1];              // 存储的键数组
    struct BPlusTreeNode *children[N];  // 子节点指针数组
    struct BPlusTreeNode *next_leaf;   // 指向下一个叶子节点的指针
} BPlusTreeNode;

// 在 B 树中插入键值
void insert_B_tree(BTreeNode *root, int key) {
    if (root->num_keys == M-1) {
        // 根节点已满，需要拆分
        BTreeNode *new_root = malloc(sizeof(BTreeNode));
        new_root->is_leaf = 0;
        new_root->num_keys = 0;
        new_root->children[0] = root;
        split_child(new_root, 0);
        insert_nonfull(new_root, key);
    } else {
        insert_nonfull(root, key);
    }
}

// 在 B+ 树中插入关键字
void insert_BPlus_tree(BPlusTreeNode **root, int key) {
    if (*root == NULL) {
        // 树为空，创建新的根节点
        BPlusTreeNode *new_root = malloc(sizeof(BPlusTreeNode));
        new_root->is_leaf = 1;
        new_root->num_keys = 1;
        new_root->keys[0] = key;
        new_root->children[0] = NULL;
        new_root->next_leaf = NULL;
        *root = new_root;
    } else {
        // 找到待插入叶子节点
        BPlusTreeNode *leaf = find_leaf(*root, key);

        if (leaf->num_keys < N-1) {
            // 叶子节点未满，直接插入
            insert_to_leaf(leaf, key);
        } else {
            // 叶子节点已满，需要拆分
            BPlusTreeNode *new_leaf = split_leaf(leaf);
            insert_to_leaf_after_split(root, leaf, new_leaf, key);
        }
    }
}

// 查找键在 B 树中的位置
BTreeNode* search_B_tree(BTreeNode *node, int key) {
    int i = 0;
    while (i < node->num_keys && key > node->keys[i]) {
        i++;
    }
    
    if (i < node->num_keys && key == node->keys[i]) {
        return node;  // 找到了
    } else if (node->is_leaf) {
        return NULL;  // 到达叶子节点仍未找到
    } else {
        return search_B_tree(node->children[i], key);  // 递归查找子节点
    }
}

// 查找键在 B+ 树中的位置
BPlusTreeNode* search_BPlus_tree(BPlusTreeNode *node, int key) {
    if (node == NULL) {
        return NULL;  // 树为空，未找到
    }

    int i = 0;
    while (i < node->num_keys && key > node->keys[i]) {
        i++;
    }
    
    if (i < node->num_keys && key == node->keys[i]) {
        return node;  // 找到了
    } else if (node->is_leaf) {
        return NULL;  // 到达叶子节点仍未找到
    } else {
        return search_BPlus_tree(node->children[i], key);  // 递归查找子节点
    }
}

// 将键插入非满节点
void insert_nonfull(BTreeNode *node, int key) {
    int i = node->num_keys - 1;

    if (node->is_leaf) {
        // 节点为叶子节点，直接将键插入合适位置
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->num_keys++;
    } else {
        // 节点为内部节点，递归向下插入合适位置
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;

        if (node->children[i]->num_keys == M-1) {
            // 子节点已满，需要拆分
            split_child(node, i);

            if (key > node->keys[i]) {
                i++;
            }
        }
        insert_nonfull(node->children[i], key);
    }
}

// 将键插入叶子节点
void insert_to_leaf(BPlusTreeNode *leaf, int key) {
    int i = leaf->num_keys - 1;

    while (i >= 0 && key < leaf->keys[i]) {
        leaf->keys[i + 1] = leaf->keys[i];
        i--;
    }

    leaf->keys[i + 1] = key;
    leaf->num_keys++;
}

// 拆分 B 树节点的子节点
void split_child(BTreeNode *parent, int index) {
    BTreeNode *child = parent->children[index];
    
    // 创建新的节点用于存储分裂出的键和子节点
    BTreeNode *new_node = malloc(sizeof(BTreeNode));
    new_node->is_leaf = child->is_leaf;
    new_node->num_keys = M / 2 - 1;
    
    for (int i = 0; i < M / 2 - 1; i++) {
        new_node->keys[i] = child->keys[i + M / 2];
    }
    
    if (!child->is_leaf) {
        for (int i = 0; i < M / 2; i++) {
            new_node->children[i] = child->children[i + M / 2];
        }
    }
    
    child->num_keys = M / 2 - 1;
    
    // 将父节点中的键和子节点后移一位
    for (int i = parent->num_keys; i > index; i--) {
        parent->keys[i] = parent->keys[i - 1];
        parent->children[i + 1] = parent->children[i];
    }
    
    parent->keys[index] = child->keys[M / 2 - 1];
    parent->children[index + 1] = new_node;
    parent->num_keys++;
}

// 拆分叶子节点
BPlusTreeNode* split_leaf(BPlusTreeNode *leaf) {
    BPlusTreeNode *new_leaf = malloc(sizeof(BPlusTreeNode));
    new_leaf->is_leaf = 1;

    // 计算要将键和子节点拆分到新叶子节点的位置
    int mid_point = (leaf->num_keys + 1) / 2;
    int num_keys_new_leaf = leaf->num_keys - mid_point;
    
    // 将键拆分到新叶子节点
    for (int i = 0; i < num_keys_new_leaf; i++) {
        new_leaf->keys[i] = leaf->keys[mid_point + i];
    }
    
    // 更新叶子节点的键的数量
    leaf->num_keys = mid_point;
    new_leaf->num_keys = num_keys_new_leaf;
    
    // 更新链表指针
    new_leaf->next_leaf = leaf->next_leaf;
    leaf->next_leaf = new_leaf;
    
    return new_leaf;
}

// 在拆分后的叶子节点中插入键
void insert_to_leaf_after_split(BPlusTreeNode **root, BPlusTreeNode *leaf, BPlusTreeNode *new_leaf, int key) {
    if (leaf == *root) {
        // 如果拆分的叶子节点为根节点，需要创建新的根节点
        BPlusTreeNode *new_root = malloc(sizeof(BPlusTreeNode));
        new_root->is_leaf = 0;
        new_root->num_keys = 1;
        new_root->keys[0] = new_leaf->keys[0];
        new_root->children[0] = leaf;
        new_root->children[1] = new_leaf;
        new_root->next_leaf = NULL;
        *root = new_root;
    } else {
        // 在父节点中插入拆分出的键和子节点指针
        BPlusTreeNode *parent = find_parent(*root, leaf);
        int i = parent->num_keys - 1;

        while (i >= 0 && leaf != parent->children[i]) {
            // 寻找拆分节点在父节点中的位置
            parent->keys[i + 1] = parent->keys[i];
            parent->children[i + 2] = parent->children[i + 1];
            i--;
        }

        parent->keys[i + 1] = new_leaf->keys[0];
        parent->children[i + 2] = new_leaf;
        parent->num_keys++;
    }

    insert_to_leaf(new_leaf, key);
}

 


http://www.ppmy.cn/news/1248202.html

相关文章

文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑不确定性的火电发电商现货-深度调峰市场优化决策》

文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑不确定性的火电发电商现货-深度调峰市场优化决策》

标题涉及到电力行业的领域&#xff0c;尤其是火电发电商在电力市场中面对深度调峰需求时的决策问题。下面是对标题的解读&#xff1a; 考虑不确定性&#xff1a; 这指的是在制定优化决策时&#xff0c;考虑到环境的不确定性&#xff0c;可能包括但不限于电力市场的价格波动、发…
阅读更多...
数据库SQL小技巧大揭秘：IGNORE选项让你的数据处理更从容

数据库SQL小技巧大揭秘：IGNORE选项让你的数据处理更从容

点击上方蓝字关注我 在 MySQL 中&#xff0c;IGNORE 是一种在插入或更新数据时处理冲突的选项。具体来说&#xff0c;在 INSERT | UPDATE 语句中&#xff0c;IGNORE 的作用是在插入或更新数据时忽略特定的错误&#xff0c;而不导致整个操作失败。另外&#xff0c;IGNORE 选项还…
阅读更多...
2023关键事件

2023关键事件

情境/背景&#xff1a; SAP系统未提供配置BOM解析功能&#xff0c;多个业务部长多次开会强调系统没有配置BOM查询功能&#xff0c;严重影响供应链物料管理。目标/任务&#xff1a; 实现SAP系统中配置BOM解析功能自开发定制程序行动/举措&#xff1a; 花费大量业余时间&#xff…
阅读更多...
命令模式 rust和java实现

命令模式 rust和java实现

文章目录 命令模式介绍javarustrust仓库 命令模式 命令模式&#xff08;Command Pattern&#xff09;是一种数据驱动的设计模式。请求以命令的形式包裹在对象中&#xff0c;并传给调用对象。调用对象寻找可以处理该命令的合适的对象&#xff0c;并把该命令传给相应的对象&…
阅读更多...
C语言——数字金字塔

C语言——数字金字塔

实现函数输出n行数字金字塔 #define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>void pyramid(int n) {int i,j,k;for (i1; i<n; i){//输出左边空格&#xff0c;空格数为n-i for (j1; j<n-i; j){printf(" "); } //每一行左边空格输完后输出数字&#…
阅读更多...
重工业ERP包含哪些模块?能为企业带来哪些优势

重工业ERP包含哪些模块?能为企业带来哪些优势

化工、五金、重型机械制造等重工业行业的经营管理模式存在明显的差别化&#xff0c;企业内部的盘点、发货、接单、报价、委外、排产、派工单、工艺、品检等各业务数据的实时和准确共享有利于企业清晰掌握运作情况&#xff0c;及时制定经营策略&#xff0c;提高对市场变化的反应…
阅读更多...
1、windows10系统下Qt5.12.0与卸载

1、windows10系统下Qt5.12.0与卸载

一、安装包下载 1、Qt社区下载 https://download.qt.io/archive/qt/5.12/5.12.10/qt-opensource-windows-x86-5.12.10.exe 2、百度网盘下载 链接&#xff1a;百度网盘 请输入提取码 3、Qt官网下载&#xff1a; Try Qt | 开发应用程序和嵌入式系统 | Qt 二、安装提示 下…
阅读更多...
Git——Git应用入门

Git——Git应用入门

将会介绍以下知识&#xff1a; 搭建Git环境和创建Git版本库&#xff08;init、clone&#xff09;。文件添加、状态检查、创建注释和查看历史记录。与其他Git版本库交互&#xff08;pull、push&#xff09;。解决合并冲突。创建分支列表、列表切换和合并。创建标签。 1、版本控…
阅读更多...
最新文章

Copyright @ 2022~2023