B+树的插入与删除

B+树删除(仅考虑阶数m>=3的情形，注意叶节点合并时需要修改叶节点顺序链表的链接指针，下文并未提到)

删除仅在叶节点上进行,在叶节点上删除给定关键码后，如果叶节点为根节点则删除操作结束(此时删除后的B+树可能为空树).如果不为根节点且含有的关键码树>=ceil(m/2)[ceil表示向上取整]则删除操作结束，如果删除的是叶节点最右侧的关键码，还需用新的最右侧关键码沿叶节点至根节点的路径向上更新父节点指向叶节点，父节点的父节点-指向父节点—–的索引项，直到根节点的索引项被更新或被更新的索引项不是节点最右侧索引项为止。如果删除关键码的叶节点不为根节点且关键码数等于ceil(m/2)-1，那么如果叶节点有右兄弟节点，且右兄弟节点的关键码数大于等于ceil(m/2)+1，则把右兄弟节点最左侧关键码上移替代指向叶节点索引项中的关键码，并把最左侧关键码复制至叶节点最右侧，至此删除操作结束。如果右兄弟节点的关键码数等于ceil(m/2)，则将被删叶节点完整拼接至右兄弟节点左侧，删除叶节点和指向它的索引项，然后若父节点为根或父节点不为根且关键码数大于等于ceil(m/2)则结束删除操作，否则回溯至父节点继续处理。

如果叶节点既无右兄弟节点也无左兄弟节点则删除父节点(根节点)，并令根节点指针指向叶节点，然后删除操作结束

如果叶节点没有右兄弟节点，但有左兄弟节点，且左兄弟节点关键码数大于等于ceil(m/2)+1,则将父节点指向左兄弟节点的索引项中的关键码下移至叶节点最左侧，删除左兄弟节点最右侧关键码，然后用左兄弟节点新的最右侧关键码填补父节点指向它的索引项中关键码位置，随后同样的，若叶节点最右侧关键码小于父节点最右侧关键码则向上更新祖先节点索引项，然后删除操作结束。

如果叶节点没有右兄弟节点但有左兄弟节点，且左兄弟节点关键码数等于ceil(m/2)则将左兄弟节点完整拼接至叶节点左侧，然后删除左兄弟节点和父节点中指向它的索引项，随后若父节点为根节点或父节点不为根节点且关键码数大于等于ceil(m/2)则删除操作结束(注意若叶节点最右侧关键码小于父节点最右侧关键码则应向上更新祖先节点索引项),否则用叶节点最右侧关键码更新父节点最右侧关键码，然后回溯至父节点继续处理

现设删除操作中当前节点的关键码数为ceil(m/2)-1且不是叶节点。

那么如果它有右兄弟，且右兄弟关键码数大于等于ceil(m/2)+1则把右兄弟最左侧关键码上移取代父节点中指向当前节点的索引项中的关键码，并将该关键码复制至当前节点最右侧，此外还应将右兄弟最左侧指针移动至当前节点最右侧，然后删除操作结束

如果它有右兄弟,且右兄弟关键码数等于ceil(m/2),则当前节点拼接至右兄弟最左侧，删去当前节点和父节点中指向它的索引项，然后父节点为根节点或父节点不为根节点且关键码数大于等于ceil(m/2)则删除操作结束，否则回溯至父节点进一步处理。

若果它没有右兄弟也无左兄弟则删除父节点(根节点)，并令根节点指针指向当前节点，然后删除操作结束

若果它没有右兄弟但有左兄弟，且左兄弟关键码数大于等于ceil(m/2)+1,则将父节点中指向左兄弟的索引项中的关键码下移至当前节点最左侧，删除左兄弟最右侧关键码并将左兄弟最右侧指针移至当前节点最左侧，最后用左兄弟新的最右侧关键码填补父节点中指向它的索引项中的关键码所在位置，删除操作结束(注意若当前节点最右侧关键码小于父节点最右侧关键码则应向上更新祖先节点索引项)

