8.2 B-Tree

系统存储容量的增长速度 << 应用问题规模的增长速度
不同容量的存储器，访问速度差异悬殊。存储系统多数分级组织(Caching)，最常用的数据尽可能放在更高层、更小的存储器中。
从磁盘中读写1B，与读写1KB速度几乎相同。批量式访问，以页(page)或块(block)为单位，使用缓冲区，最终单位字节的1KB访问时间大大缩短。

#define BUFSIZ 512 // 缓冲区默认容量
int setvbuf(FILE* fp, char* buf, int _Mode, size_t size); // 定制缓冲区（流，缓冲区，_IOFBF | _IOLBF | _IONBF，缓冲区容量）
int fflush(FILE* fp); // 强制清空缓冲区

B-Tree，平衡的多路(multi-way)搜索树，经适当合并得到超级节点，每d代合并m = 2^d路，m - 1个关键码
B-Tree逻辑上与BBST完全等价，多级存储系统中使用可针对外部查找，极大降低I/O次数，充分利用外存对批量访问的高效支持，每下降一层，以超级节点为单位，读入一组关键码
m阶B-Tree，即m路平衡搜索树(m ≥ 2)
external nodes深度相等，internal nodes深度相等
内部节点有不超过m - 1个关键码(K₁ < K₂ < ... < K_n)，不超过m个分支(A₀, A₁, A₂, ... , A_n)
内部节点的分支数不可过少，根节点 $2 \le n+1$ ，其它节点 $\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节点
    BTNodePosi(T) parent; // 父节点
    Vector<T> key; // 数值向量
    Vector<BTNodePosi(T)> child; // 子向量，长度总比key多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); // 初始时仅1个关键码
        child.insert(0, lc);
        child.insert(1, rc); // 2个子节点
        if (lc)
            lc->parent = this;
        if (rc)
            rc->parent = this;
    }
}

#define BTNodePosi(T) BTNode<T>* // B-Tree节点位置
template <typename T> class BTree { // B-Tree
protected:
    int _size; // 关键码总数
    int _order; // 阶次
    BTNodePosi(T) _root; // 根
    BTNodePosi(T) _hot; // search()最后访问的非空节点位置
    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; // 从根节点出发
    while (v) { // 逐层查找
        Rank r = v->key.search(e); // 在当前节点对应向量中顺序查找
        if (0 <= r && e == v->key[r])
            return v; // 若成功，则返回
        _hot = v;
        v = v->child[r + 1]; // 沿引用转至对应的下层子树，并载入其根I/O
    } // 若因!v退出，则抵达外部节点
    return NULL; // 失败
}

最大高度
含N个关键码的m阶B-Tree，各层内部节点数为 $n_{k} = 2 \times \left \lceil m/2 \right \rceil ^{k-1}$
外部节点所在层 $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)$
相对于BBST， $\log_{\left \lceil m/2 \right \rceil }{(N/2)}/\log_{2}{N}=1/(\log_{2}{m}-1)$ ，若取m = 256，则树高（I/O次数）降至约1/7

最小高度
含N个关键码的m阶B-Tree，各层内部节点数为 $n_{h}=m^{h}$
外部节点所在层 $N+1=n_{h} \le m^{h}$ ，可推得 $h \ge \log_{m}{(N+1)} = \Omega (\log_{m}{N})$
相对于BBST， $(\log_{m}{N}-1)/\log_{2}{N}=\log_{m}{2}-\log_{n}{2}\approx 1/\log_{2}{m}$ ，若取m = 256，则树高（I/O次数）降至约1/8

插入

template <typename T> bool BTree<T>::insert(const T & e) {
    BTNodePosi(T) v = search(e);
    if (v)
        return false; // 确认e不存在
    Rank r = _hot->key.search(e); // 在节点_hot中确定插入位置
    _hot->key.insert(r + 1, e); // 将新关键码插入至对应位置
    _hot->child.insert(r + 2, NULL); // 创建一个空子树指针
    _size++;
    solveOverflow(_hot); // 若发生上溢，则分裂
    return true; // 插入成功
}

分裂
设上溢节点中关键码为k₀, k₁, ... , k_m-1
取中位数s = $\left \lfloor m/2 \right \rfloor$ ，以关键码k_s为界划分k₀, ... , k_s-1, k_s, k_s+1, ... , k_m-1
关键码k_s上升一层，并分裂(split)以所得的2个节点作为左右子节点
若上溢节点的父节点已饱和，则在接纳被提升的关键码后上溢，继续分裂
上溢可能持续发生，并逐层向上传播，最坏情况即分裂至根

