【408考点之数据结构】B树和B+树

B树和B+树

在大规模数据存储和检索中，B树和B+树是两种广泛使用的数据结构。它们被设计用来高效地管理数据，使得插入、删除和查找操作都能在对数时间内完成。以下是对这两种数据结构的详细介绍。

1. B树（B-Tree）

定义：B树是一种自平衡的多路查找树，通常用于数据库和文件系统中。B树的所有叶子节点位于同一层，且内部节点可以包含多个关键字和子树指针。

性质：

每个节点包含关键字的数量范围为 ( [t-1, 2t-1] )，其中 ( t ) 是B树的阶数。
除根节点外，每个内部节点至少有 ( t ) 个子节点。
所有叶子节点位于同一层。
插入和删除操作需要维护树的平衡。

实现：

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

// B树节点结构
typedef struct BTreeNode {
    int *keys;  // 关键字数组
    int t;      // 最小度数
    struct BTreeNode **C; // 子树指针数组
    int n;      // 当前关键字数量
    int leaf;   // 叶子节点标志
} BTreeNode;

// 创建新的B树节点
BTreeNode* createNode(int t, int leaf) {
    BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
    node->t = t;
    node->leaf = leaf;
    node->keys = (int*)malloc(sizeof(int) * (2 * t - 1));
    node->C = (BTreeNode**)malloc(sizeof(BTreeNode*) * (2 * t));
    node->n = 0;
    return node;
}

// B树插入操作略
// 示例代码略

2. B+树（B+ Tree）

定义：B+树是B树的变种，具有所有叶子节点按顺序链接的特性，使得范围查找更加高效。所有数据都存储在叶子节点中，内部节点只存储索引。

性质：

内部节点只存储索引，不存储实际数据。
所有数据都存储在叶子节点中，并通过链表链接。
插入和删除操作会影响到索引节点，但数据节点的顺序保持不变。

实现：

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

// B+树节点结构
typedef struct BPlusTreeNode {
    int *keys;  // 关键字数组
    int t;      // 最小度数
    struct BPlusTreeNode **C; // 子树指针数组
    struct BPlusTreeNode *next; // 下一个叶子节点指针
    int n;      // 当前关键字数量
    int leaf;   // 叶子节点标志
} BPlusTreeNode;

// 创建新的B+树节点
BPlusTreeNode* createBPlusNode(int t, int leaf) {
    BPlusTreeNode* node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode));
    node->t = t;
    node->leaf = leaf;
    node->keys = (int*)malloc(sizeof(int) * (2 * t - 1));
    node->C = (BPlusTreeNode**)malloc(sizeof(BPlusTreeNode*) * (2 * t));
    node->next = NULL;
    node->n = 0;
    return node;
}

// B+树插入操作略
// 示例代码略

B树和 B+树的比较

结构差异：
- B树：内部节点和叶子节点都存储数据。
- B+树：内部节点只存储索引，所有数据都在叶子节点中，且叶子节点通过链表连接。
查找效率：
- B树：查找路径较短，但每个节点的访问次数较多。
- B+树：查找路径较长，但叶子节点间的顺序访问更高效，适合范围查找。
插入和删除：
- B树：插入和删除可能涉及到内部节点和叶子节点的调整。
- B+树：插入和删除主要影响叶子节点，内部节点只需调整索引，且顺序访问更友好。

应用场景

数据库索引：B树和B+树广泛应用于数据库索引结构中，提供高效的数据存储和查找方式。
文件系统：文件系统中使用B树和B+树管理文件目录和索引，提高文件检索效率。
内存管理：操作系统中的内存管理也可以利用B树和B+树进行页表管理和快速查找。

示例代码

以下是一个简单的B树插入操作的示例代码：

// B树插入操作示例代码
#include <stdio.h>
#include <stdlib.h>

typedef struct BTreeNode {
    int *keys; 
    int t; 
    struct BTreeNode **C; 
    int n; 
    int leaf; 
} BTreeNode;

BTreeNode* createNode(int t, int leaf) {
    BTreeNode* node = (BTreeNode*)malloc(sizeof(BTreeNode));
    node->t = t;
    node->leaf = leaf;
    node->keys = (int*)malloc(sizeof(int) * (2 * t - 1));
    node->C = (BTreeNode**)malloc(sizeof(BTreeNode*) * (2 * t));
    node->n = 0;
    return node;
}

void insertNonFull(BTreeNode* node, int k) {
    int i = node->n - 1;

    if (node->leaf) {
        while (i >= 0 && node->keys[i] > k) {
            node->keys[i + 1] = node->keys[i];
            i--;
        }
        node->keys[i + 1] = k;
        node->n += 1;
    } else {
        while (i >= 0 && node->keys[i] > k)
            i--;

        if (node->C[i + 1]->n == 2 * node->t - 1) {
            splitChild(node, i + 1, node->C[i + 1]);

            if (node->keys[i + 1] < k)
                i++;
        }
        insertNonFull(node->C[i + 1], k);
    }
}

void splitChild(BTreeNode* parent, int i, BTreeNode* y) {
    int t = y->t;
    BTreeNode* z = createNode(t, y->leaf);
    z->n = t - 1;

    for (int j = 0; j < t - 1; j++)
        z->keys[j] = y->keys[j + t];

    if (!y->leaf) {
        for (int j = 0; j < t; j++)
            z->C[j] = y->C[j + t];
    }

    y->n = t - 1;

    for (int j = parent->n; j >= i + 1; j--)
        parent->C[j + 1] = parent->C[j];

    parent->C[i + 1] = z;

    for (int j = parent->n - 1; j >= i; j--)
        parent->keys[j + 1] = parent->keys[j];

    parent->keys[i] = y->keys[t - 1];
    parent->n += 1;
}

void traverse(BTreeNode* root) {
    int i;
    for (i = 0; i < root->n; i++) {
        if (!root->leaf)
            traverse(root->C[i]);
        printf(" %d", root->keys[i]);
    }
    if (!root->leaf)
        traverse(root->C[i]);
}

int main() {
    int t = 3;
    BTreeNode* root = createNode(t, 1);
    insertNonFull(root, 10);
    insertNonFull(root, 20);
    insertNonFull(root, 5);
    insertNonFull(root, 6);
    insertNonFull(root, 12);
    insertNonFull(root, 30);
    insertNonFull(root, 7);
    insertNonFull(root, 17);

    printf("Traversal of the constructed tree is ");
    traverse(root);
    printf("\n");

    return 0;
}