如果它没有右兄弟但有左兄弟，且左兄弟关键码数等于ceil(m/2),则将左兄弟完整拼接至当前节点左侧，然后删除左兄弟和父节点中指向它的索引项，随后若父节点为根节点或父节点不为根节点且关键码数大于等于ceil(m/2)则删除操作结束(注意若当前节点最右侧关键码小于父节点最右侧关键码则应向上更新祖先节点索引项),否则用叶节点最右侧关键码更新父节点最右侧关键码，然后回溯至父节点继续处理

B+树插入(仅考虑阶数m>=3的情形，注意叶节点分裂时需要修改叶节点顺序链表的链接指针，下文并未提到)

在空树中插入，直接新建根节点并填入关键码并令root和head指针指向根节点即可

若在非空树中插入那么通过搜索在叶节点中找到插入位置直接插入，若插入后叶节点关键码数小于等于m则插入结束，否则叶节点从中间分裂为长度分别为floor((m+1)/2)和ceil((m+1)/2)的两部分，长度为ceil((m+1)/2)的部分是分裂后的原叶节点。如果原叶节点没有父节点则创建新根节点，左右两关键码为两分裂部分的最大关键码，左右两指针分别指向两分裂部分，令根节点指针指向新根节点，插入结束，否则将最大关键码较小的分裂部分的指针及其最大关键码构成的二元组插入至原叶节点父节点中最大关键码较大的分裂部分对应的二元组的左侧，父节点关键码指针数加一。如果插入二元组后父节点关键码数小于等于m，则插入结束,否则以父节点为当前节点回溯至父节点

现设插入过程中当前节点有m+1个关键码且不为叶节点，则和上述类似将当前节点分裂为长度分别为floor((m+1)/2)和ceil((m+1)/2)的两部分，长度为ceil((m+1)/2)的部分是分裂后的原当前节点，如果原当前节点没有父节点则创建新根节点，左右两关键码为两分裂部分的最大关键码，左右两指针分别指向两分裂部分，令根节点指针指向新根节点，插入结束，否则将最大关键码较小的分裂部分的指针及其最大关键码构成的二元组插入至原当前节点父节点中最大关键码较大的分裂部分对应的二元组的左侧，父节点关键码指针数加一。如果插入二元组后父节点关键码数小于等于m，则插入结束,否则以父节点为当前节点回溯至父节点

C++代码实现(如有错误欢迎指出)

