8.2 B-Tree - 簡(jiǎn)書

系統(tǒng)存儲(chǔ)容量的增長(zhǎng)速度 << 應(yīng)用問題規(guī)模的增長(zhǎng)速度
不同容量的存儲(chǔ)器斋配，訪問速度差異懸殊庐杨。存儲(chǔ)系統(tǒng)多數(shù)分級(jí)組織(Caching)咽笼，最常用的數(shù)據(jù)盡可能放在更高層、更小的存儲(chǔ)器中。
從磁盤中讀寫1B袭厂，與讀寫1KB速度幾乎相同墨吓。批量式訪問，以頁(page)或塊(block)為單位纹磺，使用緩沖區(qū)帖烘，最終單位字節(jié)的1KB訪問時(shí)間大大縮短。

#define BUFSIZ 512 // 緩沖區(qū)默認(rèn)容量
int setvbuf(FILE* fp, char* buf, int _Mode, size_t size); // 定制緩沖區(qū)（流橄杨，緩沖區(qū)秘症，_IOFBF | _IOLBF | _IONBF，緩沖區(qū)容量）
int fflush(FILE* fp); // 強(qiáng)制清空緩沖區(qū)

B-Tree讥珍，平衡的多路(multi-way)搜索樹历极，經(jīng)適當(dāng)合并得到超級(jí)節(jié)點(diǎn)，每d代合并m = 2^d路衷佃，m - 1個(gè)關(guān)鍵碼
B-Tree邏輯上與BBST完全等價(jià)，多級(jí)存儲(chǔ)系統(tǒng)中使用可針對(duì)外部查找蹄葱，極大降低I/O次數(shù)氏义，充分利用外存對(duì)批量訪問的高效支持，每下降一層图云，以超級(jí)節(jié)點(diǎn)為單位惯悠，讀入一組關(guān)鍵碼
m階B-Tree，即m路平衡搜索樹(m ≥ 2)
external nodes深度相等竣况，internal nodes深度相等
內(nèi)部節(jié)點(diǎn)有不超過m - 1個(gè)關(guān)鍵碼(K₁ < K₂ < ... < K_n)克婶，不超過m個(gè)分支(A₀, A₁, A₂, ... , A_n)
內(nèi)部節(jié)點(diǎn)的分支數(shù)不可過少，根節(jié)點(diǎn) $2 \le n+1$ 丹泉，其它節(jié)點(diǎn) $\left \lceil m/2 \right \rceil \le n+1$ 情萤，故亦可稱作( $\left \lceil m/2 \right \rceil, m$ )-Tree，例如(2, 4)-Tree

template <typename T> struct BTNode { // B-Tree節(jié)點(diǎn)
    BTNodePosi(T) parent; // 父節(jié)點(diǎn)
    Vector<T> key; // 數(shù)值向量
    Vector<BTNodePosi(T)> child; // 子向量摹恨，長(zhǎng)度總比key多1
    BTNode() {
        parent = NULL;
        child.insert(0, NULL);
    }
    BTNode(T e, BTNodePosi(T) lc = NULL, BTNodePosi(T) rc = NULL) {
        parent = NULL; // 作為根節(jié)點(diǎn)
        key.insert(0, e); // 初始時(shí)僅1個(gè)關(guān)鍵碼
        child.insert(0, lc);
        child.insert(1, rc); // 2個(gè)子節(jié)點(diǎn)
        if (lc)
            lc->parent = this;
        if (rc)
            rc->parent = this;
    }
}

#define BTNodePosi(T) BTNode<T>* // B-Tree節(jié)點(diǎn)位置
template <typename T> class BTree { // B-Tree
protected:
    int _size; // 關(guān)鍵碼總數(shù)
    int _order; // 階次
    BTNodePosi(T) _root; // 根
    BTNodePosi(T) _hot; // search()最后訪問的非空節(jié)點(diǎn)位置
    void solveOverflow(BTNodePosi(T)); // 因插入而上溢后的分裂處理
    void solveUnderflow(BTNodePosi(T)); // 因刪除而下溢后的合并處理
public:
    BTNodePosi(T) search(const T & e); // 查找
    bool insert(const T & e); // 插入
    bool remove(const T & e); // 刪除
}

查找

