1 B-树的由来

从严格意义上将，B-树并不是 二叉搜索树（因为它包含多个分支），但从逻辑上讲它依然等效于之前所讲的二叉搜索树。

B树最初的功能主要在于弥合 不同存储级别之间在访问速度上的巨大差异，也就是实现高效的I/O。

1.1 越来越小的内存

我们知道 系统存储容量的增长速度 远小于 应用问题规模的增长速度。

比如：

• 在1980年，一个数据库容量大概为10MB，当时电脑的内存容量大致为1MB。10MB / 1MB =``10；
• 在2010年，一个数据库容量大概为1TB，当时电脑的内存容量大致为1GB。1TB / 1GB =``1000；

可以看出，相对来说内存容量是在减少的。

但是内存容量为何不能更大？
答：在物理上，存储器的容量 越大，访问速度越慢。所以，为了使得访问速度更快，就不得不舍弃存储器的一部分容量。
**

1.2 高速缓存

1.2.1 事实1：不同容量的存储器，访问速度差异悬殊。

• 以磁盘与内存为例：ms /ns > 10^5 ，二者访问速度的差异相差10^5左右。
  • 如果内存的一次访问为1s，则一次外存访问就相当于1天。

所以，为了避免一次磁盘的访问，我们宁可访问1000次内存。这也是为什么大多数的存储系统，都是分级组织的，如下图：

存着层次的深入，存储器的容量越来越大；但反过来访问速度也越来越低。

这样的，分级结构之所以能够高效运转，在于其采取的策略：

• 最常用的数据尽可能的放在更高层、更小的存储器中；
• 是在找不到，才向更底层、更大的存储器索取。

两个相邻存储级别之间的数据传输，统称为I/O操作。因各级存储器的访问速度相差悬殊，故应尽可能减少I/O操作。

1.2.2 事实2：从磁盘中读写1B，与读写1KB几乎一样快

类似于，人在武汉，去广州采购粉笔，采购一支粉笔 与 采购1箱粉笔 所花费的时间成本几乎是一样的。

典型的存储系统，采用批量式访问：以页（page）或块（block）为单位，使用缓冲区。

2 多路搜索树

当数据规模大到内存已不足以容纳时，常规平衡二叉搜索树的效率将大打折扣。其原因在于，查找过程对外存的访问次数过多。例如，若将10^9个记录在外存中组织为AVL树，则每次查找大致需做30次外存访问。那么，如何才能有效减少外存操作呢?
为此，需要充分利用磁盘之类外部存储器的另一特性：就时间成本而言，读取物理地址连续的一千个字节，与读取单个字节几乎没有区别。既然外部存储器更适宜于批量式访问，不妨通过时间成本相对极低的多次内存操作，来替代时间成本相对极高的单次外存操作。相应地，需要将通常的二叉搜索树，改造为多路搜索树——在中序遍历的意义下，这也是一种等价变换。

具体地如图8.10所示，

• 比如可以两层为间隔，将各节点与其左、右孩子合并为“大节点”；
• 原节点及其孩子的共三个关键码予以保留；
• 孩子节点原有的四个分支也予以保留并按中序遍历次序排列；
• 节点到左、右孩子的分支转化为“大节点”内部的搜索，在图中表示为水平分支。

如此改造之后，每个“大节点”拥有四个分支，故称作四路搜索树。

