约 1300 字

B树

基本概念

B树中，结点中的孩子结点个数的最大值为B树的阶 m，并满足如下一些性质：

  1. 每个结点最多有 $m$ 个子树，最少有 $\lceil m/2 \rceil$ 个分支。特殊的，根结点若不是叶子，则最少有 2 个分支

  2. 若一个结点有 $n-1$ 个关键字，则有 $n$ 个分支。且关键字递增排列。关键字和孩子结点的关系如下：

    p0k1p1k2p2k3p3knpn

    其中，$n$ 为关键字的个数，ki 为关键字且满足ki<ki+1，pi为孩子结点的指针且所指结点的关键字满足 ki<pi<ki+1

  3. 根据1和2，可知结点最多有 $m-1$ 个关键字，最少有 $\lceil m/2 \rceil-1$ 个关键字。（特殊的，根可以只有1个关键字）

  4. 叶子结点处于同一层，可以用空指针表示，是查找失败到达的位置。（也就是叶子结点全都是空结点）

  5. （根据上一条）B树是平衡的

B树的查找

从根结点出发，

  1. 先查找结点内的关键字
  2. 若找不到，则在对应范围内查找

B树的插入

  1. 定位：找到最低层中的某个非叶结点
  2. 插入：若插入后，关键字个数大于 $m-1$（即子树大于 $m$），则分裂，否则完成插入。
  3. 分裂：以 $\lceil m \rceil$ 关键字进行划分，分为两个子结点，然后中间 $\lceil m \rceil$ 关键字则插入到父结点。若父节点超出 $m-1$，则继续分裂。

这个和2-3树是类似的。

B树的建立

  1. 首先确定树的阶数
  2. 先经可能地将根填满到 $m-1$
  3. 然后不断地插入

示例：5阶树

{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}
{11,12,,46,,87,13,10,5,17,9,16,20,3,12,14,18,19,15}
{14,,286,173,,1110,5,17,9,16,20,3,12,14,18,19,15}
{11,02,,54,6177,,98,,1161,,2103,3,12,14,18,19,15}
{15,,21,74,69,,711,608,201,13,,1132,14,18,19,15}
{12,02,,34,6,1,52,11740,,81,89,191,11,51}3,16,17
{13,,21,24,6,1,54,1781,,081,,99,151}116,1317,20
{11,22,134,,148,,651,9,71,518}0,,9111,61317,20
{11,52}3,4,65,7,180,,911,1126,13,1417,18,19,20
1,23,4,65170,8,913,11,112614,1517,18,19,20

B树的删除

若删除的是非终端结点（即不是最低的非空结点），可以用前驱或后继代替，从而转化为删除终端结点的情况。

若删除的是终端结点，

  1. 删除后仍满足关键字个数大于 $\lceil m/2 \rceil-1$，则完成

  2. 反正，则向兄弟结点借，节的过程是：兄弟结点的最大/小值先代替父节点的一个关键字，再将父节点的关键字移到删除结点

    删除65666000,6,空,751777118476846,86

  3. 若兄弟结点不够借（即关键字都刚好是 $\lceil m/2 \rceil-1$），则将被删结点、父结点中的关键字、兄弟结点组合成新结点（此时为 $m-1$ 个关键字）。删除后，父节点的关键字个数少1，若

    1. 父节点是根，且减少为0，则新结点成为新的根