B+树原理详解及C语言实现

news/2025/2/9 5:16:04 标签: b树, c语言, 数据结构, 算法

目录

B+树的原理

B+树的操作过程（图形化演示）

B+树的应用场景

B树与B+树的对比

C语言实现及应用实例

文件结构

总结

B+树的原理

B+树是B树的一种变体，广泛应用于数据库和文件系统中。其原理和特点如下：

  • 数据结构：B+树是一种自平衡的树形数据结构，所有实际数据（键值对）都保存在叶子节点中，内部节点仅存储索引键值，用于引导查找过程。

  • 特点：

    • 叶子节点存储所有数据，内部节点仅作为索引使用。
    • 所有叶子节点通过一个链表相互连接，方便进行范围查询或顺序访问。
    • 树的高度平衡，所有叶子节点都处于同一层，保证树的高度稳定，进而保证查询的效率。

  • 优势：

    • 提供高效的范围查询，因为叶子节点通过链表连接，可以快速访问连续的数据。
    • 内部节点只需要存储键值，减少了内存使用。
    • 更好的缓存利用，因为所有数据都存储在叶子节点中。

B+树的操作过程（图形化演示）

假设有一个阶为3的B+树，插入操作如下：

初始状态

复制

       [10, 20]
      /        \
   [5]        [15] <-> [25, 30]

插入12

  1. 找到插入位置（叶子节点 [15]）。

  2. 分裂叶子节点 [15]，生成新节点 [15, 12]，并调整父节点。

复制

       [10, 20]
      /        \
   [5]        [12, 15] <-> [25, 30]

插入22

  1. 找到插入位置（叶子节点 [25, 30]）。

  2. 分裂叶子节点 [25, 30]，生成新节点 [25, 30, 22]，并调整父节点。

复制

       [10, 20, 25]
      /        |       \
   [5]      [12, 15]   [22, 25, 30]

B+树的应用场景

  • 数据库：B+树广泛用于数据库索引中，尤其是对范围查询性能有高要求的场景。其有序链表特性使得范围查询变得更加高效，这对于数据库中的诸如BETWEEN、ORDER BY等操作非常有利。如MySQL的InnoDB存储引擎，适合需要高效磁盘访问的场景。
  • 文件存储：B+树也适用于文件系统的实现，能够减少磁盘IO次数，提高文件查找和检索的效率。如Linux的ext3/ext4文件系统。
  • 缓存：B+树的结构使其适用于需要频繁访问和更新数据的缓存系统，能够提供稳定的性能。

B树与B+树的对比

B树B+树
数据结构每个节点包含多个键值和子指针，键值有序排列内部节点仅存储索引键值，叶子节点存储实际数据，叶子节点通过链表连接
查找性能查找、插入、删除操作的时间复杂度为O(log n)提供高效的范围查询，查找性能与B树相当
范围查询范围查询性能可能不如B+树范围查询性能高效，因为叶子节点通过链表连接
磁盘IO适用于磁盘存储，减少磁盘访问次数磁盘IO次数少，因为所有数据都集中在叶子节点，且叶子节点通过链表连接
内存使用内部节点存储数据和索引，可能占用较多内存内部节点仅存储索引，减少了内存使用
平衡性所有叶子节点位于同一层级，保持树的平衡同样保持树的平衡，所有叶子节点处于同一层
易用性实现相对复杂，尤其是在节点的分裂和合并操作中实现相对复杂，特别是在管理叶子节点链表时，但范围查询性能优越
范围查询效率较低效率较高
插入/删除复杂相对简单
叶子节点链接不链接叶子节点按链表顺序链接

C语言实现及应用实例

文件结构

  • btree.h: 头文件，包含数据结构和函数声明。
  • btree.c: 实现文件，包含B+树的各种操作。
  • main.c: 示例应用，展示如何使用B+树。

btree.h

#ifndef BTREE_H
#define BTREE_H

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_KEYS 3  // 每个节点的最大关键字数，可以根据需要调整

typedef int KeyType;
typedef int ValueType;

typedef struct BPlusTreeNode {
    int key_count;
    KeyType keys[MAX_KEYS + 1];  // keys[0]到keys[key_count-1]存储实际关键字，keys[key_count]为指向子节点的指针
    struct BPlusTreeNode *children[MAX_KEYS + 1];
    ValueType *values;
    bool leaf;
} BPlusTreeNode;

typedef struct BPlusTree {
    BPlusTreeNode *root;
} BPlusTree;

BPlusTree* create_tree();
BPlusTreeNode* create_node(bool leaf);
void insert(BPlusTree *tree, KeyType key, ValueType value);
BPlusTreeNode* search(BPlusTree *tree, KeyType key, int *index);
void traverse(BPlusTreeNode *node, int depth);
void free_tree(BPlusTree *tree);

#endif // BTREE_H

btree.c

#include "btree.h"
#include <string.h>