这一策略还可进一步推广，比如以三层为间隔，将各节点及其两个孩子、四个孙子合并为含有七个关键码、八个分支的“大节点”，进而得到八路搜索树。一般地，以k层为间隔如此重组，可将二叉搜索树转化为等价的2^k路搜索树，统称多路搜索树(multi-way search tree）。

多路搜索树也支持查找等操作，且效果与原二叉搜索树完全相等。但是，其对外存的访问方式已经发生变化，实际上，在此时的搜索每下降一次，都以“大节点”为单位从外存读取一组（而不再是单个）关键码。这组关键码在逻辑上和物理上都彼此响铃故可以批量方式从外存一次性读出，且所需时间与读取单个关键码几乎一样。

• 具体多大一组，要视存盘的数据块大小而定：m = #key / pg
  • 比如，目前多数数据库系统采用 m = 200~300。

2.1 多路平衡搜索树

所谓m阶B-树(B-tree），即m路平衡搜索树(m ≥ 2），其宏观结构如图8.11所示。

外部节点+叶子：

• 外部节点的深度 统一。
  • 约定，以此深度作为树高h。
• 叶节点的深度统一相等（为h-1）

内部节点：

• 各含 n≤ m-1 个关键码：
• 各含 n+1≤ m 个分支：
  • 分支数也不能太少：
    • 
    • 

从而可以算出：

• 关键码（节点）数：
  • 树根：1 ≤ 节点数 ≤ m-1 （分支数 = 节点数+1）
  • 其余内部节点：┌m/2┐ - 1`` ≤ 节点数 ≤ m-1（分支数 = 节点数+1）

所以，m阶B-树 也称作：（其中的，各内部节点的分支数在┌m/2┐~m之间（包括边界））

• 如：(3,5)-树；(9,18)-树。

2.2 B-树的高度、宽度、表示形式

高度：
在计算B-树的高度时还需要计入其最底层的外部节点。

如上图，的高度其实等于：3（注意：叶节点的高度为0）

但是，我们看它不应该高度为2吗？✖；因为它还隐藏着外部节点没画出来，其实上图的完全形式如下图说是：

宽度：
B-树的宽度：（亦即 最底层外部节点的数目）。

• 如上图的宽度为：15；

B-树的宽度往往远大于其高度。因此，我们需要简化其中分支的画法，冰砖而采用如图（b）的紧凑形式。

2.3 查找

对于活跃的B-树，其树根节点会常驻与内存中。

B-树的查找过程，与二叉搜索树的查找过程类似：

• 首先，以根节点作为当前节点，逐层深入。若当前节点（所包含的一组关键码）中 找到了目标关键码，则查找成功。
• 否则（在当前节点中查找失败），则必可以在当前节点中确定某一个引用（失败 的位置），并通过该位置转至逻辑上处于下一层的另一个节点。若该节点不是外部节点，则将其载入内存中并更新为当前节点，然后继续重复上述过程。

如下图所示：

template<class T>
BTNodePosi<T> BTree<T>::search1(const T& e)
{
    BTNodePosi<T> v = root();     hot_ = nullptr; //从根节点出发
    while (v)
    {
        Rank r = v->key_.search(e); //在当前节点中，找到不大于e的最大关键码
                                    //注：此处的search()函数是头文件“vector.h”中的，
                                    //该函数本身定义的就是顺序查找不超过e的元素【详情请看：dsacpp（原版代码）】
        if ((r >= 0) && (v->key_[r] == e)) //成功找到该关键码
            return v; //返回该关键码所在的节点
                      //（该关键码在这个节点的具体位置是 上层调用过程进一步查找 找到的。这里我们不用管它在该节点的具体位置）
        else // 否则（未命中），进入下一层继续查找
        {
            hot_ = v;
            v = v->child_[r + 1]; //转入对应子树（hot_指向子树的父亲）——需要做I/O
        }
    }
    return NULL; //失败：最终抵达外部节点
}

2.3.1 性能分析：最大、最小树高

若存有N个关键码的m阶B树的高度为h，则必有：
（8-1）
最大树高：

最小树高：

2.3.2 复杂度

因此，每次查找过程共需访问个节点，相应的要做次外存读取操作。由此可知，对存有N个关键码的m阶B-树的每次查找操作，耗时不超过。

所用到的公式：对数函数的 换底公式、倒数公式【https://baike.baidu.com/item/%E5%AF%B9%E6%95%B0%E5%87%BD%E6%95%B0/6013318?fr=kg_qa】

2.4 插入

为在B-树中插入一个新的关键码e：

• 首先调用search(e)在树中查找该关键码。若查找成功，则按照“禁止重复关键码”的约定不予插入，操作即告完成并返回false。
• 否则，按照“2.3 查找”代码 的出口约定，查找过程必然终止于某一外部节点v，且其父节点由变量hot_指示。当然，此时的hot_必然指向某一叶节点（可能同时也是根节点）。
• 接下来，在该节点中再次查找目标关键码e。尽管这次查找注定失败，却可以确定e在其中的正确插入位置r。
• 最后，只需将e插至这一位置。

• 至此，hot_所指的节点中增加了一个关键码。若该节点内关键码的总数依然合法（即不超过m - 1个），则插入操作随即完成。否则，称该节点发生了一次上溢（overflow），此时需要通过适当的处理，使该节点以及整树重新满足B-树的条件。由代码8.9可见，这项任务将借助调整算法**solveOverflow(hot_)**来完成。 ```cpp /**插入**/ template bool BTree::insert1(const T& e) { BTNodePosi v = search1(e); if (v) return false; //如果已经查到原树中已经存在关键码e。

                      //按照“禁止关键码重复原则”，此时就不能再插入了

  //(else) 如果search1(e)的结果为空，则说明原树中不存在关键码e，可以插入。 // 此时，虽然返回的是外部节点v，但是其父节点也已经被记录下来了即hot Rank r = hot->key.search(e); //在节点hot的有序关键码中查找何时的插入位置 hot->key.insert(r + 1, e); //将新关键码插入相应的位置 hot->child.insert(r + 2, nullptr); //创建一个空子树指针

  size++; //更新全树规模 solveOverflow(hot); //如果有上溢情况，则需要处理

  return true; //插入成功 }

<a name="Fv1Dd"></a>
### 2.4.1 上溢与分裂
一般地，刚发生上溢的节点，应恰好含有m个关键码。若取中位数![](https://cdn.nlark.com/yuque/__latex/4f3deed8feef3575e204e6c588f61904.svg#card=math&code=s%3D%5Clfloor%20m%2F2%20%5Crfloor&height=20&width=77)，则它们依次为：<br />![image.png](https://cdn.nlark.com/yuque/0/2020/png/1282860/1599294706549-6801200e-50e9-4ade-8702-5b55d5764db1.png#align=left&display=inline&height=41&margin=%5Bobject%20Object%5D&name=image.png&originHeight=41&originWidth=455&size=20151&status=done&style=stroke&width=455)<br />然后，以关键码KS为界划分为：<br />![image.png](https://cdn.nlark.com/yuque/0/2020/png/1282860/1599294783513-3c1b6bce-d84c-460d-bc59-2f5ce10218de.png#align=left&display=inline&height=36&margin=%5Bobject%20Object%5D&name=image.png&originHeight=36&originWidth=412&size=3925&status=done&style=stroke&width=412)<br />关键码KS上升一层，并**分裂（split），**以所得的两个节点作为左、右孩子
> 左、右孩子所含关键码数目，依然符合m阶B-树的条件


若上溢节点的父亲本已饱和，则在接纳被提升的关键码之后，也将上溢，需要**再次分裂**

- 此时，大可套用前法，继续分裂。
   - 上溢可能持续发生，并逐层向上传播。（纵然最坏情况，亦不过到根 //若果真抵达树根...）
> 这里注意，**当上溢传播至树根时：原树根分裂之后，新创建的树根仅含单个关键码**。


从而，我们也可以看出，**B-树长高的唯一可能情况就是：上溢传播至树根**。<br />![image.png](https://cdn.nlark.com/yuque/0/2020/png/1282860/1599295306343-113793fd-2929-469f-b3f9-196fd89495d7.png#align=left&display=inline&height=460&margin=%5Bobject%20Object%5D&name=image.png&originHeight=460&originWidth=873&size=90173&status=done&style=stroke&width=873)
```cpp
template<typename T>
void BTree<T>::solveOverflow(BTNodePosi<T> v)
{
    if (order() >= v->key_.size()) return; //递归基：当前节点并未上溢

    Rank s = order_ / 2; //轴点（此时应有 order_ = v.size() = child_.size() -1）
    BTNodePosi<T> u = new BTNode<T>(); //注意：新节点已有一个空孩子

    //接下来该将轴点右侧的关键码一起组成一个新节点u
    for (Rank i = 0; i < order_ - s - 1; i++) //v右侧的order_-s-1个孩子及关键码 分裂为右侧节点u
    {
        u->child_.insert(i, v->child_.remove(s + 1));
        u->key_.insert(i, v->key_.remove(s + 1));
    }
    u->child_.insert(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

    // 由于在将v节点从轴点（不包含轴点）开始的右侧关键码 组成新节点u的同时，也将这些关键码从节点v中remove掉了
    // 所以，不需要再新建节点来表示v中的周丹左侧关键码组了
    BTNodePosi<T> p = v->parent_; //p为v节点当前的父亲
    if (!p) //如果p空（此时对应一直上溢传播至树根，因为树根的父亲为空），则创建之
    {
        root_ = p = new BTNode<T>();
        p->child_[0] = v;
        v->parent_ = p;
    }
    Rank r = 1 + p->key_.search(v->key_[0]); // p中指向u的指针的秩(因为p实际上就是轴点关键码上升之后所在的节点）
                                             // 所以，“p->key_.search(v->key_[0])”表示轴点 左侧部分节点（代码中是remove掉轴点右侧关键码后的v），
                                             // 在节点p中的第几个分支（即 它的秩）
                                             // 然后，再 +1 就得到 轴点右侧部分组成的节点（代码中是u）在p节点中的第几个分支（即 它的秩）
    p->key_.insert(r, v->key_.remove(s)); //将轴点关键码上溢
    p->child_.insert(r + 1, u); //新节点u与父节点p互联


    solveOverflow(p); //上升一层，如有必要则继续分裂——至多递归O(logn)次
}

可见整个过程中所做分裂操作的次数，必不超过全树的高度：【根据2.3.1 小节】

2.4.2 复杂度

2.5 删除

为从B-树中删除关键码e：

• 也首先需要调用search(e)查找e所属的节点。倘若查找失败，则说明关键码e尚不存在，删除操作即告完成；
• 否则按照“2.3 查找”代码 的出口约定，目标关键码所在的节点必由返回的位置v指示。此时，通过顺序查找，即可进一步确定e在节点v中的秩r。

• 然后，需要考虑节点v的位置：

  • 如果v正好在叶节点上（内部节点的最深层），那么直接删除；
  • 如果v不在叶节点上，则需要找出其直接前驱（或者直接后继。这里不妨找其后继）。找到其直接后继之后（该后继一定位于叶节点处），将关键码e与其直接后继的关键码u[0] 互换位置，然后删除此时e所在的位置；

    如此，节点v中所含的关键码以及（空）分支将分别减少一个。

• 最后，还要看删除后的那个节点是否符合B-树的规定（即该节点的关键码的数量是否满足要求）：

  • 若该节点所含关键码的总数依然合法（即不少于[m/21- 1)，则删除操作随即完成。

  • 否则，称该节点发生了下溢(underflow），并需要通过适当的处置，使该节点以及整树重新满足B-树的条件。这项任务将借助调整算法solveUnderflow(v)来完成。

    /**************************************删除********************************************/
    template<class T>
    bool BTree<T>::remove1(const T& e)
    {
    BTNodePosi<T> v = search1(e); if (!v) return false; //当查找失败时，说明原树根本不存在该关键码
    
    Rank r = v->key_.search(e); //找到关键码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;
    }
    

2.5.1 下溢与合并

其中的合并这一步骤，合并后节点的关键码总数也不会超过m-1。即合并后该节点是合法的。

template<typename T>
void BTree<T>::solveUnderflow(BTNodePosi<T> v)
{
    if (ceil(order_ / 2) - 1 <= v->key_.size()) //递归基：当前节点并未下溢
        return;        //其中的ceil(float arg)函数：计算不小于arg的最小整数值

    BTNodePosi<T> p = v->parent_;
    if (!p) //递归基：v已到根节点，没有孩子下限（只需保证根节点关键码最少有一个即可）。p是根节点v的父亲，所以它为空    
    {
        if (!v->key_.size() && v->child_[0]) //所以，要使根节点下溢，就只能是根节点中一个关键码都没有，但是它有（唯一地）非空孩子
        {
            root_ = v->child_[0]; root_->parent_ = nullptr; //此时，只需将其下层非空孩子设置为树根，
            v->child_[0] = nullptr; release(v); //并将原来的根节点删除（销毁）
        }
        return;
    }//整树高度降低一层


    Rank r = 0; while (p->child_[r] != v) ++r; //确定v是p的第r个孩子 —— 此时v可能不含关键码，所以不能通过关键码查找

    //情况1：向左兄弟接关键码（右旋）
    if(r>0) //当v不是p的第一个孩子（此时才有左兄弟），则
    {
        BTNodePosi<T> ls = p->child_[r - 1]; //v的左兄弟必存在
        if (ceil(order_ / 2) =< ls->key_.size())//若该兄弟足够“胖”（即其关键码是大于最低关键码数的）
        {
            v->key_.insert(0, p->key_[r - 1]); //则p借出一个关键码给v
            p->key_[r - 1] = ls->key_.remove(ls->key_.size() - 1); //并将ls的最大关键点转入p
            //同时将ls最后的分支一并转过去
            v->child_.insert(0, ls->child_.remove(ls->child_.size() - 1)); 
            if (v->child_[0]) v->child_[0].parent_ = v;

            return; //至此，通过右旋已完成当前层（以及所有层）的下溢处理
        }
    } //至此，左兄弟要么为空，要么太瘦

    //情况2：向右兄弟接关键码（左旋）
    if (r < p->(child_.size() + 1)) //当v不是p的最后一个孩子（此时才有右兄弟）,
    {
        BTNodePosi<T> rs = p->child_[r + 1]; //找到与v相邻的右兄弟
        if (ceil(order_ / 2) =< rs->child_.size()) //若该兄弟足够“胖”（即其关键码是大于最低关键码数的）
        {
            v->key_.insert(v->key_.size(), p->key_[r]); //则p借出一个关键码给v
            p->key_[r] = rc.key_.remove(0); //并将rs的最小关键点转入p
            //同时将rs第一个的分支一并转过去
            v->child_.insert(v->child_.size(), rc.child_.remove(0));
            if (v->child_[v->child_.size() - 1]) v->child_[v->child_.size() - 1] = v;

            return; //至此，通过左旋已完成当前层（以及所有层）的下溢处理
        }
    }//至此，右兄弟要么为空，要么太瘦

    //情况3：左、右兄弟要么为空（但不可能同时）；要么都太“瘦” ————则需要进行 合并
    if (r > 0) //与左兄弟合并
    {
        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)); //将v的最左侧的分支过继给ls
        if (ls->child_.[ls->child_.size() - 1]) //v的最左侧孩子过继给ls做最右侧孩子
            ls->child_[ls->child_.size() - 1] = ls;

        while (!v->key_.empty())
        {
            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] = ls;
            }
        }
        release(v); //释放v
    }
    else //与右兄弟合并
    {
        BTNodePosi<T> rs = p->child_[r + 1]; //右兄弟
        rs.key_.insert(0, p->key_.remove(r));    p->child_.remove(r);

        rs->child_.insert(0, v->child_.remove(v->child_.size() - 1));//将v的最右侧的分支过继给rs
        if (rs->child_[0])    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] = rs;
            }
        }
        release(v); //释放v
    }

    solveUnderflow(p); //上升一层，如有必要则继续分裂————至多递归 O(logn)层

    return;
}

2.5.2 复杂度