当前位置：首页 > web >正文

数据结构---B树

web 2025/6/17 16:21:33

B树

B树是一种自平衡的多路查找树，广泛应用于数据库管理系统和文件系统中，用于高效地存储和检索大量数据。它是一种特殊的多叉树结构，具有许多独特的性质和优势。

一、B树的定义

B树是一种平衡的多路查找树，它满足以下性质：

每个节点最多有 *M* 个子节点（其中 M 是B树的阶数）。
每个节点至少有 ⌈*M*/2⌉ 个子节点（除了根节点，根节点至少有2个子节点，除非它是叶子节点）。
所有叶子节点都在同一层，即B树是平衡的。
每个节点最多有 *M*−1 个键值。
每个节点的键值按升序排列。
根节点至少有2个子节点（除非它是叶子节点）。

二、B树的特点

平衡性：
- B树的所有叶子节点都在同一层，这保证了查找、插入和删除操作的时间复杂度均为 O(logn)，其中 n 是树中节点的数量。
高效性：
- B树的每个节点可以存储多个键值，这使得它在磁盘存储中非常高效，因为每次磁盘I/O操作可以读取或写入一个完整的节点。
自平衡：
- B树通过分裂和合并节点来保持平衡。插入或删除操作可能会导致节点分裂或合并，但这些操作的时间复杂度仍然是 O(logn)。
适合磁盘存储：
- B树的节点通常设计为适合磁盘块的大小，这样可以减少磁盘I/O操作的次数，提高性能

三、B树的操作

1. 插入操作

查找插入位置：从根节点开始，递归地查找插入位置。
插入键值：如果目标节点未满，直接插入键值并保持有序。
分裂节点：如果目标节点已满，分裂该节点，将中间的键值提升到父节点，并将原节点分成两个子节点。
更新根节点：如果根节点满了，分裂根节点并创建一个新的根节点。

2. 删除操作

查找删除位置：从根节点开始，递归地查找要删除的键值。
删除键值：如果键值在叶子节点中，直接删除；如果键值在非叶子节点中，用其后继或前驱替换该键值，然后删除后继或前驱。
合并节点：如果删除后某个节点的键值数量少于 ⌈M/2⌉−1，则从兄弟节点借一个键值，或者与兄弟节点合并。
更新根节点：如果根节点为空，更新根节点。

3. 查找操作

从根节点开始：从根节点开始，递归地查找目标键值。
二分查找：在每个节点中使用二分查找确定目标键值所在的子树。
返回结果：如果找到目标键值，返回该节点；否则返回空。

四、B树的应用

数据库索引：
- B树是许多关系型数据库管理系统（如MySQL、PostgreSQL等）的索引实现基础。它能够高效地支持范围查询和顺序扫描。
文件系统：
- 文件系统（如NTFS、Ext4等）使用B树来管理文件和目录的元数据，以支持高效的文件查找和存储。
内存数据库：
- 一些内存数据库（如Redis）也使用B树来优化数据存储和检索。

五、B树的变种

B+树：
- B+树是B树的一个变种，所有键值都存储在叶子节点中，叶子节点通过指针连接，形成一个有序链表。B+树更适合范围查询和顺序扫描。
B*树：
- B树是B树的另一种变种，它通过减少节点分裂的频率来提高性能。B树在节点分裂时会尝试将键值均匀分配到两个子节点中。

优点

高效性：B树的多路查找结构减少了树的高度，从而减少了磁盘I/O操作。
平衡性：B树始终保持平衡，确保操作的时间复杂度为 O(logn)。
适合磁盘存储：B树的节点结构适合磁盘块的大小，减少了磁盘I/O操作。

缺点

实现复杂：B树的插入和删除操作实现较为复杂，需要处理节点分裂和合并。
内存占用：B树的每个节点需要存储多个键值和子节点指针，可能会占用较多内存。

