B-树
1.多路平衡查找
多路搜索树
具体地如图8.10所示,比如可以两层为间隔,将各节点与其左、右孩子合并为“大节点”，每个“大节点”拥有四个分支,故称作四路搜索树。一般地,以k层为间隔如此重组,可将二叉搜索树转化为等价的2^k路搜索树,统称多路搜索树(multi-way search tree)。
多路平衡搜索树
所谓m阶B-树 (B-tree),即m路平衡搜索树(m >= 2),其宏观结构如图
4阶B树：即2-3-4树
2.ADT接口及其实现
B-树节点BTNode类：
#include "../vector/vector.h"
#define BTNodePosi(T) BTNode<T>* //B-树节点位置
template <typename T> struct BTNode { //B-树节点模板类
// 成员(为简化描述起见统一开放,读者可根据需要进一步封装)
BTNodePosi(T) parent; //父节点
Vector<T> key; //关键码向量
Vector<BTNodePosi(T)> child; //孩子向量(其长度总比key多一)
// 构造函数(注意:BTNode只能作为根节点创建,而且初始时有0个关键码和1个空孩子指针)
BTNode() { parent = NULL; child.insert(0, NULL); }
BTNode(T e, BTNodePosi(T) lc = NULL, BTNodePosi(T) rc = NULL) {
parent = NULL; //作为根节点,而且初始时
key.insert(0, e); //只有一个关键码,以及
child.insert(0, lc); child.insert(1, rc); //两个孩子
if (lc) lc->parent = this; if (rc) rc->parent = this;
}
};
同一节点的所有孩子组织为一个向量,各相邻孩子之间的关键码也组织为一个向量。按照B-树的定义,孩子向量的实际长度总是比关键码向量多一。
B-树模板类
#include "BTNode.h" //引入B-树节点类
template <typename T> class BTree { //B-树模板类
protected:
int _size; //存放的关键码总数
int _order; //B-树的阶次,至少为3——创建时指定,一般不能修改
BTNodePosi(T) _root; //根节点
BTNodePosi(T) _hot; //BTree::search()最后访问的非空(除非树空)的节点位置
void solveOverflow(BTNodePosi(T)); //因插入而上溢之后的分裂处理
void solveUnderflow(BTNodePosi(T)); //因删除而下溢之后的合并处理
public:
BTree(int order = 3) : _order(order), _size(0) //构造函数:默认为最低的3阶
{ _root = new BTNode<T>(); }
~BTree() { if (_root) release(_root); } //析构函数:释放所有节点
int const order() { return _order; } //阶次
int const size() { return _size; } //规模
BTNodePosi(T) & root() { return _root; } //树根
bool empty() const { return !_root; } //判空
BTNodePosi(T) search(const T& e); //查找
bool insert(const T& e); //插入
bool remove(const T& e); //删除
}; //BTree
3.关键码查找
算法
一般地如图8.13所示,可以将大数据集组织为B-树并存放于外存。对于活跃的B-树,其根节点会常驻于内存;此外,任何时刻通常只有另一节点(称作当前节点)留驻于内存。
与二叉搜索树的不同之处在于,因此时各节点内通常都包含多个关键码,故有可能需要经过(在内存中的)多次比较,才能确定应该转向下一层的哪个节点并继续查找。
实现代码：节点内部的查找直接借用了有序向量的search()接口
template <typename T> BTNodePosi(T) BTree<T>::search(const T& e) { //在B-树中查找关键码e
BTNodePosi(T) v = _root; _hot = NULL; //从根节点出发
while (v) { //逐层查找
Rank r = v->key.search(e); //在当前节点中,找到不大于e的最大关键码
if ((0 <= r) && (e == v->key[r])) return v; //成功:在当前节点中命中目标关键码
_hot = v; v = v->child[r + 1]; //否则,转入对应子树(_hot指向其父)——需做I/O,最费时间
} //这里在向量内是二分查找,但对通常的_order可直接顺序查找
return NULL; //失败:最终抵达外部节点
}
代码8.8 B-树关键码的查找
与二叉搜索树的实现类似,这里也约定查找结果由返回的节点位置指代:成功时返回目标关键码所在的节点,上层调用过程可在该节点内进一步查找以确定准确的命中位置;失败时返回对应外部节点,其父节点则由变量_hot指代。
复杂度：每次查找过程共需访问O(log m N)个节点,相应地需要做O(log m N)次外存读取操作。由此可知,对存有N个关键码的m阶B-树的每次查找操作,耗时不超过O(log m N)。
4.关键码插入
template <typename T> bool BTree<T>::insert(const T& e) { //将关键码e插入B树中
BTNodePosi(T) v = search(e); if (v) return false; //确认目标节点不存在
Rank r = _hot->key.search(e); //在节点_hot的有序关键码向量中查找合适的插入位置
_hot->key.insert(r + 1, e); //将新关键码插至对应的位置
_hot->child.insert(r + 2, NULL); //创建一个空子树指针
_size++; //更新全树规模
solveOverflow(_hot); //如有必要,需做分裂
return true; //插入成功
}
代码8.9 B-树关键码的插入
按照代码8.8的出口约定,查找过程必然终止于某一外部节点v,且其父节点由变量_hot指示。接下来,在该节点中再次查找目标关键码e。尽管这次查找注定失败,却可以确定e在其中的正确插入位置r。最后,只需将e插至这一位置。
5.上溢与分裂
算法
一般地,刚发生上溢的节点,应恰好含有m个关键码。若取s = [m/2] ,则它们依次为:
{ k 0 , ..., k s-1 ;k s ;k s+1 , ..., k m-1 }
可见,以k s 为界,可将该节点分前、后两个子节点,且二者大致等长。于是,可令关键码k s上升一层,归入其父节点(若存在)中的适当位置,并分别以这两个子节点作为其左、右孩子。这一过程,称作节点的分裂(split)。
实例：
如图(a1)所示,设原上溢节点的父节点存在,且足以接纳一个关键码。此种情况下,只需将被提升的关键码(37)按次序插入父节点中,修复即告完成,修复后的局部如图(a2)所示。
如图(b1)所示,尽管上溢节点的父节点存在,但业已处于饱和状态。此时如图(b2),在强行将被提升的关键码插入父节点之后,尽管上溢节点也可得到修复,却会导致其父节点继而发生上溢这种现象称作上溢的向上传递。好在每经过一次这样的修复,上溢节点的高度都必然上升一层。这意味着上溢的传递不至于没有尽头,最远不至超过树根。
如图(c1)所示,若上溢果真传递至根节点,则可令被提升的关键码(37)自成一个节点,并作为新的树根。
实现代码：
template <typename T> //关键码插入后若节点上溢,则做节点分裂处理
void BTree<T>::solveOverflow(BTNodePosi(T) v) {
if (_order >= v->child.size()) return; //递归基:当前节点并未上溢
Rank s = _order / 2; //轴点(此时应有_order = key.size() = child.size() - 1)
BTNodePosi(T) u = new BTNode<T>(); //注意:新节点已有一个空孩子
for (Rank j = 0; j < _order - s - 1; j++) { //v右侧的_order-s-1个孩子及关键码分裂为右侧节点u
u->child.insert(j, v->child.remove(s + 1)); //逐个移动效率低
u->key.insert(j, v->key.remove(s + 1)); //此策略可改进
}
u->child[_order - s - 1] = v->child.remove(s + 1); //移动v最靠右的孩子
if (u->child[0]) //若u的孩子们非空,则
for (Rank j = 0; j < _order - s; j++) //将它们的父节点统一
u->child[j]->parent = u; //指向u
BTNodePosi(T) p = v->parent; //v当前的父节点p
if (!p) { _root = p = new BTNode<T>(); p->child[0] = v; v->parent = p; } //若p为空则创建之
Rank r = 1 + p->key.search(v->key[0]); //p中指向u的指针的秩
p->key.insert(r, v->key.remove(s)); //轴点关键码上升
p->child.insert(r + 1, u); u->parent = p; //新节点u与父节点p互联
solveOverflow(p); //上升一局,如有必要则继续分裂——至多递归O(logn)局
}
代码8.10 B-树节点的上溢处理
实例：
6.关键码删除
template <typename T> bool BTree<T>::remove(const T& e) { //从BTree树中删除关键码e
BTNodePosi(T) v = search(e); if (!v) return false; //确认目标关键码存在
Rank r = v->key.search(e); //确定目标关键码在节点v中的秩(由上,肯定合法)
if (v->child[0]) { //若v非叶子,则e的后继必属于某叶节点
BTNodePosi(T) u = v->child[r+1]; //在右子树中一直向左,即可
while (u->child[0]) u = u->child[0]; //找出e的后继
v->key[r] = u->key[0]; v = u; r = 0; //并与之交换位置
} //至此,v必然位于最底局,且其中第r个关键码就是待删除者
v->key.remove(r); v->child.remove(r + 1); _size--; //删除e,以及其下两个外部节点之一
solveUnderflow(v); //如有必要,需做旋转或合并
return true;
}
代码8.11 B-树关键码的删除
7.下溢与合并
对下溢节点的整个处理过程：
template <typename T> //关键码删除后若节点下溢,则做节点旋转或合并处理
void BTree<T>::solveUnderflow(BTNodePosi(T) v) {
if ((_order + 1) / 2 <= v->child.size()) return; //递归基:当前节点并未下溢
BTNodePosi(T) p = v->parent;
if (!p) { //递归基:已到根节点,没有孩子的下限
if (!v->key.size() && v->child[0]) {
//但倘若作为树根的v已不含关键码,却有(唯一的)非空孩子,则
_root = v->child[0]; _root->parent = NULL; //这个节点可被跳过
v->child[0] = NULL; release(v); //并因不再有用而被销毁
} //整树高度降低一层
return;
}
Rank r = 0; while (p->child[r] != v) r++;
//确定v是p的第r个孩子——此时v可能不含关键码,故不能通过关键码查找
//另外,在实现了孩子指针的判等器之后,也可直接调用Vector::find()定位
// 情况1:向左兄弟借关键码
if (0 < r) { //若v不是p的第一个孩子,则
BTNodePosi(T) ls = p->child[r - 1]; //左兄弟必存在
if ((_order + 1) / 2 < ls->child.size()) { //若该兄弟足够“胖”,则
v->key.insert(0, p->key[r - 1]); //p借出一个关键码给v(作为最小关键码)
p->key[r - 1] = ls->key.remove(ls->key.size() - 1); //ls的最大关键码转入p
v->child.insert(0, ls->child.remove(ls->child.size() - 1));
//同时ls的最右侧孩子过继给v
if (v->child[0]) v->child[0]->parent = v; //作为v的最左侧孩子
return; //至此,通过右旋已完成当前层(以及所有层)的下溢处理
}
} //至此,左兄弟要么为空,要么太“瘦”
// 情况2:向右兄弟借关键码
if (p->child.size() - 1 > r) { //若v不是p的最后一个孩子,则
BTNodePosi(T) rs = p->child[r + 1]; //右兄弟必存在
if ((_order + 1) / 2 < rs->child.size()) { //若该兄弟足够“胖”,则
v->key.insert(v->key.size(), p->key[r]); //p借出一个关键码给v(作为最大关键码)
p->key[r] = rs->key.remove(0); //ls的最小关键码转入p
v->child.insert(v->child.size(), rs->child.remove(0));
//同时rs的最左侧孩子过继给v
if (v->child[v->child.size() - 1]) //作为v的最右侧孩子
v->child[v->child.size() - 1]->parent = v;
return; //至此,通过左旋已完成当前层(以及所有层)的下溢处理
}
} //至此,右兄弟要么为空,要么太“瘦”
// 情况3:左、右兄弟要么为空(但不可能同时),要么都太“瘦”——合并
if (0 < r) { //与左兄弟合并
BTNodePosi(T) ls = p->child[r - 1]; //左兄弟必存在
ls->key.insert(ls->key.size(), p->key.remove(r - 1)); p->child.remove(r);
//p的第r - 1个关键码转入ls,v不再是p的第r个孩子
ls->child.insert(ls->child.size(), v->child.remove(0));
if (ls->child[ls->child.size() - 1]) //v的最左侧孩子过继给ls做最右侧孩子
ls->child[ls->child.size() - 1]->parent = ls;
while (!v->key.empty()) { //v剩余的关键码和孩子,依次转入ls
ls->key.insert(ls->key.size(), v->key.remove(0));
ls->child.insert(ls->child.size(), v->child.remove(0));
if (ls->child[ls->child.size() - 1]) ls->child[ls->child.size() - 1]->parent = ls;
}
release(v); //释放v
} else { //与右兄弟合并
BTNodePosi(T) rs = p->child[r + 1]; //右兄弟必存在
rs->key.insert(0, p->key.remove(r)); p->child.remove(r);
//p的第r个关键码转入rs,v不再是p的第r个孩子
rs->child.insert(0, v->child.remove(v->child.size() - 1));
if (rs->child[0]) rs->child[0]->parent = rs; //v的最左侧孩子过机给ls做最右侧孩子
while (!v->key.empty()) { //v剩余的关键码和孩子,依次转入rs
rs->key.insert(0, v->key.remove(v->key.size() - 1));
rs->child.insert(0, v->child.remove(v->child.size() - 1));
if (rs->child[0]) rs->child[0]->parent = rs;
}
release(v); //释放v
}
solveUnderflow(p); //上升一层,如有必要则继续分裂——至多递归O(logn)层
return;
}
实例：