template <typename T> void BTree::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++) { // 分裂出右侧节点u
        u->child.insert(j, v->child.remove(s + 1)); // v右侧_order-s-1个子节点
        u->key.insert(j, v->key.remove(s + 1)); // v右侧_order-s-1个关键码
    }
    u->child[_order - s -1] = v->child.remove(s + 1); // 移动v最右子节点
    if (u->child[0]) // 若u子节点非空，则统一令其以u为父节点
        for (Rank j = 0; j < _order - s; j++)
            u->child[j]->parent = u;
    BTNodePosi(T) p = v->parent; // v当前父节点p
    if (!p) { // 若p为空，则创建，全树增加1层，新根节点恰好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)); // 轴点关键码上升
    p->child.insert(r + 1, u);
    u->parent = p; // 新节点u与父节点p互联
    solveOverflow(p); // 上升一层，若有必要则继续分裂，至多递归O(logn)层
}

删除

template <typename T> bool BTree<T>::remove(const T & e) {
    BTNodePosi(T) v =search(e);
    if (!v)
        return false; // 确认e存在
    Rank r = v->key.search(e) // 确定e在v中的秩
    if (v->child[0]) { // 若v非叶节点
        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--;
    solveUnderflow(v); // 若发生下溢，则需旋转或合并
    return true;
}

旋转与合并
节点V下溢时，必恰好包含 $\left \lceil m/2 \right \rceil - 2$ 个关键码与 $\left \lceil m/2 \right \rceil - 1$ 个分支
视其左右兄弟节点L与R的规模，可分3种情况处理
(1) 若L存在，且至少包含 $\left \lceil m/2 \right \rceil$ 个关键码，则将P中分界关键码y移至V中（作为最小关键码），将L中最大关键码x移至P中（取代原关键码y），经此旋转后，局部乃至全树重新满足B-Tree条件，下溢修复完毕
(2) 若R存在，且至少包含 $\left \lceil m/2 \right \rceil$ 个关键码，亦可旋转，完全对称
(3) 若L或R不存在，或均不足 $\left \lceil m/2 \right \rceil$ 个关键码，L与R仍必有其一（以L为例），且恰含� $\left \lceil m/2 \right \rceil - 1$ 个关键码，从P中抽取介于L与V之间的分界关键码y，通过y粘接，将L与V合成一个节点，同时合并此前y的子节点引用
此处下溢得以修复，但可能继而导致P下溢，若如此，则继续旋转或合并
下溢可能持续发生并向上传播，但至多不超过O(h)层

template <typename T> void BTree<T>::solveUnderflow(BTNodePosi(T) v) { // 下溢修复
    if ((_order + 1) >> 1 <= v->child.size())
        return; // v未下溢
    BTNodePosi(T) p = v->parent;
    if (!p) { // 已至根节点
        if (!v->key.size() && v->child[0]) { // 若v已经不含有关键码，但有唯一的非空child时
            _root = v->child[0];
            _root->par = NULL; // 跳过该节点
            v->child[0] = NULL;
            release(v);  // 释放v
        } // 树高减1
        return;
    }
    Rank r = 0;
    while (p->child[r] != v)
        r++; // 确定v是p的第r个子节点
    if (0 < r) { // 若v不是p的第1个子节点
        BTNodePosi(T) ls = p->child[r - 1]; // 则左兄弟节点必存在
        if ((_order + 1) >> 1 < 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，作v最左子节点
            if (v->child[0])
                v->child[0]->parent = v; // 调整指针
            return; // 至此，通过右旋已完成当前层（及所有层）的下溢处理
        }
    }
    if (p->child.size() - 1 > r) { // 若v不是p的最后1个子节点
        BTNodePosi(T) rs = p->child[r + 1]; // 则右兄弟节点必存在
        if ((_order + 1) >> 1 < rs->child.size()) { // 若右兄弟节点数量足够多
            v->key.insert(v->key.size(), p->key[r]); // 则p借出一个关键码给v，作为最大关键码
            p->key[r] = rs->key.remove(0); // rs最小关键码转入p
            v->child.insert(v->child.size(), rs->child.remove(0)); // 同时rs最左子节点给v，作v最右子节点
            if (v->child[v->child.size() - 1])
                v->child[v->child.size() - 1]->parent = v; // 调整指针
            return; // 至此，通过左旋已完成当前层（及所有层）的下溢处理
    }
    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); // 合并后该局部的根已空，因此释放，合并后节点作为新的根
    } else { // 与右兄弟节点合并
        BTNodePosi(T) rs = p->child[r + 1]; // 右兄弟节点必存在
        rs->key.insert(0, p->key.remove(r));
        p->child.remove(r); // p的第r个关键码转入rs
        rs->child.insert(0, v->child.remove(v->child.size() - 1));
        if (rs->child[0] // v最右子节点给rs，作最左子节点
            rs->child[0]->parent = rs;
        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); // 合并后该局部的根已空，因此释放，合并后节点作为新的根
    }
    solveUnderflow(p); // 上升1层，继续分裂，至多递归O(logn)层
    return;
}