B树介绍
B树（B-Tree）是一种自平衡的树结构，它维持数据的有序性，并且允许搜索、顺序访问、插入和删除操作都在对数时间内完成。B树是为磁盘和其他直接访问的辅助存储设备而设计的，主要用于数据库和文件系统中。以下是B树的一些主要特点：
B树的特性：
- 节点最大和最小孩子数：一个B树的节点可能有许多孩子，从几个到数千个。每个节点除了叶子节点外，都有至少两个孩子。
- 节点中的键（Key）：每个节点包含一定数量的键。这些键按照升序排列，并分隔开节点指针，使得每个键都是一个子树的分隔键。
- 分支因子：B树的每个节点最多包含的子节点数称为分支因子，通常用字母m表示。一个节点的键的数量比它孩子的数量少1，即一个节点包含最多m-1个键。
- 平衡性：B树是平衡的，所有叶子节点都在同一层。
- 填充因子：为了保持树的平衡，B树在插入和删除操作时会进行节点的分裂和合并。节点的分裂和合并会确保树的高度尽可能低。
B树的操作：
- 搜索：从根节点开始，根据要查找的键与节点的键进行比较，决定是继续在左子树还是右子树中搜索。
- 插入：在找到合适的叶子节点后，将新键插入该节点。如果节点中的键的数量超过了m-1，则节点会分裂成两个节点，并将中间的键提升到父节点。
- 删除：找到包含要删除键的节点，并从节点中移除该键。如果删除后节点中的键的数量少于要求的最小数量，则需要重新分配或合并节点。
B树的应用：
- 数据库索引：B树由于其高效的磁盘I/O操作，常被用作数据库系统的索引结构。
- 文件系统：许多文件系统使用B树或其变种（如B+树）来存储文件系统的元数据。
B树之所以高效，是因为它减少了磁盘I/O操作的次数。在数据库和文件系统中，磁盘I/O是非常耗时的操作，因此减少磁盘访问次数可以显著提高性能。
以下是一个简单的B树示例，我们将通过一个具体的例子来展示B树的搜索、插入、和删除操作。假设我们有一个B树，其分支因子为4，这意味着每个节点最多可以有3个键和4个子节点。
案例
结构理解
初始状态
首先，我们从一个空的B树开始，然后逐步执行插入操作。
空B树
插入操作
现在，我们将以下键按顺序插入到B树中：10, 20, 5, 6, 12, 30, 7, 17。
- 插入10
10
- 插入20
10 20
- 插入5
5 10 20
- 插入6
5 6 10 20
- 插入12
5 6 10 12 20
- 插入30
因为节点已满，我们需要分裂节点：
6
/ \
5 10
/ \
12 20
\
30
- 插入7
6
/ \
5 10
/ \
7 12
\
20
/
30
- 插入17
因为节点已满，我们需要再次分裂节点：
10
/ \
6 20
/ \ / \
5 7 12 30
\
17
搜索操作
假设我们要搜索键值为17的节点。
- 从根节点10开始，因为17 > 10，所以我们搜索右子树。
- 在节点20的左子树中，因为17 < 20，我们搜索节点12。
- 在节点12的右子树中，我们找到了键17。
删除操作
现在，假设我们要删除键值为7的节点。
- 找到键7所在的节点，它是节点6的左孩子。
- 删除键7。
- 因为删除后节点6仍然有至少2个键，所以不需要进行节点合并或重新分配。
删除后的B树如下：
10
/ \
6 20
/ \ / \
5 7 12 30
\
17
需要注意的是删除操作可能会导致节点的合并或重新分配，但在本例中，我们假设删除操作不会触发这些情况。如果删除操作导致节点键的数量少于最小要求，那么需要从兄弟节点借键或与兄弟节点合并，以保持B树的平衡。
C代码实现
#include <stdio.h>
#include <stdlib.h>
#define MAX_KEYS 3
#define MIN_KEYS 2
typedef struct BTreeNode {
int keys[MAX_KEYS + 1];
struct BTreeNode *child[MAX_KEYS + 2];
int num_keys;
int is_leaf;
} BTreeNode;
BTreeNode *create_node(int is_leaf) {
BTreeNode *node = (BTreeNode *)malloc(sizeof(BTreeNode));
node->num_keys = 0;
node->is_leaf = is_leaf;
for (int i = 0; i <= MAX_KEYS; i++) {
node->keys[i] = 0;
node->child[i] = NULL;
}
node->child[MAX_KEYS + 1] = NULL;
return node;
}
void insert(BTreeNode **root, int key) {
if (*root == NULL) {
*root = create_node(1);
(*root)->keys[0] = key;
(*root)->num_keys = 1;
return;
}
if ((*root)->num_keys == MAX_KEYS) {
BTreeNode *new_root = create_node(0);
new_root->child[0] = *root;
split_child(new_root, 0);
insert_non_full(new_root, key);
*root = new_root;
} else {
insert_non_full(*root, key);
}
}
void insert_non_full(BTreeNode *node, int key) {
int i = node->num_keys - 1;
if (node->is_leaf) {
while (i >= 0 && node->keys[i] > key) {
node->keys[i + 1] = node->keys[i];
i--;
}
node->keys[i + 1] = key;
node->num_keys++;
} else {
while (i >= 0 && node->keys[i] > key) i--;
i++;
if (node->child[i]->num_keys == MAX_KEYS) {
split_child(node, i);
if (key > node->keys[i]) i++;
}
insert_non_full(node->child[i], key);
}
}
void split_child(BTreeNode *node, int i) {
BTreeNode *z = create_node(node->child[i]->is_leaf);
z->num_keys = MIN_KEYS;
for (int j = 0; j < MIN_KEYS; j++) {
z->keys[j] = node->child[i]->keys[j + MIN_KEYS + 1];
}
if (!node->child[i]->is_leaf) {
for (int j = 0; j < MIN_KEYS + 1; j++) {
z->child[j] = node->child[i]->child[j + MIN_KEYS + 1];
}
}
node->child[i]->num_keys = MIN_KEYS;
for (int j = node->num_keys; j >= i + 1; j--) {
node->child[j + 1] = node->child[j];
}
node->child[i + 1] = z;
for (int j = node->num_keys - 1; j >= i; j--) {
node->keys[j + 1] = node->keys[j];
}
node->keys[i] = node->child[i]->keys[MIN_KEYS];
node->num_keys++;
}
BTreeNode *search(BTreeNode *root, int key) {
int i = 0;
while (i < root->num_keys && key > root->keys[i]) {
i++;
}
if (i < root->num_keys && key == root->keys[i]) {
return root;
}
if (root->is_leaf) {
return NULL;
} else {
return search(root->child[i], key);
}
}
void delete(BTreeNode **root, int key) {
if (*root == NULL) return;
int i = 0;
while (i < (*root)->num_keys && key > (*root)->keys[i]) {
i++;
}
if (i < (*root)->num_keys && key == (*root)->keys[i]) {
if ((*root)->is_leaf) {
for (int j = i; j < (*root)->num_keys - 1; j++) {
(*root)->keys[j] = (*root)->keys[j + 1];
}
(*root)->num_keys--;
if ((*root)->num_keys == 0) {
free(*root);
*root = NULL;
}
} else {
}
} else {
if ((*root)->is_leaf) {
return; // Key not found in the tree
}
// The key might be in the child
BTreeNode *child = (*root)->child[i];
if (child->num_keys == MIN_KEYS) {
// 如果删除操作导致节点键的数量少于最小要求，那么需要从兄弟节点借键或与兄弟节点合并，以保持B树的平衡
} else {
delete(&child, key);
}
}
}
void print_tree(BTreeNode *node, int level) {
if (node != NULL) {
for (int i = 0; i < node->num_keys; i++) {
print_tree(node->child[i], level + 1);
for (int j = 0; j < level; j++) printf(" ");
printf("%d\n", node->keys[i]);
}
print_tree(node->child[node->num_keys], level + 1);
}
}
int main() {
BTreeNode *root = NULL;
int keys_to_insert[] = {10, 20, 5, 6, 12, 30, 7, 17};
int num_keys = sizeof(keys_to_insert) / sizeof(keys_to_insert[0]);
for (int i = 0; i < num_keys; i++) {
insert(&root, keys_to_insert[i]);
}
printf("B-Tree after insertions:\n");
print_tree(root, 0);
BTreeNode *search_result = search(root, 17);
if (search_result != NULL) {
printf("Key 17 found in BTree.\n");
} else {
printf("Key 17 not found in BTree.\n");
}
delete(&root, 7);
printf("B-Tree after deleting 7:\n");
print_tree(root, 0);
return 0;
}
这个程序展示了如何创建一个B树，插入一系列键，搜索一个键，并简单地删除一个键。删除操作只处理了叶子节点的情况，并没有处理节点合并或重新分配的复杂情况。打印函数print_tree用于可视化地展示B树的结构。
标签：node,keys,int,child,数据结构,root,节点 From： https://blog.csdn.net/Young_Pro/article/details/140351433