相关代码：

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// B树节点类
template <typename T, int M>
class BTreeNode {
public:bool isLeaf;                // 是否为叶子节点vector<T> keys;             // 关键字数组vector<BTreeNode*> children; // 子节点指针数组int keyCount;               // 当前关键字数量BTreeNode(bool leaf = true) : isLeaf(leaf), keyCount(0) {keys.resize(M - 1);     // B树的阶为M，每个节点最多M-1个关键字children.resize(M);      // 最多M个子节点}~BTreeNode() {for (auto child : children) {if (child) delete child;}}// 在节点中查找key的位置或应插入的子节点索引int findKey(const T& key) {int idx = 0;while (idx < keyCount && keys[idx] < key) {++idx;}return idx;}
};// B树类
template <typename T, int M>
class BTree {
private:BTreeNode<T, M>* root;// 分裂子节点void splitChild(BTreeNode<T, M>* parent, int childIdx) {BTreeNode<T, M>* child = parent->children[childIdx];BTreeNode<T, M>* newNode = new BTreeNode<T, M>(child->isLeaf);// 新节点获取后半部分的关键字for (int i = 0; i < M/2 - 1; ++i) {newNode->keys[i] = child->keys[i + M/2];}newNode->keyCount = M/2 - 1;// 如果不是叶子节点，还要复制子节点指针if (!child->isLeaf) {for (int i = 0; i < M/2; ++i) {newNode->children[i] = child->children[i + M/2];child->children[i + M/2] = nullptr;}}child->keyCount = M/2 - 1;// 将父节点的关键字和子节点指针后移for (int i = parent->keyCount; i > childIdx; --i) {parent->keys[i] = parent->keys[i - 1];parent->children[i + 1] = parent->children[i];}// 将中间关键字提升到父节点parent->keys[childIdx] = child->keys[M/2 - 1];parent->children[childIdx + 1] = newNode;parent->keyCount++;}// 插入非满节点void insertNonFull(BTreeNode<T, M>* node, const T& key) {int i = node->keyCount - 1;if (node->isLeaf) {// 如果是叶子节点，直接插入while (i >= 0 && key < node->keys[i]) {node->keys[i + 1] = node->keys[i];i--;}node->keys[i + 1] = key;node->keyCount++;} else {// 找到合适的子节点while (i >= 0 && key < node->keys[i]) {i--;}i++;// 检查子节点是否需要分裂if (node->children[i]->keyCount == M - 1) {splitChild(node, i);if (key > node->keys[i]) {i++;}}insertNonFull(node->children[i], key);}}// 合并子节点void merge(BTreeNode<T, M>* parent, int idx) {BTreeNode<T, M>* child = parent->children[idx];BTreeNode<T, M>* sibling = parent->children[idx + 1];// 将父节点的关键字下移到子节点child->keys[M/2 - 1] = parent->keys[idx];// 复制兄弟节点的关键字和子节点for (int i = 0; i < sibling->keyCount; ++i) {child->keys[i + M/2] = sibling->keys[i];}if (!child->isLeaf) {for (int i = 0; i <= sibling->keyCount; ++i) {child->children[i + M/2] = sibling->children[i];sibling->children[i] = nullptr;}}// 调整父节点的关键字和子节点指针for (int i = idx + 1; i < parent->keyCount; ++i) {parent->keys[i - 1] = parent->keys[i];parent->children[i] = parent->children[i + 1];}child->keyCount += sibling->keyCount + 1;parent->keyCount--;delete sibling;}// 从子树中删除关键字void removeFromSubtree(BTreeNode<T, M>* node, const T& key) {int idx = node->findKey(key);if (idx < node->keyCount && node->keys[idx] == key) {// 关键字在当前节点中if (node->isLeaf) {removeFromLeaf(node, idx);} else {removeFromNonLeaf(node, idx);}} else {// 关键字不在当前节点中if (node->isLeaf) {cout << "Key " << key << " not found in the tree\n";return;}bool flag = (idx == node->keyCount);// 如果子节点关键字不足，先填充if (node->children[idx]->keyCount < M/2) {fill(node, idx);}// 如果最后一个子节点被合并，它现在会合并到前一个子节点if (flag && idx > node->keyCount) {removeFromSubtree(node->children[idx - 1], key);} else {removeFromSubtree(node->children[idx], key);}}}// 从叶子节点删除关键字void removeFromLeaf(BTreeNode<T, M>* node, int idx) {for (int i = idx + 1; i < node->keyCount; ++i) {node->keys[i - 1] = node->keys[i];}node->keyCount--;}// 从非叶子节点删除关键字void removeFromNonLeaf(BTreeNode<T, M>* node, int idx) {T key = node->keys[idx];// 如果前驱子节点有足够的关键字if (node->children[idx]->keyCount >= M/2) {T pred = getPredecessor(node, idx);node->keys[idx] = pred;removeFromSubtree(node->children[idx], pred);}// 如果后继子节点有足够的关键字else if (node->children[idx + 1]->keyCount >= M/2) {T succ = getSuccessor(node, idx);node->keys[idx] = succ;removeFromSubtree(node->children[idx + 1], succ);}// 如果两个子节点关键字都不足，则合并else {merge(node, idx);removeFromSubtree(node->children[idx], key);}}// 获取前驱关键字T getPredecessor(BTreeNode<T, M>* node, int idx) {BTreeNode<T, M>* curr = node->children[idx];while (!curr->isLeaf) {curr = curr->children[curr->keyCount];}return curr->keys[curr->keyCount - 1];}// 获取后继关键字T getSuccessor(BTreeNode<T, M>* node, int idx) {BTreeNode<T, M>* curr = node->children[idx + 1];while (!curr->isLeaf) {curr = curr->children[0];}return curr->keys[0];}// 填充不足的子节点void fill(BTreeNode<T, M>* node, int idx) {// 从前一个子节点借一个关键字if (idx != 0 && node->children[idx - 1]->keyCount >= M/2) {borrowFromPrev(node, idx);}// 从后一个子节点借一个关键字else if (idx != node->keyCount && node->children[idx + 1]->keyCount >= M/2) {borrowFromNext(node, idx);}// 合并子节点else {if (idx != node->keyCount) {merge(node, idx);} else {merge(node, idx - 1);}}}// 从前一个子节点借关键字void borrowFromPrev(BTreeNode<T, M>* node, int idx) {BTreeNode<T, M>* child = node->children[idx];BTreeNode<T, M>* sibling = node->children[idx - 1];// 将父节点的关键字下移到子节点for (int i = child->keyCount - 1; i >= 0; --i) {child->keys[i + 1] = child->keys[i];}if (!child->isLeaf) {for (int i = child->keyCount; i >= 0; --i) {child->children[i + 1] = child->children[i];}}child->keys[0] = node->keys[idx - 1];if (!child->isLeaf) {child->children[0] = sibling->children[sibling->keyCount];sibling->children[sibling->keyCount] = nullptr;}node->keys[idx - 1] = sibling->keys[sibling->keyCount - 1];child->keyCount++;sibling->keyCount--;}// 从后一个子节点借关键字void borrowFromNext(BTreeNode<T, M>* node, int idx) {BTreeNode<T, M>* child = node->children[idx];BTreeNode<T, M>* sibling = node->children[idx + 1];child->keys[child->keyCount] = node->keys[idx];if (!child->isLeaf) {child->children[child->keyCount + 1] = sibling->children[0];sibling->children[0] = nullptr;}node->keys[idx] = sibling->keys[0];for (int i = 1; i < sibling->keyCount; ++i) {sibling->keys[i - 1] = sibling->keys[i];}if (!sibling->isLeaf) {for (int i = 1; i <= sibling->keyCount; ++i) {sibling->children[i - 1] = sibling->children[i];sibling->children[i] = nullptr;}}child->keyCount++;sibling->keyCount--;}public:BTree() : root(nullptr) {}~BTree() {if (root) delete root;}// 查找关键字bool search(const T& key) {if (!root) return false;BTreeNode<T, M>* curr = root;while (curr) {int i = curr->findKey(key);if (i < curr->keyCount && curr->keys[i] == key) {return true;}if (curr->isLeaf) {return false;}curr = curr->children[i];}return false;}// 插入关键字void insert(const T& key) {if (!root) {root = new BTreeNode<T, M>(true);root->keys[0] = key;root->keyCount = 1;return;}// 如果根节点已满，需要分裂if (root->keyCount == M - 1) {BTreeNode<T, M>* newRoot = new BTreeNode<T, M>(false);newRoot->children[0] = root;splitChild(newRoot, 0);// 决定将新关键字插入哪个子节点int i = 0;if (newRoot->keys[0] < key) {i++;}insertNonFull(newRoot->children[i], key);root = newRoot;} else {insertNonFull(root, key);}}// 删除关键字void remove(const T& key) {if (!root) {cout << "Tree is empty\n";return;}removeFromSubtree(root, key);// 如果根节点没有关键字了，使其第一个子节点成为新的根节点if (root->keyCount == 0) {BTreeNode<T, M>* temp = root;if (root->isLeaf) {root = nullptr;} else {root = root->children[0];temp->children[0] = nullptr; // 防止析构时被删除}delete temp;}}// 打印B树void print() {if (root) {printNode(root, 0);}}private:void printNode(BTreeNode<T, M>* node, int level) {cout << "Level " << level << ": ";for (int i = 0; i < node->keyCount; ++i) {cout << node->keys[i] << " ";}cout << endl;if (!node->isLeaf) {for (int i = 0; i <= node->keyCount; ++i) {if (node->children[i]) {printNode(node->children[i], level + 1);}}}}
};int main() {BTree<int, 4> tree; // 创建一个4阶B树// 插入测试tree.insert(10);tree.insert(20);tree.insert(5);tree.insert(6);tree.insert(12);tree.insert(30);tree.insert(7);tree.insert(17);cout << "B树结构:" << endl;tree.print();// 查找测试cout << "\n查找测试:" << endl;cout << "6 " << (tree.search(6) ? "存在" : "不存在") << endl;cout << "15 " << (tree.search(15) ? "存在" : "不存在") << endl;// 删除测试cout << "\n删除6后:" << endl;tree.remove(6);tree.print();cout << "\n删除13(不存在)后:" << endl;tree.remove(13);tree.print();cout << "\n删除30后:" << endl;tree.remove(30);tree.print();return 0;
}

代码运行结果：

微信截图_20250615164334

六、代码说明

BTreeNode类：表示B树的节点，包含：
- isLeaf：标记是否为叶子节点
- keys：存储关键字的数组
- children：存储子节点指针的数组
- keyCount：当前节点中关键字的数量
BTree类：实现B树的主要操作：
- insert：插入新关键字
- remove：删除关键字
- search：查找关键字
- print：打印B树结构
核心操作：
- splitChild：分裂子节点
- merge：合并子节点
- borrowFromPrev/Next：从相邻节点借关键字
- insertNonFull：向非满节点插入关键字
- removeFromSubtree：从子树中删除关键字
测试代码：
- 创建4阶B树
- 插入多个关键字
- 测试查找和删除操作