template <typename T> BTNodePosi(T) BTree<T>::search(const T & e) {
    BTNodePosi(T) v = _root;
    _hot = NULL; // 從根節(jié)點(diǎn)出發(fā)
    while (v) { // 逐層查找
        Rank r = v->key.search(e); // 在當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)向量中順序查找
        if (0 <= r && e == v->key[r])
            return v; // 若成功筋岛，則返回
        _hot = v;
        v = v->child[r + 1]; // 沿引用轉(zhuǎn)至對(duì)應(yīng)的下層子樹，并載入其根I/O
    } // 若因!v退出晒哄，則抵達(dá)外部節(jié)點(diǎn)
    return NULL; // 失敗
}

最大高度
含N個(gè)關(guān)鍵碼的m階B-Tree睁宰，各層內(nèi)部節(jié)點(diǎn)數(shù)為 $n_{k} = 2 \times \left \lceil m/2 \right \rceil ^{k-1}$
外部節(jié)點(diǎn)所在層 $N+1=n_{h}\ge 2\times\left\lceil m/2\right\rceil^{h-1}$ ，可推得 $h\le 1+\log_{\left\lceil m/2\right\rceil}{\left\lfloor\left(N+1\right)/2\right\rfloor}=O\left(\log_{m}{N}\right)$
相對(duì)于BBST寝凌， $\log_{\left \lceil m/2 \right \rceil }{(N/2)}/\log_{2}{N}=1/(\log_{2}{m}-1)$ 柒傻，若取m = 256，則樹高（I/O次數(shù)）降至約1/7

最小高度
含N個(gè)關(guān)鍵碼的m階B-Tree较木，各層內(nèi)部節(jié)點(diǎn)數(shù)為 $n_{h}=m^{h}$
外部節(jié)點(diǎn)所在層 $N+1=n_{h} \le m^{h}$ 红符，可推得 $h \ge \log_{m}{(N+1)} = \Omega (\log_{m}{N})$
相對(duì)于BBST， $(\log_{m}{N}-1)/\log_{2}{N}=\log_{m}{2}-\log_{n}{2}\approx 1/\log_{2}{m}$ ，若取m = 256违孝，則樹高（I/O次數(shù)）降至約1/8

插入

template <typename T> bool BTree<T>::insert(const T & e) {
    BTNodePosi(T) v = search(e);
    if (v)
        return false; // 確認(rèn)e不存在
    Rank r = _hot->key.search(e); // 在節(jié)點(diǎn)_hot中確定插入位置
    _hot->key.insert(r + 1, e); // 將新關(guān)鍵碼插入至對(duì)應(yīng)位置
    _hot->child.insert(r + 2, NULL); // 創(chuàng)建一個(gè)空子樹指針
    _size++;
    solveOverflow(_hot); // 若發(fā)生上溢刹前，則分裂
    return true; // 插入成功
}

分裂
設(shè)上溢節(jié)點(diǎn)中關(guān)鍵碼為k₀, k₁, ... , k_m-1
取中位數(shù)s = $\left \lfloor m/2 \right \rfloor$ ，以關(guān)鍵碼k_s為界劃分k₀, ... , k_s-1, k_s, k_s+1, ... , k_m-1
關(guān)鍵碼k_s上升一層雌桑，并分裂(split)以所得的2個(gè)節(jié)點(diǎn)作為左右子節(jié)點(diǎn)
若上溢節(jié)點(diǎn)的父節(jié)點(diǎn)已飽和喇喉，則在接納被提升的關(guān)鍵碼后上溢，繼續(xù)分裂
上溢可能持續(xù)發(fā)生校坑，并逐層向上傳播拣技，最壞情況即分裂至根