BPlusTree* create_tree() {
    BPlusTree *tree = (BPlusTree*)malloc(sizeof(BPlusTree));
    tree->root = create_node(true);
    return tree;
}

BPlusTreeNode* create_node(bool leaf) {
    BPlusTreeNode *node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));
    node->key_count = 0;
    node->leaf = leaf;
    if (leaf) {
        node->values = (ValueType*)malloc(sizeof(ValueType) * (MAX_KEYS + 1));
        memset(node->values, 0, sizeof(ValueType) * (MAX_KEYS + 1));
    } else {
        node->values = NULL;
    }
    memset(node->keys, 0, sizeof(KeyType) * (MAX_KEYS + 1));
    memset(node->children, NULL, sizeof(BPlusTreeNode*) * (MAX_KEYS + 1));
    return node;
}

void insert(BPlusTree *tree, KeyType key, ValueType value) {
    BPlusTreeNode *root = tree->root;
    if (root->key_count == MAX_KEYS) {
        BPlusTreeNode *new_root = create_node(false);
        new_root->children[0] = root;
        new_root->key_count = 1;
        new_root->keys[0] = key;
        split_child(new_root, 0, tree);
        tree->root = new_root;
        insert_non_full(tree->root, key, value);
    } else {
        insert_non_full(root, key, value);
    }
}

