c语言实现b树

简介: 这篇文章介绍了B树的概念、特点和应用场景,并提供了一个C语言实现的B树数据结构示例代码,包括节点定义、创建新节点、分裂节点、插入关键字和打印B树等函数。

概述:B 树(B-tree)是一种自平衡的搜索树数据结构,广泛应用于数据库和文件系统等领域。它的设计旨在提供一种高效的插入、删除和查找操作,同时保持树的平衡,确保各个节点的深度相差不大。

B 树的特点包括:

  1. 平衡性: 所有叶子节点到根节点的路径长度相等,确保在查找、插入和删除等操作时,各个节点的访问次数相对均衡,提高了性能。

  2. 多路搜索: B 树每个内部节点可以有多个子节点,这是与二叉搜索树的主要区别。每个节点包含多个关键字和对应的子树,这样可以减少树的高度,提高检索效率。

  3. 节点存储多个关键字: 每个节点可以存储多个关键字,而不仅仅是一个。这样可以提高每个节点的利用率,减少磁盘 I/O 次数。

  4. 自调整: 在插入和删除操作时,B 树会自动调整其结构以保持平衡。这通过节点分裂和合并的方式来实现。

B 树的阶数(order)是一个重要的概念,它表示一个节点最多可以包含的子节点数(或关键字数)。通常,B 树的阶数会根据具体的使用场景进行调整,以满足性能和空间的需求。

B 树广泛应用于数据库系统中,作为索引结构,因为它能够高效地支持范围查询、插入和删除操作。同时,B 树也被用于文件系统,以加速文件的检索和访问。

完整代码:

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

// B 树的阶数
#define ORDER 3

// B 树节点结构
typedef struct BTreeNode {
    int leaf; // 是否是叶子节点
    int n;    // 当前关键字数量
    int keys[ORDER - 1]; // 关键字数组
    struct BTreeNode* child[ORDER]; // 子节点数组
} BTreeNode;

// 创建新节点
BTreeNode* createNode() {
    BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
    newNode->leaf = 1;
    newNode->n = 0;
    for (int i = 0; i < ORDER - 1; ++i) {
        newNode->keys[i] = 0;
    }
    for (int i = 0; i < ORDER; ++i) {
        newNode->child[i] = NULL;
    }
    return newNode;
}

// 分裂节点
void splitChild(BTreeNode* parent, int index, BTreeNode* child) {
    BTreeNode* newNode = createNode();
    newNode->leaf = child->leaf;
    newNode->n = ORDER / 2 - 1;

    // 将 child 中的一半关键字移动到 newNode 中
    for (int i = 0; i < ORDER / 2 - 1; ++i) {
        newNode->keys[i] = child->keys[i + ORDER / 2];
    }

    // 如果 child 不是叶子节点,将一半子节点移动到 newNode 中
    if (!child->leaf) {
        for (int i = 0; i < ORDER / 2; ++i) {
            newNode->child[i] = child->child[i + ORDER / 2];
            child->child[i + ORDER / 2] = NULL;
        }
    }

    // 调整 child 的关键字数量
    child->n = ORDER / 2 - 1;
    newNode->n = ORDER / 2 - 1;

    // 将 parent 中的一个关键字和 newNode 相关的子节点插入到 parent 中
    for (int i = parent->n; i > index; --i) {
        parent->keys[i] = parent->keys[i - 1];
        parent->child[i + 1] = parent->child[i];
    }
    parent->keys[index] = child->keys[ORDER / 2 - 1];
    parent->child[index + 1] = newNode;

    // 调整 parent 的关键字数量
    parent->n++;

    // 将 parent 中的一个关键字插入到 child 中
    child->keys[ORDER / 2 - 1] = 0;
    child->child[ORDER / 2] = NULL;
}

// 插入非满节点
void insertNonFull(BTreeNode** root, int key) {
    BTreeNode* node = *root;
    int i = node->n - 1;

    // 如果是叶子节点,直接插入
    if (node->leaf) {
        while (i >= 0 && key < node->keys[i]) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = key;
        node->n++;
    } else {
        // 如果是内部节点,找到要插入的子节点
        while (i >= 0 && key < node->keys[i]) {
            i--;
        }
        i++;

        // 如果子节点已满,先分裂再插入
        if (node->child[i]->n == ORDER - 1) {
            splitChild(node, i, node->child[i]);
            if (key > node->keys[i]) {
                i++;
            }
        }

        // 递归插入子节点
        insertNonFull(&(node->child[i]), key);
    }
}