template <typename T> void BTree::solveOverflow(BTNodePosi(T) v) { // 上溢修復(fù)
    if (_order >= v->child.size())
        return; // 不再上溢
    Rank s = _order / 2; // 軸點(diǎn)，此時(shí)_order = key.size() = child.size() - 1
    BTNodePosi(T) u = new BTNode<T>(); // 新節(jié)點(diǎn)已有一個(gè)空子節(jié)點(diǎn)
    for (Rank j = 0; j < _order - s - 1; j++) { // 分裂出右側(cè)節(jié)點(diǎn)u
        u->child.insert(j, v->child.remove(s + 1)); // v右側(cè)_order-s-1個(gè)子節(jié)點(diǎn)
        u->key.insert(j, v->key.remove(s + 1)); // v右側(cè)_order-s-1個(gè)關(guān)鍵碼
    }
    u->child[_order - s -1] = v->child.remove(s + 1); // 移動(dòng)v最右子節(jié)點(diǎn)
    if (u->child[0]) // 若u子節(jié)點(diǎn)非空耍目，則統(tǒng)一令其以u(píng)為父節(jié)點(diǎn)
        for (Rank j = 0; j < _order - s; j++)
            u->child[j]->parent = u;
    BTNodePosi(T) p = v->parent; // v當(dāng)前父節(jié)點(diǎn)p
    if (!p) { // 若p為空膏斤，則創(chuàng)建，全樹增加1層邪驮，新根節(jié)點(diǎn)恰好2度
        _root = p = new BTNode<T>();
        p->child[0] = v;
        v->parent = p;
    }
    Rank r = 1 + p->key.search(v->key[0]); // p中指向u的指針的秩
    p->key.insert(r, v->key.remove(s)); // 軸點(diǎn)關(guān)鍵碼上升
    p->child.insert(r + 1, u);
    u->parent = p; // 新節(jié)點(diǎn)u與父節(jié)點(diǎn)p互聯(lián)
    solveOverflow(p); // 上升一層莫辨，若有必要?jiǎng)t繼續(xù)分裂，至多遞歸O(logn)層
}

刪除

template <typename T> bool BTree<T>::remove(const T & e) {
    BTNodePosi(T) v =search(e);
    if (!v)
        return false; // 確認(rèn)e存在
    Rank r = v->key.search(e) // 確定e在v中的秩
    if (v->child[0]) { // 若v非葉節(jié)點(diǎn)
        BTNodePosi(T) u = v->child[r + 1]; // 則在右子樹中一直向左
        while (u->child[0])
            u = u->child[0]; // 即可找到e的后繼（必屬于葉節(jié)點(diǎn)）
        v->key[r] = u->key[0];
        v = u;
        r = 0; // 并交換位置
    } // 至此v必然位于最底層毅访，且其中第r個(gè)關(guān)鍵碼即待刪除者
    v->key.remove(r);
    v->child.remove(r + 1);
    _size--;
    solveUnderflow(v); // 若發(fā)生下溢沮榜，則需旋轉(zhuǎn)或合并
    return true;
}

旋轉(zhuǎn)與合并
節(jié)點(diǎn)V下溢時(shí)，必恰好包含 $\left \lceil m/2 \right \rceil - 2$ 個(gè)關(guān)鍵碼與 $\left \lceil m/2 \right \rceil - 1$ 個(gè)分支
視其左右兄弟節(jié)點(diǎn)L與R的規(guī)模喻粹，可分3種情況處理
(1) 若L存在蟆融，且至少包含 $\left \lceil m/2 \right \rceil$ 個(gè)關(guān)鍵碼，則將P中分界關(guān)鍵碼y移至V中（作為最小關(guān)鍵碼）守呜，將L中最大關(guān)鍵碼x移至P中（取代原關(guān)鍵碼y）型酥，經(jīng)此旋轉(zhuǎn)后，局部乃至全樹重新滿足B-Tree條件查乒，下溢修復(fù)完畢
(2) 若R存在弥喉，且至少包含 $\left \lceil m/2 \right \rceil$ 個(gè)關(guān)鍵碼，亦可旋轉(zhuǎn)侣颂，完全對(duì)稱
(3) 若L或R不存在档桃，或均不足 $\left \lceil m/2 \right \rceil$ 個(gè)關(guān)鍵碼，L與R仍必有其一（以L為例）憔晒，且恰含? $\left \lceil m/2 \right \rceil - 1$ 個(gè)關(guān)鍵碼藻肄，從P中抽取介于L與V之間的分界關(guān)鍵碼y，通過y粘接拒担，將L與V合成一個(gè)節(jié)點(diǎn)嘹屯，同時(shí)合并此前y的子節(jié)點(diǎn)引用
此處下溢得以修復(fù)，但可能繼而導(dǎo)致P下溢从撼，若如此州弟，則繼續(xù)旋轉(zhuǎn)或合并
下溢可能持續(xù)發(fā)生并向上傳播钧栖，但至多不超過O(h)層

