天津市网站建设_网站建设公司_VPS_seo优化

头文件

#pragma once #include <stdio.h> #include <iostream> #include <stdlib.h> #include <string.h> #include <assert.h> using namespace std; #define M 4 // B+树的阶数 // B+树节点结构 typedef struct BPlusTreeNode { int key_num; // 当前关键字数量 int keys[M]; // 关键字数组 bool is_leaf; // 是否为叶子节点 struct BPlusTreeNode* parent; // 父节点指针 struct BPlusTreeNode* children[M + 1]; // 子节点指针数组 struct BPlusTreeNode* next; // 叶子节点的下一个兄弟（链表连接） void** data_ptrs[M]; // 叶子节点的数据指针数组 } BPlusTreeNode; // B+树结构 typedef struct BPlusTree { BPlusTreeNode* root; // 根节点 BPlusTreeNode* first_leaf; // 第一个叶子节点（用于范围查询） int size; // 树中关键字总数 } BPlusTree; // 查找结果结构 typedef struct SearchResult { BPlusTreeNode* node; // 找到的节点 int index; // 关键字位置 bool found; // 是否找到 } SearchResult; // 工具函数声明 // 创建查找结果 SearchResult* CreateSearchResult(); //创建节点 BPlusTreeNode* CreateNode(bool is_leaf); //查找关键字位置 int FindKeyIndex(BPlusTreeNode* node, int key); // 主要操作函数声明 //初始化B+树 void InitBPlusTree(BPlusTree* tree); //查找 SearchResult* Search(BPlusTree* tree, int key); //插入 bool Insert(BPlusTree* tree, int key, void* data); // 删除 bool Delete(BPlusTree* tree, int key); //显示 void Display(BPlusTree* tree, bool show_details = false); //范围查询 void RangeQuery(BPlusTree* tree, int start_key, int end_key); //销毁树 void DestroyTree(BPlusTree* tree);

源文件

