B树和B+树的概念和区别以及其C++实现

B树是一种自平衡的查找树,它具有以下特征:

1. 是m叉树,通常m的值在2到3之间。也就是每个节点最多有m个孩子。
2. 除了根节点和叶子节点外,其他每个节点至少有m/2个孩子。
3. 根节点至少有两个孩子。
4. 所有的叶子节点处于同一层级。
5. 每个节点存放至多m-1个关键字(key)。关键字的个数n满足m/2<=n<=m-1。
6. 关键字按从小到大的顺序存放。
7. 非叶子节点的指针按关键字的值从小到大进行链接。
   B树的主要优点如下:
8. 查找、插入和删除的时间复杂度为O(logn)。
9. 由于关键字和指针的分布,B树的查询效率比较高。
10. B树的高度较低,因此在大容量存储介质(如磁盘)上查询效率也比较高。
11. B树支持动态插入和删除,且可以维持较高的平衡度。
12. B树减少了磁盘I/O次数,因此查询速度较快。

所以,总的来说,B树是一种效率较高的索引结构,支持高效的查找、插入和删除操作,特别适用于外存索引的构建。它是广泛使用的数据库索引类型之一。
B+树是B树的变体,两者的主要区别在于:B+树只在叶子节点存放关键字信息,且叶子节点使用链表连接。所以B+树的查询效率高于B树,更适合外部存储器的查找。
B树和B+树是两种常见的数据结构，它们都是一种多路搜索树，用于在大量数据中进行查找。B树和B+树的区别主要有以下几点：

1. B树的非叶子节点也存储关键字信息,但B+树的非叶子节点只存储指向子树根节点的指针,关键字只存在于叶子节点。
2. B+树的叶子节点使用链表连接,提高区间访问效率。B树的叶子节点不连接。
3. B+树的查询效率高于B树,因为B+树的关键字都在叶子节点,且叶子节点链表连接。B树的关键字分布在各个层,效率稍低。
4. B+树的修改稍微复杂,因为插入时需要维护叶子节点链表。B树的修改简单些。
5. B+树的存储空间稍大,因为非叶子节点也存储指针。B树的存储稍小。
   所以总体来说,B+树的查询效率高,更适合在外部存储器中使用,如数据库索引。B树的修改简单,空间效率高,也较适用于内存索引。但两者的时间复杂度都是O(logn)。

以下是简易版的B树和B+树的实现方式

template <typename T>
class Node {T key;Node *left;Node *right;bool isLeaf;Node* parent;Node(T key, Node* left, Node* right, bool isLeaf, Node* parent) {this->key = key;this->left = left;this->right = right;this->isLeaf = isLeaf;this->parent = parent;}
};template <typename T>
class BTree {Node<T>* root;int m;  // 阶数public:BTree(int m) {root = nullptr;this->m = m;}// 查找关键字key所在的节点Node<T>* search(T key) {Node<T>* cur = root;while (cur != nullptr) {if (key == cur->key) return cur;else if (key < cur->key) cur = cur->left;else cur = cur->right;}return nullptr;}// 向树中插入关键字keyvoid insert(T key) {// 找到父节点parent和叶子节点leafNode<T>* leaf = search(key);Node<T>* parent = nullptr;if (leaf == nullptr) {  // 没找到,树为空,插入根节点root = new Node<T>(key, nullptr, nullptr, true, nullptr);return;} else {parent = leaf->parent;}if (leaf->isLeaf) { // 找到叶子节点,插入if (key == leaf->key) return;  // key已存在,不插入else if (key < leaf->key) {leaf->left = new Node<T>(key, nullptr, nullptr, true, leaf);leaf->left->parent = leaf;} else {leaf->right = new Node<T>(key, nullptr, nullptr, true, leaf);leaf->right->parent = leaf;}} else {    // 未找到叶子,继续递归插入if (key < leaf->key) insert(key, leaf->left);else insert(key, leaf->right);}// 插入后,检测阶数是否超过m,若超过则拆分if (leaf->isLeaf && (leaf->left != nullptr && leaf->left->isLeaf)&& (leaf->right != nullptr && leaf->right->isLeaf)&& (leaf->left->key - leaf->key) + (leaf->key - leaf->right->key) > m) {split(leaf);}}private:// 拆分节点,节点分裂成两个节点void split(Node<T>* node) {// 找到中位数key和中点midpointT midKey;Node<T>* midNode;if (node->left->isLeaf && node->right->isLeaf) {midKey = (node->left->key + node->key) / 2;midNode = node->left;} else if (node->left->isLeaf) {midKey = node->left->key;midNode = node->left;} else if (node->right->isLeaf) {midKey = node->key;midNode = node;}// 创建新节点newNode,并移动节点至newNodeNode<T>* newNode = new Node<T>(midKey, nullptr, nullptr, true, node->parent);if (midNode == node) {  // 以node节点中间键为分界newNode->left = node->left;node->left->parent = newNode;node->left = midNode->right;midNode->right->parent = node;newNode->right = midNode->right;midNode->right = nullptr;} else {    // 以node左子节点或右子节点为分界newNode->left = midNode->left;newNode->right = node->right;node->right = nullptr;midNode->left = nullptr;}}
};template <typename T>
class BPlusTree {Node<T>* root;int m;  // 阶数public:BPlusTree(int m) {root = nullptr;this->m = m;}// 查找关键字key所在的节点Node<T>* search(T key) {Node<T>* cur = root;while (cur != nullptr && !cur->isLeaf) {cur = key < cur->key ? cur->next : cur->pre;}return cur;}// 向树中插入关键字keyvoid insert(T key) {Node<T>* leaf = search(key);if (leaf == nullptr) {  // 树为空,插入根节点root = new Node<T>(key, nullptr, nullptr, true, nullptr);return;}if (key == leaf->key) return;   // key已存在,不插入// 找到叶子节点后插入Node<T>* newNode = new Node<T>(key, nullptr, nullptr, true, leaf->parent);if (key < leaf->key) {   // 插入到当前节点之前newNode->next = leaf;newNode->pre = leaf->pre;leaf->pre->next = newNode;leaf->pre = newNode;} else {    // 插入到当前节点之后newNode->pre = leaf;newNode->next = leaf->next;leaf->next->pre = newNode;leaf->next = newNode;}// 插入后,检测阶数是否超过m,若超过则拆分if (leaf != nullptr && leaf->next != nullptr && leaf->pre != nullptr&& leaf->next->key - leaf->key + leaf->key - leaf->pre->key > m) {split(leaf);}}private:// 拆分节点,节点分裂成两个节点void split(Node<T>* node) {Node<T>* newNode;T midKey;if (node == root) {     // 根节点拆分midKey = (node->next->key + node->key) / 2;newNode = new Node<T>(midKey, node->next, node, false, nullptr);node->next->pre = newNode;node->next = newNode->next;node->next->pre = node;newNode->next = node;root = newNode;return;}if (node->pre->key < node->key && node->key < node->next->key) {midKey = (node->pre->key + node->key) / 2;newNode = new Node<T>(midKey, node->pre->next, node->pre, false, node->parent);node->pre->next = newNode;node->pre = newNode;} else if (node->key < node->next->key && node->next->key < node->pre->key) {midKey = (node->key + node->next->key) / 2;newNode = new Node<T>(midKey, node, node->next, false, node->parent);node->next->pre = newNode;node->next = newNode->next;node->next->pre = node;newNode->next = node->next;}}
};