template <typename T> void BTree<T>::solveUnderflow(BTNodePosi(T) v) { // 下溢修復(fù)
    if ((_order + 1) >> 1 <= v->child.size())
        return; // v未下溢
    BTNodePosi(T) p = v->parent;
    if (!p) { // 已至根節(jié)點(diǎn)
        if (!v->key.size() && v->child[0]) { // 若v已經(jīng)不含有關(guān)鍵碼，但有唯一的非空child時(shí)
            _root = v->child[0];
            _root->par = NULL; // 跳過該節(jié)點(diǎn)
            v->child[0] = NULL;
            release(v);  // 釋放v
        } // 樹高減1
        return;
    }
    Rank r = 0;
    while (p->child[r] != v)
        r++; // 確定v是p的第r個(gè)子節(jié)點(diǎn)
    if (0 < r) { // 若v不是p的第1個(gè)子節(jié)點(diǎn)
        BTNodePosi(T) ls = p->child[r - 1]; // 則左兄弟節(jié)點(diǎn)必存在
        if ((_order + 1) >> 1 < ls->child.size()) { // 若左兄弟節(jié)點(diǎn)數(shù)量足夠多
            v->key.insert(0, p->key[r - 1]); // 則p借出一個(gè)關(guān)鍵碼給v婆翔，作為最小關(guān)鍵碼
            p->key[r - 1] = ls->key.remove(ls->key.size() - 1); // ls最大關(guān)鍵碼轉(zhuǎn)入p
            v->child.insert(0, ls->child.remove(ls->child.size() - 1)); // 同時(shí)ls最右子節(jié)點(diǎn)給v拯杠，作v最左子節(jié)點(diǎn)
            if (v->child[0])
                v->child[0]->parent = v; // 調(diào)整指針
            return; // 至此，通過右旋已完成當(dāng)前層（及所有層）的下溢處理
        }
    }
    if (p->child.size() - 1 > r) { // 若v不是p的最后1個(gè)子節(jié)點(diǎn)
        BTNodePosi(T) rs = p->child[r + 1]; // 則右兄弟節(jié)點(diǎn)必存在
        if ((_order + 1) >> 1 < rs->child.size()) { // 若右兄弟節(jié)點(diǎn)數(shù)量足夠多
            v->key.insert(v->key.size(), p->key[r]); // 則p借出一個(gè)關(guān)鍵碼給v啃奴，作為最大關(guān)鍵碼
            p->key[r] = rs->key.remove(0); // rs最小關(guān)鍵碼轉(zhuǎn)入p
            v->child.insert(v->child.size(), rs->child.remove(0)); // 同時(shí)rs最左子節(jié)點(diǎn)給v潭陪，作v最右子節(jié)點(diǎn)
            if (v->child[v->child.size() - 1])
                v->child[v->child.size() - 1]->parent = v; // 調(diào)整指針
            return; // 至此，通過左旋已完成當(dāng)前層（及所有層）的下溢處理
    }
    if (0 < r) { // 與左兄弟節(jié)點(diǎn)合并
        BTNodePosi(T) ls = p->child[r - 1]; // 左兄弟節(jié)點(diǎn)必存在
        ls->key.insert(ls->key.size(), p->key.remove(r - 1));
        p->child.remove(r); // p的第r-1個(gè)關(guān)鍵碼轉(zhuǎn)入ls最蕾，v不再是p的第r個(gè)子節(jié)點(diǎn)
        ls->child.insert(ls->child.size(), v->child.remove(0));
        if (ls->child[ls->child.size() - 1] // v最左子節(jié)點(diǎn)給ls依溯，作最右子節(jié)點(diǎn)
            ls->child[ls->child.size() - 1]->parent = ls;
        while (!v->key.empty()) { // 若v中元素仍非空，則將其余元素依次轉(zhuǎn)入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); // 合并后該局部的根已空瘟则，因此釋放黎炉，合并后節(jié)點(diǎn)作為新的根
    } else { // 與右兄弟節(jié)點(diǎn)合并
        BTNodePosi(T) rs = p->child[r + 1]; // 右兄弟節(jié)點(diǎn)必存在
        rs->key.insert(0, p->key.remove(r));
        p->child.remove(r); // p的第r個(gè)關(guān)鍵碼轉(zhuǎn)入rs
        rs->child.insert(0, v->child.remove(v->child.size() - 1));
        if (rs->child[0] // v最右子節(jié)點(diǎn)給rs，作最左子節(jié)點(diǎn)
            rs->child[0]->parent = rs;
        while (!v->key.empty()) { // 若v中元素仍非空醋拧，則將其余元素依次轉(zhuǎn)入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); // 合并后該局部的根已空慷嗜，因此釋放，合并后節(jié)點(diǎn)作為新的根
    }
    solveUnderflow(p); // 上升1層趁仙，繼續(xù)分裂洪添，至多遞歸O(logn)層
    return;
}