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;
}
執行個體：