#include <iostream> #include <utility> #include <stack> #include <vector> #include <random> #include <ctime> #include <algorithm> using namespace std; const int M = 4; //B+树阶数 template <typename T> struct BPlusTreeNode { union { pair<vector<T>, BPlusTreeNode<T>*>* keyandptr; //叶节点指针域和数据域 vector<pair<T, BPlusTreeNode<T>*>>* keyptrmap; //分支节点索引项集合 }; enum flag { leaf, branch } NodeFlag; //节点标志叶节点or分支节点 BPlusTreeNode(flag N); ~BPlusTreeNode(); }; template <typename T> BPlusTreeNode<T>::BPlusTreeNode(flag N) { NodeFlag = N; if (NodeFlag == leaf) { keyandptr = new pair<vector<T>, BPlusTreeNode<T>*>(vector<T>(), nullptr); } else { keyptrmap = new vector<pair<T, BPlusTreeNode<T>*>>(); } } template <typename T> BPlusTreeNode<T>::~BPlusTreeNode() { if (NodeFlag == leaf) { delete keyandptr; } else { delete keyptrmap; } } template <typename T> pair<typename vector<pair<T, BPlusTreeNode<T>*>>::iterator, bool> SearchBPlusTreeNode(BPlusTreeNode<T>* ptr, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator d) //返回值：尾后表示失败,非尾后即为对应指针 { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator m; //实参pair:尾后表示从第一指针后一指针开始搜索,非尾后表示从非尾后后一位置开始搜索 if (d == ptr->keyptrmap->end()) { m = ptr->keyptrmap->begin(); } else { m = d; ++m; } if (m == ptr->keyptrmap->end() || m->second != nullptr) return { m, true }; return { ptr->keyptrmap->end(), false }; } template <typename T> T getMaxValueForLeaf(BPlusTreeNode<T>* leaf) { typename vector<T>::iterator t = leaf->keyandptr->first.end() - 1; return *t; } template <typename T> bool leafKeyFromSmallToBig(BPlusTreeNode<T>* leaf) { typename vector<T>::iterator before = leaf->keyandptr->first.begin(); typename vector<T>::iterator after = before + 1; for (; after != leaf->keyandptr->first.end(); before = after, ++after) { if (*before >= *after) return false; } return true; } template <typename T> bool isBPlusTree(BPlusTreeNode<T>* root, BPlusTreeNode<T>* head) //判断给定多叉树是否为B树 { struct memory { BPlusTreeNode<T>* p; typename vector<pair<T, BPlusTreeNode<T>*>>::iterator direction; T nodemin; memory(BPlusTreeNode<T>* p, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator d) :p(p), direction(d) {} }; T max_value_pre_leaf; BPlusTreeNode<T>* leaf_list_run = head; BPlusTreeNode<T>* ptr = root; typename vector<pair<T, BPlusTreeNode<T>*>>::iterator d; if (ptr->NodeFlag != BPlusTreeNode<T>::flag::leaf) d = ptr->keyptrmap->end(); pair<typename vector<pair<T, BPlusTreeNode<T>*>>::iterator, bool> t; BPlusTreeNode<T>* const dest = ptr; stack<memory> arrange; bool TF = false; int level = 0; int beforelevel = 0; T min; T max; while (true) { if (ptr->NodeFlag == BPlusTreeNode<T>::flag::leaf ? true : (t = SearchBPlusTreeNode(ptr, d)) == pair<typename vector<pair<T, BPlusTreeNode<T>*>>::iterator, bool>(ptr->keyptrmap->end(), true)) { if (ptr == dest) { if (ptr->NodeFlag == BPlusTreeNode<T>::flag::leaf) { if (!(1 <= ptr->keyandptr->first.size() && ptr->keyandptr->first.size() <= M)) { cout << "当前树只有根节点,但根节点子树数量不符合要求,非B+树" << endl; return false; } if (leafKeyFromSmallToBig(ptr) == false) { cout << "当前树只有根节点,但根节点关键码没有从小到大排列,非B+树" << endl; return false; } return true; } else { if (2 <= ptr->keyptrmap->size() && ptr->keyptrmap->size() <= M) { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = ptr->keyptrmap->end(); --temp; if (max == temp->first) { --temp; if (min > temp->first) { return true; } else { cout << "当前树不是" << M << "路搜索树,非B+树" << endl; return false; } } else { cout << "当前树不是" << M << "路搜索树,非B+树" << endl; return false; } } else { cout << "当前树根节点子树数量不符合要求,非B+树"; return false; } } } else { if (ptr->NodeFlag == BPlusTreeNode<T>::flag::leaf) { ++level; if (TF == false) { beforelevel = level; TF = true; } else { if (level != beforelevel) { cout << "叶节点不在同一层,非B+树" << endl; return false; } } if ((M + 1) / 2 <= ptr->keyandptr->first.size() && ptr->keyandptr->first.size() <= M) { if (arrange.top().direction == arrange.top().p->keyptrmap->begin()) { arrange.top().nodemin = *(ptr->keyandptr->first.begin()); } min = *(ptr->keyandptr->first.begin()); max = *(--ptr->keyandptr->first.end()); } else { cout << "当前树叶节点关键码数量不符合要求,非B+树" << endl; return false; } if (leafKeyFromSmallToBig(ptr) == false) { cout << "当前树叶节点关键码没有从小到大排列,非B+树" << endl; return false; } if (leaf_list_run != nullptr && ptr == leaf_list_run) { if (leaf_list_run != head) { if (*(leaf_list_run->keyandptr->first.begin()) <= max_value_pre_leaf) { cout << "叶节点链表关键码非从小到大排列,非B+树" << endl; return false; } } max_value_pre_leaf = getMaxValueForLeaf(leaf_list_run); leaf_list_run = leaf_list_run->keyandptr->second; } else { cout << "叶节点链表没有顺序链接所有叶节点,非B+树" << endl; return false; } } else { if ((M + 1) / 2 <= ptr->keyptrmap->size() && ptr->keyptrmap->size() <= M) { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = ptr->keyptrmap->end(); --temp; if (max == temp->first) { --temp; if (min > temp->first) { min = arrange.top().nodemin; arrange.pop(); if (arrange.top().direction == arrange.top().p->keyptrmap->begin()) arrange.top().nodemin = min; } else { cout << "当前树不是" << M << "路搜索树,非B+树" << endl; return false; } } else { cout << "当前树不是" << M << "路搜索树,非B+树" << endl; return false; } } else { cout << "当前树分支节点子树数量不符合要求,非B+树" << endl; return false; } } --level; ptr = arrange.top().p; d = arrange.top().direction; } } else { if (t.second == false) { cout << "非叶节点的分支节点存在空子树,非B+树" << endl; return false; } if (d == ptr->keyptrmap->end()) { arrange.push(memory(ptr, ptr->keyptrmap->begin())); ptr = ptr->keyptrmap->begin()->second; ++level; } else { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = t.first; --temp; if (max == temp->first) { if (temp != ptr->keyptrmap->begin()) { --temp; if (!(min > temp->first)) { cout << "当前树不是" << M << "路搜索树,非B+树" << endl; return false; } } } else { cout << "当前树不是" << M << "路搜索树,非B+树" << endl; return false; } arrange.top().direction = t.first; ptr = t.first->second; } if (ptr->NodeFlag != BPlusTreeNode<T>::flag::leaf) { d = ptr->keyptrmap->end(); } } } if (leaf_list_run != nullptr) { cout << "叶节点链表中叶节点数大于B+树中叶节点数,非B+树" << endl; return false; } } template <typename T> bool compare(const pair<T, BPlusTreeNode<T>*>& left, const pair<T, BPlusTreeNode<T>*>& right) { return left.first < right.first; } template <typename T> void updatemax(stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>>& stackforback, T key) //向上更新父节点索引项关键码 { while (stackforback.empty() == false) { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = stackforback.top().second; if (temp == stackforback.top().first->keyptrmap->end()) --temp; temp->first = key; ++temp; if (temp != stackforback.top().first->keyptrmap->end()) { break; } stackforback.pop(); } } template <typename T> pair<bool, typename vector<T>::iterator> BinarySearch(vector<T>& list, typename vector<T>::iterator left, typename vector<T>::iterator right, const T& key) { while (left <= right) { int d = right - left + 1; typename vector<T>::iterator mid; if (d % 2 == 1) { mid = left + d / 2; } else { mid = left + (d / 2 - 1); } if (key < *mid) { if (mid == list.begin()) { return { false, left }; } right = mid - 1; } else if (key > *mid) { left = mid + 1; } else { return { true, mid }; } } return { false, left }; } template <typename T> typename vector<pair<T, BPlusTreeNode<T>*>>::iterator Upper_Bound(const T& key, vector<pair<T, BPlusTreeNode<T>*>>& list) { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator left = list.begin(); typename vector<pair<T, BPlusTreeNode<T>*>>::iterator right = list.end() - 1; while (left <= right) { int d = right - left + 1; typename vector<pair<T, BPlusTreeNode<T>*>>::iterator mid; if (d % 2 == 1) { mid = left + d / 2; } else { mid = left + (d / 2 - 1); } if (key <= (*mid).first) { if (mid == list.begin()) { return left; } right = mid - 1; } else { left = mid + 1; } } return left; } template<typename T> bool afterSplit(stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>>& stackforback, BPlusTreeNode<T>* ptr, BPlusTreeNode<T>*& current) { if (stackforback.top().first->keyptrmap->size() <= M) { if (stackforback.top().second == stackforback.top().first->keyptrmap->end()) { stackforback.pop(); if (ptr->NodeFlag == BPlusTreeNode<T>::flag::leaf) updatemax(stackforback, ptr->keyandptr->first.back()); else updatemax(stackforback, ptr->keyptrmap->back().first); } return true; } current = stackforback.top().first; stackforback.pop(); return false; } template <typename T> void left_to_right_for_leaf(BPlusTreeNode<T>* left, BPlusTreeNode<T>* right, const typename vector<pair<T, BPlusTreeNode<T>*>>::iterator &mid) { right->keyandptr->first.insert(right->keyandptr->first.begin(), mid->first); left->keyandptr->first.pop_back(); mid->first = left->keyandptr->first.back(); } template <typename T> void right_to_left_for_leaf(BPlusTreeNode<T>* left, BPlusTreeNode<T>* right, const typename vector<pair<T, BPlusTreeNode<T>*>>::iterator& mid) { left->keyandptr->first.push_back(*(right->keyandptr->first.begin())); mid->first = *(right->keyandptr->first.begin()); right->keyandptr->first.erase(right->keyandptr->first.begin()); } template <typename T> void left_to_right_for_branch(BPlusTreeNode<T>* left, BPlusTreeNode<T>* right, const typename vector<pair<T, BPlusTreeNode<T>*>>::iterator& mid) { right->keyptrmap->insert(right->keyptrmap->begin(), left->keyptrmap->back()); left->keyptrmap->pop_back(); mid->first = left->keyptrmap->back().first; } template <typename T> void right_to_left_for_branch(BPlusTreeNode<T>* left, BPlusTreeNode<T>* right, const typename vector<pair<T, BPlusTreeNode<T>*>>::iterator& mid) { left->keyptrmap->push_back(*(right->keyptrmap->begin())); mid->first = right->keyptrmap->begin()->first; right->keyptrmap->erase(right->keyptrmap->begin()); } template <typename T> bool toRight(stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>>& stackforback, BPlusTreeNode<T>* current) { if (stackforback.top().second < stackforback.top().first->keyptrmap->end() - 1) { if (current->NodeFlag == BPlusTreeNode<T>::flag::leaf) { if (stackforback.top().second < stackforback.top().first->keyptrmap->end() - 1) { if ((stackforback.top().second + 1)->second->keyandptr->first.size() < M) { left_to_right_for_leaf(current, (stackforback.top().second + 1)->second, stackforback.top().second); return true; } } } else { if (stackforback.top().second < stackforback.top().first->keyptrmap->end() - 1) { if ((stackforback.top().second + 1)->second->keyptrmap->size() < M) { left_to_right_for_branch(current, (stackforback.top().second + 1)->second, stackforback.top().second); return true; } } } } return false; } template <typename T> bool toLeft(stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>>& stackforback, BPlusTreeNode<T>* current) { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = stackforback.top().second; if (temp != stackforback.top().first->keyptrmap->begin()) { if (temp == stackforback.top().first->keyptrmap->end()) --temp; if (current->NodeFlag == BPlusTreeNode<T>::flag::leaf) { if ((temp - 1)->second->keyandptr->first.size() < M) { right_to_left_for_leaf((temp - 1)->second, current, temp - 1); if (stackforback.top().second == stackforback.top().first->keyptrmap->end()) { updatemax(stackforback, current->keyandptr->first.back()); } return true; } } else { if ((temp - 1)->second->keyptrmap->size() < M) { right_to_left_for_branch((temp - 1)->second, current, temp - 1); if (stackforback.top().second == stackforback.top().first->keyptrmap->end()) { updatemax(stackforback, current->keyptrmap->back().first); } return true; } } } return false; } template <typename T> bool toLeftOrRight(stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>>& stackforback, BPlusTreeNode<T>* current) { if (toRight(stackforback, current)) return true; if (toLeft(stackforback, current)) return true; return false; } template <typename T> pair<BPlusTreeNode<T>*, BPlusTreeNode<T>*> BPlusInsert(BPlusTreeNode<T>* root, BPlusTreeNode<T>* head, const T& key) //B+树插入函数 { if (root == nullptr) { root = new BPlusTreeNode<T>(BPlusTreeNode<T>::flag::leaf); head = root; root->keyandptr->first.push_back(key); return { root, head }; } else { BPlusTreeNode<T>* current = root; stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>> stackforback; while (current->NodeFlag != BPlusTreeNode<T>::flag::leaf) { BPlusTreeNode<T>* p = nullptr; typename vector<pair<T, BPlusTreeNode<T>*>>::iterator scankey = Upper_Bound(key, *(current->keyptrmap)); if (scankey == current->keyptrmap->end()) { stackforback.push(make_pair(current, scankey)); --scankey; p = scankey->second; while (p->NodeFlag != BPlusTreeNode<T>::flag::leaf) { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = p->keyptrmap->end(); stackforback.push(make_pair(p, temp)); --temp; p = temp->second; } current = p; break; } if (scankey->first == key) { cout << "关键码" << key << "已存在,无法插入" << endl; return { root, head }; } stackforback.push(make_pair(current, scankey)); current = scankey->second; } { pair<bool, typename vector<T>::iterator> result = BinarySearch(current->keyandptr->first, current->keyandptr->first.begin(), current->keyandptr->first.end() - 1, key); if (result.first == false) { current->keyandptr->first.insert(result.second, key); if (current->keyandptr->first.size() <= M) { if (current != root && key == current->keyandptr->first.back()) updatemax(stackforback, current->keyandptr->first.back()); return { root, head }; } if (stackforback.empty() == false) { if (toLeftOrRight(stackforback, current)) return { root, head }; } BPlusTreeNode<T>* ptr = new BPlusTreeNode<T>(BPlusTreeNode<T>::flag::leaf); ptr->keyandptr->first.insert(ptr->keyandptr->first.end(), current->keyandptr->first.end() - (M + 1) / 2, current->keyandptr->first.end()); current->keyandptr->first.erase(current->keyandptr->first.end() - (M + 1) / 2, current->keyandptr->first.end()); ptr->keyandptr->second = current->keyandptr->second; current->keyandptr->second = ptr; if (stackforback.empty() == true) { root = new BPlusTreeNode<T>(BPlusTreeNode<T>::flag::branch); root->keyptrmap->push_back(make_pair(current->keyandptr->first.back(), current)); root->keyptrmap->push_back(make_pair(ptr->keyandptr->first.back(), ptr)); return { root, head }; } typename vector<T>::iterator temp = ptr->keyandptr->first.end() - 1; if (stackforback.top().second == stackforback.top().first->keyptrmap->end()) { stackforback.top().first->keyptrmap->insert(stackforback.top().second, make_pair(*temp, ptr)); stackforback.top().second = stackforback.top().first->keyptrmap->end(); (stackforback.top().second - 2)->first = *(current->keyandptr->first.end() - 1); } else { stackforback.top().second = stackforback.top().first->keyptrmap->insert(stackforback.top().second + 1, make_pair(*temp, ptr)); --stackforback.top().second; stackforback.top().second->first = *(current->keyandptr->first.end() - 1); } if (afterSplit(stackforback, ptr, current)) return { root, head }; while (true) { if (stackforback.empty() == false) { if (toLeftOrRight(stackforback, current)) return { root, head }; } BPlusTreeNode<T>* ptr = new BPlusTreeNode<T>(BPlusTreeNode<T>::flag::branch); ptr->keyptrmap->insert(ptr->keyptrmap->end(), current->keyptrmap->end() - (M + 1) / 2, current->keyptrmap->end()); current->keyptrmap->erase(current->keyptrmap->end() - (M + 1) / 2, current->keyptrmap->end()); if (stackforback.empty() == true) { root = new BPlusTreeNode<T>(BPlusTreeNode<T>::flag::branch); root->keyptrmap->push_back(make_pair(current->keyptrmap->back().first, current)); root->keyptrmap->push_back(make_pair(ptr->keyptrmap->back().first, ptr)); return { root, head }; } typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = ptr->keyptrmap->end() - 1; if (stackforback.top().second == stackforback.top().first->keyptrmap->end()) { stackforback.top().first->keyptrmap->insert(stackforback.top().second, make_pair(temp->first, ptr)); stackforback.top().second = stackforback.top().first->keyptrmap->end(); (stackforback.top().second - 2)->first = current->keyptrmap->back().first; } else { stackforback.top().second = stackforback.top().first->keyptrmap->insert(stackforback.top().second + 1, make_pair(temp->first, ptr)); --stackforback.top().second; stackforback.top().second->first = current->keyptrmap->back().first; } if (afterSplit(stackforback, ptr, current)) return { root, head }; } } else { cout << "关键码" << key << "已存在,无法插入" << endl; return { root, head }; } } } } template <typename T> bool afterMerge(stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>>& stackforback, BPlusTreeNode<T>*& root, BPlusTreeNode<T>*& current, const typename vector<pair<T, BPlusTreeNode<T>*>>::iterator& temp, const T& key) { if (stackforback.top().first == root || stackforback.top().first->keyptrmap->size() >= (M + 1) / 2) { if (stackforback.top().first == root && root->keyptrmap->size() == 1) { BPlusTreeNode<T>* temp_ptr = root->keyptrmap->front().second; delete root; root = temp_ptr; } else { if (current == nullptr) { if (temp->second->NodeFlag == BPlusTreeNode<T>::flag::leaf) { if (temp->second->keyandptr->first.back() < key) { stackforback.pop(); updatemax(stackforback, temp->second->keyandptr->first.back()); } } else { if (temp->second->keyptrmap->back().first < key) { stackforback.pop(); updatemax(stackforback, temp->second->keyptrmap->back().first); } } } } return true; } current = stackforback.top().first; stackforback.pop(); return false; } template <typename T> bool borrowFromRight(stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>>& stackforback, BPlusTreeNode<T>* current) { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = stackforback.top().second; ++temp; if (temp != stackforback.top().first->keyptrmap->end()) { if (current->NodeFlag == BPlusTreeNode<T>::flag::leaf) { if (temp->second->keyandptr->first.size() >= (M + 1) / 2 + 1) { right_to_left_for_leaf(current, temp->second, stackforback.top().second); return true; } } else { if (temp->second->keyptrmap->size() >= (M + 1) / 2 + 1) { right_to_left_for_branch(current, temp->second, stackforback.top().second); return true; } } } return false; } template <typename T> bool borrowFromLeft(stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>>& stackforback, BPlusTreeNode<T>* current, const T& key) { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = stackforback.top().second; if (temp != stackforback.top().first->keyptrmap->begin()) { --temp; if (current->NodeFlag == BPlusTreeNode<T>::flag::leaf) { if (temp->second->keyandptr->first.size() >= (M + 1) / 2 + 1) { left_to_right_for_leaf(temp->second, current, temp); if (current->keyandptr->first.back() < key) updatemax(stackforback, current->keyandptr->first.back()); return true; } } else { if (temp->second->keyptrmap->size() >= (M + 1) / 2 + 1) { left_to_right_for_branch(temp->second, current, temp); if (current->keyptrmap->back().first < key) updatemax(stackforback, current->keyptrmap->back().first); return true; } } } return false; } template <typename T> bool borrowFromLeftOrRight(stack<pair<BPlusTreeNode<T>*, typename vector<pair<T, BPlusTreeNode<T>*>>::iterator>>& stackforback, BPlusTreeNode<T>* current, const T& key) { if (borrowFromRight(stackforback, current)) return true; if (borrowFromLeft(stackforback, current, key)) return true; return false; } template <typename T> pair<BPlusTreeNode<T>*, BPlusTreeNode<T>*> BPlusDelete(BPlusTreeNode<T>* root, BPlusTreeNode<T>* head, const T& key) //B+树删除函数,root根节点指针,head叶节点顺序链头节点指针 { BPlusTreeNode<T>* current = root; stack<pair<BPlusTreeNode<T>*, vector<pair<T, BPlusTreeNode<T>*>>::iterator>> stackforback; while (current->NodeFlag != BPlusTreeNode<T>::flag::leaf) { typename vector<pair<T, BPlusTreeNode<T>*>>::iterator scankey = Upper_Bound(key, *(current->keyptrmap)); if (scankey == current->keyptrmap->end()) { cout << "关键码不存在删除失败" << endl; return { root, head }; } stackforback.push(make_pair(current, scankey)); current = scankey->second; } { pair<bool, typename vector<T>::iterator> result = BinarySearch(current->keyandptr->first, current->keyandptr->first.begin(), current->keyandptr->first.end() - 1, key); if (result.first == false) { cout << "关键码不存在删除失败" << endl; return { root, head }; } current->keyandptr->first.erase(result.second); } if (stackforback.empty() == true) { if (current->keyandptr->first.empty() == true) { delete current; return { nullptr, nullptr }; } return { current, current }; } if (current->keyandptr->first.size() >= (M + 1) / 2) { if (current->keyandptr->first.back() < key) updatemax(stackforback, current->keyandptr->first.back()); return { root, head }; } if (borrowFromLeftOrRight(stackforback, current, key)) { return { root, head }; } typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = stackforback.top().second; ++temp; if (temp != stackforback.top().first->keyptrmap->end()) { current->keyandptr->first.insert(current->keyandptr->first.end(), temp->second->keyandptr->first.begin(), temp->second->keyandptr->first.end()); current->keyandptr->second = temp->second->keyandptr->second; delete temp->second; stackforback.top().first->keyptrmap->erase(temp); stackforback.top().second->first = current->keyandptr->first.back(); } else { temp = temp - 2; temp->second->keyandptr->first.insert(temp->second->keyandptr->first.end(), current->keyandptr->first.begin(), current->keyandptr->first.end()); temp->second->keyandptr->second = current->keyandptr->second; temp->first = temp->second->keyandptr->first.back(); delete current; current = nullptr; stackforback.top().first->keyptrmap->erase(stackforback.top().second); } if (afterMerge(stackforback, root, current, temp, key)) return { root, head }; while (true) { if (borrowFromLeftOrRight(stackforback, current, key)) { return { root, head }; } typename vector<pair<T, BPlusTreeNode<T>*>>::iterator temp = stackforback.top().second; ++temp; if (temp != stackforback.top().first->keyptrmap->end()) { current->keyptrmap->insert(current->keyptrmap->end(), temp->second->keyptrmap->begin(), temp->second->keyptrmap->end()); delete temp->second; stackforback.top().second->first = current->keyptrmap->back().first; stackforback.top().first->keyptrmap->erase(temp); } else { temp = temp - 2; temp->second->keyptrmap->insert(temp->second->keyptrmap->end(), current->keyptrmap->begin(), current->keyptrmap->end()); temp->first = temp->second->keyptrmap->back().first; delete current; stackforback.top().first->keyptrmap->erase(stackforback.top().second); typename vector<pair<T, BPlusTreeNode<T>*>>::iterator it = temp->second->keyptrmap->end() - 1; current = nullptr; } if (afterMerge(stackforback, root, current, temp, key)) return { root, head }; } } int main() { const int N = 2000; vector<int> seq(N); for (int i = 0; i < N; ++i) { seq[i] = i + 1; } shuffle(seq.begin(), seq.end(), default_random_engine()); BPlusTreeNode<int>* root = nullptr; BPlusTreeNode<int>* head = nullptr; for (vector<int>::const_iterator p = seq.cbegin(); p != seq.cend(); ++p) { cout << "插入节点" << *p << endl; pair<BPlusTreeNode<int>*, BPlusTreeNode<int>* > temp = BPlusInsert(root, head, *p); root = temp.first; head = temp.second; if (isBPlusTree(root, head)) { cout << "当前树为B+树" << endl; } else { cout << "错误,当前树不为B+树!" << endl; exit(-1); } cout << endl; } for (vector<int>::const_iterator p = seq.cbegin(); p != seq.cend(); ++p) { cout << "删除节点" << *p << endl; pair<BPlusTreeNode<int>*, BPlusTreeNode<int>* > temp = BPlusDelete(root, head, *p); root = temp.first; head = temp.second; if (root == nullptr && head == nullptr) cout << "NULL"; else { if (isBPlusTree(root, head)) { cout << "当前树为B+树" << endl; } else { cout << "错误,当前树不为B+树!" << endl; exit(-1); } } cout << endl; } return 0; }