void insert_non_full(BPlusTreeNode *node, KeyType key, ValueType value) {
    if (node->leaf) {
        int i = node->key_count - 1;
        while (i >= 0 && node->keys[i] > key) {
            node->keys[i + 1] = node->keys[i];
            node->values[i + 1] = node->values[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->values[i + 1] = value;
        node->key_count++;
    } else {
        int i = node->key_count - 1;
        while (i >= 0 && node->keys[i] > key) {
            i--;
        }
        i++;
        if (node->children[i]->key_count == MAX_KEYS) {
            split_child(node, i, tree);
            if (node->keys[i] < key) {
                i++;
            }
        }
        insert_non_full(node->children[i], key, value);
    }
}

void split_child(BPlusTreeNode *parent, int index, BPlusTree *tree) {
    BPlusTreeNode *full_node = parent->children[index];
    BPlusTreeNode *new_node = create_node(full_node->leaf);
    parent->key_count++;

    for (int i = 0; i < MAX_KEYS / 2; i++) {
        new_node->keys[i] = full_node->keys[i + MAX_KEYS / 2 + 1];
        if (!full_node->leaf) {
            new_node->children[i] = full_node->children[i + MAX_KEYS / 2 + 1];
        } else {
            new_node->values[i] = full_node->values[i + MAX_KEYS / 2 + 1];
        }
    }

    if (!full_node->leaf) {
        new_node->children[MAX_KEYS / 2] = full_node->children[MAX_KEYS + 1];
    }

    full_node->key_count = MAX_KEYS / 2;
    parent->keys[index] = full_node->keys[MAX_KEYS / 2];
    parent->children[index + 1] = new_node;

    if (index == parent->key_count - 1) {
        parent->key_count++;
    } else {
        for (int j = parent->key_count; j > index + 1; j--) {
            parent->keys[j] = parent->keys[j - 1];
            parent->children[j + 1] = parent->children[j];
        }
    }
}

BPlusTreeNode* search(BPlusTree *tree, KeyType key, int *index) {
    BPlusTreeNode *node = tree->root;
    while (!node->leaf) {
        *index = 0;
        while (*index < node->key_count && node->keys[*index] < key) {
            (*index)++;
        }
        node = node->children[*index];
    }
    *index = -1;
    for (int i = 0; i < node->key_count; i++) {
        if (node->keys[i] == key) {
            *index = i;
            return node;
        }
    }
    return NULL;
}

void traverse(BPlusTreeNode *node, int depth) {
    for (int i = 0; i < node->key_count; i++) {
        printf("%*s%d ", depth * 2, "", node->keys[i]);
        if (!node->leaf) {
            traverse(node->children[i], depth + 1);
        }
    }
    if (!node->leaf && node->key_count > 0) {
        traverse(node->children[node->key_count], depth + 1);
    }
}

void free_tree(BPlusTree *tree) {
    free_node(tree->root);
    free(tree);
}

void free_node(BPlusTreeNode *node) {
    if (node != NULL) {
        if (!node->leaf) {
            for (int i = 0; i <= node->key_count; i++) {
                free_node(node->children[i]);
            }
        } else {
            free(node->values);
        }
        free(node);
    }
}

main.c

int main() {
    BPlusTree tree;
    tree.root = create_node(true);  // 创建一个空的根节点（叶子节点）

    // 插入一些键值对
    insert(&tree, 10, 100);
    insert(&tree, 20, 200);
    insert(&tree, 5, 50);
    insert(&tree, 15, 150);
    insert(&tree, 25, 250);

    // 查找键值并打印对应的值
    KeyType keysToFind[] = {5, 10, 15, 20, 25, 30};  // 30是一个不存在的键值
    for (int i = 0; i < sizeof(keysToFind) / sizeof(keysToFind[0]); i++) {
        ValueType *value = search(&tree, keysToFind[i]);
        if (value) {
            printf("Found key %d with value %d\n", keysToFind[i], *value);
        } else {
            printf("Key %d not found\n", keysToFind[i]);
        }
    }

    // 省略了释放内存的代码...
    return 0;
}

说明

  1. 数据结构：我们定义了B+树节点和B+树本身的数据结构，包括键值、子节点指针、链表连接指针、是否为叶子节点的标志以及叶子节点中的值数组。
  2. 辅助函数：创建新节点、分裂子节点和查找叶子节点的辅助函数实现，这些函数对于实现插入和查找操作是必要的。
  3. 插入操作：插入操作由于相对复杂。它需要处理节点的分裂，并可能递归地向上调整树的结构。
  4. 查找操作：查找操作沿着树向下搜索，直到找到目标键值或确定其不存在。在叶子节点中查找键值并返回对应的值。
  5. 应用实例：在main函数中，我们创建了一个B+树，插入了一些键值对，然后查找这些键值并打印对应的值。

请注意，由于篇幅限制和简化目的，省略了删除操作和一些错误处理。在实际应用中，需要实现完整的插入、删除和查找操作，并添加适当的错误处理。此外，这个实现中的B+树是内存中的数据结构，如果要在磁盘上实现B+树，还需要考虑磁盘IO操作和缓存管理。

总结

B+树通过将所有数据集中在叶子节点并连接叶子节点，优化了范围查询和顺序扫描的效率，特别适合数据库索引和文件系统等场景。其C语言实现需要考虑节点分裂、合并等复杂操作，但可以显著提高数据访问效率。


http://www.niftyadmin.cn/n/5845528.html

相关文章

【实用技能】如何借助3D文档控件Aspose.3D， 在Java中无缝制作 3D 球体

【实用技能】如何借助3D文档控件Aspose.3D， 在Java中无缝制作 3D 球体

概述 创建 3D 球体是 3D 图形设计的一个基本方面。无论您是在开发游戏、模拟还是可视化&#xff0c;无缝创建 3D 球体模型的能力都至关重要。Aspose.3D通过提供强大的 3D 图形 SDK 在各个行业中发挥着重要作用。它允许开发人员轻松创建、操作和转换 3D 模型。此 SDK 对于希望将…
阅读更多...
centos 7.x无法安装kong gateway 3.9X的解决方案

centos 7.x无法安装kong gateway 3.9X的解决方案

一、问题背景 笔者想在centos7.9上通过yum的方式安装kong gateway 3.9X&#xff0c;安装官网安装指导 curl -1sLf "https://packages.konghq.com/public/gateway-39/config.rpm.txt?distroel&codename$(rpm --eval %{rhel})" | sudo tee /etc/yum.repos.d/kong…
阅读更多...
自动化测试工具：selenium

自动化测试工具：selenium

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 Selenium是一个用于Web应用程序测试的工具。是一个开源的Web的自动化测试工具&#xff0c;最初是为网站自动化测试而开发的&#xff0c;类型像我们玩游戏用的按键…
阅读更多...
Java 读取 Word 模板文档并替换内容生成新文档

Java 读取 Word 模板文档并替换内容生成新文档

嘿&#xff0c;朋友们&#xff01;在实际开发中&#xff0c;经常会遇到需要根据 Word 模板生成特定文档的需求&#xff0c;比如合同、报告等。咱们可以使用 Apache POI 库来读取 Word 模板文档&#xff0c;然后替换其中的指定内容&#xff0c;最后生成新的文档。下面我就详细给…
阅读更多...
计算机毕业设计SparkStreaming+Kafka广告推荐系统 广告预测 广告数据分析可视化 广告爬虫 大数据毕业设计 深度学习 机器学习

计算机毕业设计SparkStreaming+Kafka广告推荐系统 广告预测 广告数据分析可视化 广告爬虫 大数据毕业设计 深度学习 机器学习

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…
阅读更多...
vue3学习四

vue3学习四

七 标签ref属性 设置标签ref属性&#xff0c;类似于设置标签id。 普通标签 <template name"test4"> <p ref"title" id"title" click"showinfo">VIEW4</p> <View3/><script lang"ts" setup>…
阅读更多...
F - Building Roads S

F - Building Roads S

Description Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms. Each of the N (1 ≤ N ≤ 1,000) …
阅读更多...
UnityShader学习笔记——多种光源

UnityShader学习笔记——多种光源

——内容源自唐老狮的shader课程 目录 1.光源类型 2.判断光源类型 2.1.在哪判断 2.2.如何判断 3.光照衰减 3.1.基本概念 3.2.unity中的光照衰减 3.3.光源空间变换矩阵 4.点光源衰减计算 5.聚光灯衰减计算 5.1.聚光灯的cookie&#xff08;灯光遮罩&#xff09; 5.2.聚…
阅读更多...
最新文章

Copyright @ 2022~2023