#include "b+树.h" // 创建查找结果 SearchResult* CreateSearchResult() { SearchResult* result = (SearchResult*)malloc(sizeof(SearchResult)); if (!result) { perror("Failed to allocate search result"); exit(EXIT_FAILURE); } result->node = nullptr; result->index = -1; result->found = false; return result; } //创建节点 BPlusTreeNode* CreateNode(bool is_leaf) { BPlusTreeNode* node = (BPlusTreeNode*)malloc(sizeof(BPlusTreeNode)); if (!node) { perror("Failed to allocate node"); exit(EXIT_FAILURE); } node->key_num = 0; node->is_leaf = is_leaf; node->parent = nullptr; node->next = nullptr; memset(node->keys, 0, sizeof(node->keys)); // 初始化指针数组 for (int i = 0; i <= M; i++) { node->children[i] = nullptr; if (is_leaf && i < M) { node->data_ptrs[i] = nullptr; } } return node; } //查找关键字位置 int FindKeyIndex(BPlusTreeNode* node, int key) { int left = 0; int right = node->key_num - 1; while (left <= right) { int mid = left + (right - left) / 2; if (node->keys[mid] == key) { return mid; } else if (node->keys[mid] < key) { left = mid + 1; } else { right = mid - 1; } } return left; // 返回应该插入的位置 } // ==================== 主要操作实现 ==================== //初始化B+树 void InitBPlusTree(BPlusTree* tree) { assert(tree != nullptr); tree->root = nullptr; tree->first_leaf = nullptr; tree->size = 0; } //查找 SearchResult* Search(BPlusTree* tree, int key) { assert(tree != nullptr); SearchResult* result = CreateSearchResult(); if (tree->root == nullptr) { return result; } BPlusTreeNode* current = tree->root; // 查找合适的叶子节点 while (!current->is_leaf) { int pos = FindKeyIndex(current, key); current = current->children[pos]; } // 在叶子节点中查找关键字 int pos = FindKeyIndex(current, key); result->node = current; result->index = pos; if (pos < current->key_num && current->keys[pos] == key) { result->found = true; } return result; } //插入 bool Insert(BPlusTree* tree, int key, void* data) { assert(tree != nullptr); // 空树情况 if (tree->root == nullptr) { BPlusTreeNode* new_node = CreateNode(true); new_node->keys[0] = key; new_node->data_ptrs[0] = data; new_node->key_num = 1; tree->root = new_node; tree->first_leaf = new_node; tree->size = 1; return true; } // 查找插入位置 SearchResult* result = Search(tree, key); if (result->found) { // 关键字已存在，更新数据 result->node->data_ptrs[result->index] = data; free(result); return true; } BPlusTreeNode* leaf = result->node; int pos = result->index; free(result); // 在叶子节点中插入 for (int i = leaf->key_num; i > pos; i--) { leaf->keys[i] = leaf->keys[i - 1]; leaf->data_ptrs[i] = leaf->data_ptrs[i - 1]; } leaf->keys[pos] = key; leaf->data_ptrs[pos] = data; leaf->key_num++; tree->size++; // 检查是否需要分裂 if (leaf->key_num == M) { InsertAdjust(tree, leaf); } return true; } // 内部函数：分裂节点 BPlusTreeNode* SplitNode(BPlusTree* tree, BPlusTreeNode* node) { int split_pos = M / 2; bool is_leaf = node->is_leaf; // 创建新节点 BPlusTreeNode* new_node = CreateNode(is_leaf); new_node->parent = node->parent; if (is_leaf) { // 叶子节点分裂 for (int i = split_pos; i < M; i++) { int j = i - split_pos; new_node->keys[j] = node->keys[i]; new_node->data_ptrs[j] = node->data_ptrs[i]; new_node->key_num++; // 清空原节点 node->keys[i] = 0; node->data_ptrs[i] = nullptr; } node->key_num = split_pos; // 维护叶子链表 new_node->next = node->next; node->next = new_node; } else { // 内部节点分裂 for (int i = split_pos + 1; i < M; i++) { int j = i - (split_pos + 1); new_node->keys[j] = node->keys[i]; new_node->children[j] = node->children[i]; if (node->children[i]) { node->children[i]->parent = new_node; } new_node->key_num++; // 清空原节点 node->keys[i] = 0; node->children[i] = nullptr; } new_node->children[new_node->key_num] = node->children[M]; if (node->children[M]) { node->children[M]->parent = new_node; } node->children[M] = nullptr; // 更新原节点关键字数 node->key_num = split_pos; } return new_node; } // 插入调整（处理上溢） void InsertAdjust(BPlusTree* tree, BPlusTreeNode* node) { while (node && node->key_num == M) { int split_pos = M / 2; int promoted_key; BPlusTreeNode* new_node; if (node->is_leaf) { // 叶子节点分裂 new_node = SplitNode(tree, node); promoted_key = new_node->keys[0]; // 复制第一个关键字到父节点 } else { // 内部节点分裂 promoted_key = node->keys[split_pos]; new_node = SplitNode(tree, node); } if (node->parent == nullptr) { // 创建新的根节点 BPlusTreeNode* new_root = CreateNode(false); new_root->keys[0] = promoted_key; new_root->key_num = 1; new_root->children[0] = node; new_root->children[1] = new_node; node->parent = new_root; new_node->parent = new_root; tree->root = new_root; break; } else { // 插入到父节点 BPlusTreeNode* parent = node->parent; int pos = FindKeyIndex(parent, promoted_key); // 移动关键字和指针 for (int i = parent->key_num; i > pos; i--) { parent->keys[i] = parent->keys[i - 1]; parent->children[i + 1] = parent->children[i]; } parent->keys[pos] = promoted_key; parent->children[pos] = node; parent->children[pos + 1] = new_node; parent->key_num++; // 继续向上调整 node = parent; } } } bool Delete(BPlusTree* tree, int key) { assert(tree != nullptr); if (tree->root == nullptr) { return false; } SearchResult* result = Search(tree, key); if (!result->found) { free(result); return false; } BPlusTreeNode* leaf = result->node; int pos = result->index; free(result); // 从叶子节点删除 for (int i = pos; i < leaf->key_num - 1; i++) { leaf->keys[i] = leaf->keys[i + 1]; leaf->data_ptrs[i] = leaf->data_ptrs[i + 1]; } leaf->key_num--; tree->size--; // 如果是第一个关键字被删除，需要更新父节点 if (pos == 0 && leaf->parent) { BPlusTreeNode* parent = leaf->parent; int parent_pos = FindKeyIndex(parent, key); if (parent_pos < parent->key_num && parent->keys[parent_pos] == key) { parent->keys[parent_pos] = leaf->keys[0]; } } // 检查下溢 if (leaf->key_num < (M + 1) / 2 - 1) { DeleteAdjust(tree, leaf); } return true; } // 删除调整（处理下溢） void DeleteAdjust(BPlusTree* tree, BPlusTreeNode* node) { if (node == tree->root) { // 根节点特殊处理 if (node->key_num == 0 && !node->is_leaf) { tree->root = node->children[0]; if (tree->root) { tree->root->parent = nullptr; } free(node); } return; } // 计算最小关键字数 int min_keys = (M + 1) / 2 - 1; if (node->key_num >= min_keys) { return; } BPlusTreeNode* parent = node->parent; int index = 0; while (parent->children[index] != node) { index++; } // 尝试从左兄弟借 if (index > 0) { BPlusTreeNode* left_sibling = parent->children[index - 1]; if (left_sibling->key_num > min_keys) { // 从左兄弟借一个元素 if (node->is_leaf) { // 叶子节点借用 for (int i = node->key_num; i > 0; i--) { node->keys[i] = node->keys[i - 1]; node->data_ptrs[i] = node->data_ptrs[i - 1]; } node->keys[0] = left_sibling->keys[left_sibling->key_num - 1]; node->data_ptrs[0] = left_sibling->data_ptrs[left_sibling->key_num - 1]; node->key_num++; left_sibling->key_num--; // 更新父节点关键字 parent->keys[index - 1] = node->keys[0]; } else { // 内部节点借用 // 将父节点关键字下移 for (int i = node->key_num; i > 0; i--) { node->keys[i] = node->keys[i - 1]; } for (int i = node->key_num + 1; i > 0; i--) { node->children[i] = node->children[i - 1]; } node->keys[0] = parent->keys[index - 1]; node->children[0] = left_sibling->children[left_sibling->key_num]; if (node->children[0]) { node->children[0]->parent = node; } node->key_num++; // 将左兄弟最后一个关键字上移到父节点 parent->keys[index - 1] = left_sibling->keys[left_sibling->key_num - 1]; left_sibling->key_num--; } return; } } // 尝试从右兄弟借 if (index < parent->key_num) { BPlusTreeNode* right_sibling = parent->children[index + 1]; if (right_sibling->key_num > min_keys) { // 从右兄弟借一个元素 if (node->is_leaf) { // 叶子节点借用 node->keys[node->key_num] = right_sibling->keys[0]; node->data_ptrs[node->key_num] = right_sibling->data_ptrs[0]; node->key_num++; // 移动右兄弟的元素 for (int i = 0; i < right_sibling->key_num - 1; i++) { right_sibling->keys[i] = right_sibling->keys[i + 1]; right_sibling->data_ptrs[i] = right_sibling->data_ptrs[i + 1]; } right_sibling->key_num--; // 更新父节点关键字 parent->keys[index] = right_sibling->keys[0]; } else { // 内部节点借用 node->keys[node->key_num] = parent->keys[index]; node->children[node->key_num + 1] = right_sibling->children[0]; if (node->children[node->key_num + 1]) { node->children[node->key_num + 1]->parent = node; } node->key_num++; // 将右兄弟第一个关键字上移到父节点 parent->keys[index] = right_sibling->keys[0]; // 移动右兄弟的元素 for (int i = 0; i < right_sibling->key_num - 1; i++) { right_sibling->keys[i] = right_sibling->keys[i + 1]; } for (int i = 0; i < right_sibling->key_num; i++) { right_sibling->children[i] = right_sibling->children[i + 1]; } right_sibling->key_num--; } return; } } // 合并操作 if (index > 0) { // 与左兄弟合并 BPlusTreeNode* left_sibling = parent->children[index - 1]; if (node->is_leaf) { // 叶子节点合并 for (int i = 0; i < node->key_num; i++) { left_sibling->keys[left_sibling->key_num + i] = node->keys[i]; left_sibling->data_ptrs[left_sibling->key_num + i] = node->data_ptrs[i]; } left_sibling->key_num += node->key_num; left_sibling->next = node->next; // 删除父节点关键字 for (int i = index - 1; i < parent->key_num - 1; i++) { parent->keys[i] = parent->keys[i + 1]; parent->children[i + 1] = parent->children[i + 2]; } parent->key_num--; free(node); } else { // 内部节点合并 left_sibling->keys[left_sibling->key_num] = parent->keys[index - 1]; left_sibling->key_num++; for (int i = 0; i < node->key_num; i++) { left_sibling->keys[left_sibling->key_num + i] = node->keys[i]; left_sibling->children[left_sibling->key_num + i] = node->children[i]; if (left_sibling->children[left_sibling->key_num + i]) { left_sibling->children[left_sibling->key_num + i]->parent = left_sibling; } } left_sibling->children[left_sibling->key_num + node->key_num] = node->children[node->key_num]; if (left_sibling->children[left_sibling->key_num + node->key_num]) { left_sibling->children[left_sibling->key_num + node->key_num]->parent = left_sibling; } left_sibling->key_num += node->key_num; // 删除父节点关键字 for (int i = index - 1; i < parent->key_num - 1; i++) { parent->keys[i] = parent->keys[i + 1]; parent->children[i + 1] = parent->children[i + 2]; } parent->key_num--; free(node); } } else { // 与右兄弟合并 BPlusTreeNode* right_sibling = parent->children[index + 1]; if (node->is_leaf) { // 叶子节点合并 for (int i = 0; i < right_sibling->key_num; i++) { node->keys[node->key_num + i] = right_sibling->keys[i]; node->data_ptrs[node->key_num + i] = right_sibling->data_ptrs[i]; } node->key_num += right_sibling->key_num; node->next = right_sibling->next; // 删除父节点关键字 for (int i = index; i < parent->key_num - 1; i++) { parent->keys[i] = parent->keys[i + 1]; parent->children[i + 1] = parent->children[i + 2]; } parent->key_num--; free(right_sibling); } else { // 内部节点合并 node->keys[node->key_num] = parent->keys[index]; node->key_num++; for (int i = 0; i < right_sibling->key_num; i++) { node->keys[node->key_num + i] = right_sibling->keys[i]; node->children[node->key_num + i] = right_sibling->children[i]; if (node->children[node->key_num + i]) { node->children[node->key_num + i]->parent = node; } } node->children[node->key_num + right_sibling->key_num] = right_sibling->children[right_sibling->key_num]; if (node->children[node->key_num + right_sibling->key_num]) { node->children[node->key_num + right_sibling->key_num]->parent = node; } node->key_num += right_sibling->key_num; // 删除父节点关键字 for (int i = index; i < parent->key_num - 1; i++) { parent->keys[i] = parent->keys[i + 1]; parent->children[i + 1] = parent->children[i + 2]; } parent->key_num--; free(right_sibling); } } // 递归向上调整 DeleteAdjust(tree, parent); } // ==================== 显示和遍历函数 ==================== //显示 void Display(BPlusTree* tree, bool show_details) { assert(tree != nullptr); printf("B+ Tree (size: %d):\n", tree->size); DisplayNode(tree->root, 0, show_details); printf("\n"); } void DisplayNode(BPlusTreeNode* node, int level, bool show_details) { if (node == nullptr) return; // 打印缩进 for (int i = 0; i < level; i++) { printf(" "); } printf("["); for (int i = 0; i < node->key_num; i++) { printf("%d", node->keys[i]); if (i < node->key_num - 1) printf(", "); } printf("]"); if (show_details) { printf(" (keys=%d, %s)", node->key_num,node->is_leaf ? "leaf" : "internal"); if (node->is_leaf && node->next) { printf(" -> next"); } } printf("\n"); if (!node->is_leaf) { for (int i = 0; i <= node->key_num; i++) { DisplayNode(node->children[i], level + 1, show_details); } } } //范围查询 void RangeQuery(BPlusTree* tree, int start_key, int end_key) { assert(tree != nullptr); if (tree->root == nullptr) { printf("Tree is empty.\n"); return; } // 查找起始关键字 SearchResult* result = Search(tree, start_key); BPlusTreeNode* current = result->node; int pos = result->index; free(result); printf("Range query [%d, %d]: ", start_key, end_key); bool found_any = false; while (current) { while (pos < current->key_num) { if (current->keys[pos] > end_key) { printf("\n"); return; } printf("%d ", current->keys[pos]); found_any = true; pos++; } current = current->next; pos = 0; } if (!found_any) { printf("No keys found in range."); } printf("\n"); } //销毁树 void DestroyTree(BPlusTree* tree) { assert(tree != nullptr); DestroyNode(tree->root); tree->root = nullptr; tree->first_leaf = nullptr; tree->size = 0; } void DestroyNode(BPlusTreeNode* node) { if (node == nullptr) return; if (!node->is_leaf) { for (int i = 0; i <= node->key_num; i++) { DestroyNode(node->children[i]); } } free(node); }