// 插入关键字
void insert(BTreeNode** root, int key) {
    BTreeNode* node = *root;

    // 如果树为空,创建一个新节点作为根
    if (!node) {
        *root = createNode();
        (*root)->keys[0] = key;
        (*root)->n = 1;
        return;
    }

    // 如果根节点已满,先分裂再插入
    if (node->n == ORDER - 1) {
        BTreeNode* newRoot = createNode();
        newRoot->leaf = 0;
        newRoot->child[0] = *root;
        *root = newRoot;
        splitChild(newRoot, 0, node);
        insertNonFull(root, key);
    } else {
        insertNonFull(root, key);
    }
}



// 打印 B 树
void printBTree(BTreeNode* node, int level) {
    if (node) {
        printf("Level %d: ", level);
        for (int i = 0; i < node->n; ++i) {
            printf("%d ", node->keys[i]);
        }
        printf("\n");

        if (!node->leaf) {
            for (int i = 0; i <= node->n; ++i) {
                printBTree(node->child[i], level + 1);
            }
        }
    }
}

int main() {
    BTreeNode* root = NULL;

    // 插入一些关键字
    insert(&root, 3);
    insert(&root, 7);
    insert(&root, 2);
    insert(&root, 9);
    insert(&root, 1);
    insert(&root, 6);
    insert(&root, 4);
    insert(&root, 5);
    insert(&root, 8);

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

    return 0;
}

首先定义了B树的阶数ORDER为3,即每个节点最多可以有3个子节点。然后定义了一个B树节点的结构体,包含以下成员:

  • leaf:表示该节点是否为叶子节点,如果是叶子节点则为1,否则为0。
  • n:表示当前节点中关键字的数量。
  • keys:关键字数组,用于存储节点中的关键字。
  • child:子节点数组,用于存储指向子节点的指针。

接下来实现了创建新节点的函数createNode(),用于分配内存并初始化节点的成员变量。

然后实现了分裂节点的函数splitChild(),用于将一个节点分裂成两个节点。分裂过程包括将原节点的一半关键字移动到新节点中,并将原节点的一半子节点移动到新节点中。同时调整原节点的关键字数量和新节点的关键字数量。最后将原节点中的一个关键字和与新节点相关的子节点插入到原节点中,并调整原节点的关键字数量。

接着实现了插入非满节点的函数insertNonFull(),用于在非满节点中插入关键字。如果节点是叶子节点,则直接插入关键字;如果节点是内部节点,则找到要插入的子节点,如果子节点已满,则先分裂再插入。然后递归插入子节点。

最后实现了插入关键字的函数insert(),用于向B树中插入关键字。如果树为空,则创建一个新节点作为根;如果根节点已满,则先分裂再插入。然后调用insertNonFull()函数插入关键字。

最后实现了打印B树的函数printBTree(),用于按层次遍历的方式打印B树的结构。

在main()函数中,创建了一个空的根节点root,然后插入了一些关键字,并调用printBTree()函数打印B树的结构。

目录
相关文章
|
6月前
|
存储 分布式数据库 数据库
C语言 B树的分析与实现
本文主要说明了B树的概念、应用以及如何用C语言实现B树。
78 1
|
28天前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
31 3
|
19天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余,其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值,并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出,支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
32 10
|
12天前
|
存储 算法 程序员
C语言:库函数
C语言的库函数是预定义的函数,用于执行常见的编程任务,如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作,提高开发效率。C标准库提供了丰富的函数,满足各种需求。
|
17天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件,并通过求阶乘、打印整数每一位和求斐波那契数等实例,展示了递归的应用。递归的核心在于将大问题分解为小问题,但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点,提醒读者在实际编程中合理使用递归。
43 7
|
17天前
|
存储 编译器 程序员
【c语言】函数
本文介绍了C语言中函数的基本概念,包括库函数和自定义函数的定义、使用及示例。库函数如`printf`和`scanf`,通过包含相应的头文件即可使用。自定义函数需指定返回类型、函数名、形式参数等。文中还探讨了函数的调用、形参与实参的区别、return语句的用法、函数嵌套调用、链式访问以及static关键字对变量和函数的影响,强调了static如何改变变量的生命周期和作用域,以及函数的可见性。
25 4
|
22天前
|
存储 编译器 C语言
C语言函数的定义与函数的声明的区别
C语言中,函数的定义包含函数的实现,即具体执行的代码块;而函数的声明仅描述函数的名称、返回类型和参数列表,用于告知编译器函数的存在,但不包含实现细节。声明通常放在头文件中,定义则在源文件中。
|
29天前
|
C语言
c语言回顾-函数递归(上)
c语言回顾-函数递归(上)
31 2
|
30天前
|
Java 编译器 C语言
【一步一步了解Java系列】:Java中的方法对标C语言中的函数
【一步一步了解Java系列】:Java中的方法对标C语言中的函数
19 3
|
1月前
|
存储 程序员 编译器
C语言——动态内存管理与内存操作函数
C语言——动态内存管理与内存操作函数