B树

平衡树算法的扩展，支持对保存在磁盘或网络上的符号表进行外部查找。

概念

又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B数的阶，通常用m表示。

具有以下特性：

• 树中每个结点至多有m棵子树，即至多含有m-1个关键字

• 若根结点不是终端结点，则至少有两颗子树。

• 所有非叶子结点的结构：（见书上所示）

• 所有叶子结点都出现在同一层次上，并且不带信息。（可视为类似于折半查找判定树的查找失败结点，实际上这些结点不存在）

B树是所有结点的平衡因子均等于0的多路平衡查找树。

B树的高度（磁盘存取次数）

一般只讲B树的前两层放入内存中，剩余层级全部放在磁盘中，因此B树的高度就约为每次进行查找的磁盘存取次数。

首先明确B树的高度不包含最后的不带任何信息的叶结点所处的那一层。

假设$n\ge 1$，则对于任意一棵包含n个关键字，高度为h、阶数为m的B树：

• 根据树中关键字个数计算高度满足的范围
• 若让每个结点中的关键字个数达到最少，则容纳同样多关键字的B树高度达到最大。

B树的查找

每个结点具有多路分支。

与二叉树的查找很相似，只是每个结点都是多个关键字的有序表，要在每个结点上根据该结点的子树做多路分支决定。

包含两个基本操作：

• 在B树中找结点
• 在结点内找关键字

B树常存储在磁盘中，因此前一个查找操作是在磁盘上进行的，后一个查找操作是在内存中进行的，即在找到目标结点后，将其读入内存，然后在结点内采用顺序或折半查找方法查找。

B树的插入

将关键字插入B树的过程如下：

• 定位：利用前述的B树查找算法，找出插入该关键字的最低层中的某个非叶结点。
• 插入：每个非失败结点的关键字个数都在区间$[\lceil m/2\rceil-1,m-1]$内，插入后的结点关键字个数小于m，则可以直接插入；插入后的结点关键字大于m-1时，必须对结点进行分裂。

分裂的方法：取一个新结点，在插入key后的原结点，从中间位置（$\lceil m/2\rceil$）将其中的关键字分为两部分，左半部分包含的关键字放入原结点中，右半部分包含的关键字放入新结点中，中间位置（$\lceil m/2\rceil$）的结点插入原结点的父结点中；如果父结点关键字个数也超过了上限，则继续进行这种分裂操作，知道这个过程传到根结点为止，进而使得B树的高度增1。

B树的删除

与插入的操作类似，即要使得删除后结点中关键字的个数$\ge \lceil m/2\rceil-1$，将会涉及结点的合并问题。

• 当被删除关键字k不在终端结点：可以用k的前驱和后继替代k，然后在相应结点中删除该前驱或后继。该前驱或后继必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。
• 当被删除结点在终端结点中时，有以下三种情况：
  • 直接删除关键字。即被删除关键字所在结点的关键字个数$\ge \lceil m/2\rceil$，表明删除后仍满足B树定义。
  • 兄弟够接。被删除前所在结点关键字个数$= \lceil m/2\rceil-1$，且与此结点相邻的兄弟结点的关键字个数$\ge \lceil m/2\rceil$，需要通过父子换位法进行调整，达到新的平衡。
  • 兄弟不够借。被删除前所在结点关键字个数$= \lceil m/2\rceil-1$，且与此结点相邻的兄弟结点的关键字个数$= \lceil m/2\rceil -1$，则要将关键字删除后与左右兄弟结点及双亲结点中的关键字进行合并。合并过程中双亲结点中关键字会-1，若其双亲结点是根结点且关键字个数减少为0，则直接将根结点删除，合并后的新结点成为根结点。

详细例子见书上。

性能

在实际应用中对于适当的阶数M，查找的成本是常数级别的。

B+树

是B树的一种变形。一个m阶B+树要满足以下条件：

• 每个分支结点最多有m棵子树（孩子结点）
• 非叶根节点至少有两棵子树，其他每个分支结点至少有$ \lceil m/2\rceil$棵子树。
• 结点的子树个数与关键字个数相等
• 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排序，并且相邻叶结点按大小顺序相互链接起来。
• 所有分支结点只包含它的子结点中关键字的最大值以及指向其子结点的指针。

通常B+树有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此对B+树进行两种查找运算：

• 从最小关键字开始的顺序查找
• 从根结点开始的多路查找

最后修改于 2021-12-10