数据结构：树表的查找之B-树和B+树

线性表和二叉排序树的查找方法，都属于内查找法。内查找法的主要特点是，以结点为单位进行查找，适用于能够存储在计算机内存中较小的文件。当文件很大时，无法全部存储到内存中，采用内查找法，需要反复地进行内、外存交换，查找效率很低，此时最好的方法是使用外查找法。

一、B-树

B-树（或B树），又称多路平衡搜索树，是一棵适用于外查找的平衡多叉树。1970年，由鲁道夫·拜尔（R.Bayer）和E·麦克雷特（E.Mccreight）提出。磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用B-树这种数据结构。

3.1、定义

一棵m $(m \ge 3)$ 阶的B-树，或是空树，或是满足下列特性的m叉树：

树中每个结点最多有m棵子树；
若根结点不是叶子结点，则至少有两棵子树；
除根之外的所有非终端结点至少有 $\lceil m/2 \rceil$ 棵子树；
所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点（注：失败结点并不存在，指向这些结点的指针为空。引入失败结点是为了便于分析B-树的查找性能）；
所有的非终端结点最多有m-1个关键字。

在B-树中，结点的逻辑结构如下图所示：

其中：

$n(\lceil m/2 \rceil -1 <= n <= m-1)$ 为结点中关键字的个数（或n+1为子树个数）；
$K_i(i=1,2,...n)$ 为关键字，且 $K_i<K_{i+1}(i=1,2,...,n-1)$ ；
$P_i(i=0,1,...,n)$ 为指向子树根结点的指针，且在指针 $P_{i-1}$ 所指向的子树中所有结点的关键字均小于 $K_i$ ，在 $P_n$ 所指向的子树中所有结点的关键字均大于 $K_n$ 。

从上述定义可以看出，对任一关键字 $K_i$ 而言， $P_{i-1}$ 相当于指向其“左子树”， $P_i$ 相当于指向其“右子树”。如下图，是一棵4阶的B-树。

B-树具有平衡、有序、多路的特点。上图所示的树能很好地说明B-树的这些特点。

所有叶子结点均在同一层次，这体现出其平衡的特点。
树中每个结点中的关键字都是有序的，且关键字 $K_i$ 的“左子树”中的关键字均小于 $K_i$ ，而其“右子树”中的关键字均大于 $K_i$ ，这体现出其有序的特点。
除叶子结点外，有的结点中有一个关键字、两棵子树，有的结点中有两个关键字、3棵子树，在4阶的B-树中最多有3个关键字、4棵子树，这体现出其多路的特点。

由于B-树主要用做文件索引，因此它的查找涉及外存的存取，在后面的算法描述中将略去外存的读写，只做示意性描述。在此假设结点类型定义如下：

// B-树的阶，暂设为3
#define m 3

// B-树结点和B-树的类型
typedef struct BTNode {
    // 结点中关键字的个数，即结点的大小
    int keynum;
    // 双亲结点指针
    struct BTNode *parent;
    // 子树指针向量
    struct BTNode *ptr[m+1];
    // 关键字向量，0号单元未用
    KeyType K[m+1];
    // 记录指针向量，0号单元未用
    Record *recptr[m+1];
}BTNode, *BTree;

// B-树的查找结果类型
typedef struct {
    // 指向找到的结点
    BTNode *pt;
    // 关键字在结点中的序号（1..m）
    int i;
    // 查找结果：1表示成功，0表示失败
    int tag;
}Result;

在具体实现时，为记录结点的双亲结点，通常会增加一个parent指针，指向其双亲结点。在B-树中，结点的实际存储结构如下图所示。

3.2、查找

3.2.1、查找过程

B-树的查找过程和二叉排序树的查找过程类似。接下来，我们以下图为例，说明如何在B-树中进行查找。

在这棵B-树中查找关键字47的过程如下：首先从根开始，通过根结点指针t找到结点*a，因结点*a中只有一个关键字，且47>35，若查找的记录存在，则必在指针 $P_1$ 所指的子树内，顺指针找到结点*c，在该结点中有两个关键字（43和78），而43<47<78，若查找的记录存在，则必在指针 $P_1$ 所指的子树中。同样，顺指针找到结点*g，在该结点中顺序查找，找到关键字47，由此，查找成功。

查找不成功的过程也类似，例如，在这棵树中查找23。从根开始，因为23<35，则顺该结点中的指针 $P_0$ 找到结点*b，又因为结点*b中只有一个关键字18，且23>18，所以顺结点中的第二个指针 $P_1$ 找到结点*e。同理，因为23<27，则顺指针往下找，此时因指针所指结点为叶子结点，说明这棵B-树中不存在关键字23，查找失败。

由此可见，在B-树中进行查找的过程是一个顺指针查找结点和在结点中找关键字交叉进行的过程。

3.2.2、算法步骤

在B-树中进行查找的算法步骤为，将给定值key与根结点的各个关键字 $K_1,K_2,...,K_j(1<=j<=m-1)$ 进行比较，由于关键字序列是有序的，所以查找时可采用顺序查找，也可采用折半查找。查找时：

若 $key=K_i(1<=i<=j)$ ，则查找成功；
若 $key<K_1$ ，则顺着指针 $P_0$ 所指向的子树继续向下查找；
若 $K_i<key<K_{i+1}（1<=i<=j-1）$ ，则顺着指针 $P_i$ 所指向的子树继续向下查找；
若 $key>K_j$ ，则顺着指针 $P_j$ 所指向的子树继续向下查找。

在自上而下的查找过程中，如果找到了值为key的关键字，则查找成功；如果直到叶子结点也未找到，则查找失败。

3.2.3、算法描述

如下，是在B-树中进行查找的C语言算法描述：

// 在m阶B-树T中查找关键字key，返回结果(pt, i, tag)
// 若查找成功，则特征值tag=1，在指针pt所指结点中，第i个关键字等于key
// 否则特征值tag=0，等于key的关键字应插入到指针pt所指结点中，第i和第i+1个关键字之间
Result SearchBTree(BTree T, KeyType key) {
    // 初始化（p指向待查结点，q指向p的双亲）
    p=T;q=NULL;found=FALSE;i=0;

    // 待查结点存在，且尚未找到待查关键字
    while(p&&!found) {
        // 在结点的关键字向量（即p->K[1..keynum]）中查找i，使得p->K[i] <= key < p->K[i+1]
        i=Search(p,key);
        // 找到待查关键字
        if(i>0 && p->K[i]==key) found=TRUE
        // 未找到待查关键字
        else {
            q=p;
            p=p->ptr[i];
        }
    }

    // 查找成功
    if(found) return(p, i, 1);
    // 查找不成功，返回key的插入位置信息
    else return(q, i, 0);
}

3.2.4、算法分析

从上述算法描述可见，在B-树中进行查找包含两种基本操作：

在B-树中找结点；
在结点中找关键字。

由于B-树通常存储在磁盘上，因此前一查找操作是在磁盘上进行的（在上述算法中没有体现），而后一查找操作则是在内存中进行的，即在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或折半查找查询等于key的关键字。显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多出很多，因此，在磁盘上进行查找的次数，即待查关键字所在结点在B-树上的层次数，是决定B-树查找效率的首要因素。

现考虑最坏情况，即待查结点在B-树的最下面一层。也就是说，含有N个关键字的m阶B-树的最大深度是多少？

先看一棵3阶的B-树。按B-树的定义，在3阶的B-树中所有非终端结点中最多可有两个关键字，最少有一个关键字（即子树个数为2或3，故又称2-3树）。当关键字个数小于等于2时，树的最大深度为2（即叶子结点层次为2）；若关键字个数小于等于6时，树的最大深度不超过3。反之，若B-树的深度为4，则关键字的个数必须大于等于7（见下图最后一棵树），此时，每个结点都含有可能的关键字的最小数目。

一般情况的分析可类似平衡二叉树进行，先讨论深度为h+1的m阶B-树所具有的最少结点数。

根据B-树的定义，第一层至少有1个结点；第二层至少有2个结点；由于除根之外的每个非终端结点至少有 $\lceil m/2 \rceil$ 棵子树，则第三层至少有 $2(\lceil m/2 \rceil)$ 个结点；依次类推，第h+1层至少有 $2(\lceil m/2 \rceil)^{h-1}$ 个结点。然而第h+1层的结点为叶子结点，若m阶B-树中具有N个关键字，则叶子结点数即查找不成功的结点数为N+1，由此有：

N+1 >= 2*(\lceil m/2 \rceil)^{h-1}

反之：

h<=log_{\rceil m/2 \rceil} (\frac{N+1}{2})+1

这就是说，在含有N个关键字的m阶B-树中进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过 $log_{\rceil m/2 \rceil} (\frac{N+1}{2})+1$ 。

3.3、插入

3.3.1、插入过程

B-树是一棵动态查找树，其生成过程是从空树起，在查找过程中通过逐个插入关键字而得到。

由于，B-树的内部结点中的关键字个数必须大于等于 $\lceil m/2 \rceil -1$ ，因此，每次插入一个关键字不是简单的在树中添加一个叶子结点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1，则插入完成，否则表明结点已满，需要进行结点“分裂”，将此结点在同一层分成两个结点。

一般情况下，结点分裂方法是：以中间关键字为界把结点一分为二，成为两个结点，并把中间关键字向上插入到双亲结点中，若双亲结点已满，则采用同样的方法继续分解。最坏的情况是，一直分解到树根结点，此时B-树高度增加1。

例如，下图是一棵3阶的B-树（图中略去了叶子结点，即F结点），假设需依次插入关键字30、26、85和7。

插入关键字30

首先通过查找确定应插入的位置。由根结点*a起进行查找，确定30应插入在结点*d中，由于*d中关键字数目不超过2（即m−1），故第一个关键字插入完成。如下图，是插入30后的B-树。

插入关键字26

同样地，通过查找确定关键字26也应该插入到结点*d中。由于*d中关键字数目超过2，此时需将*d分裂成两个结点，即关键字26及其前、后两个指针仍保留在结点*d中，关键字37及其前、后两个指针存储到新产生的结点*d'中，关键字30和指示结点*d'的指针插入到其双亲结点中。由于结点*b中的关键字数目没有超过2，则插入完成。如下图，是插入关键字26的过程。

插入关键字85

类似地，在结点*g中插入85之后需分裂成两个结点，而将70插入到结点*g的双亲结点中时，由于结点*e中关键字数目超过2，则再次分裂为结点*e和*e'。如下图，是插入关键字85的过程。

插入关键字7

最后插入关键字7时，结点*c、*b和*a相继分裂，最终生成一个新的根结点*m。如下图，是插入关键字7的过程。

3.3.2、算法步骤

在B-树中插入关键字的算法步骤为：

在B-树中查找给定关键字的记录，若查找成功，则插入操作失败，否则将新记录作为空指针ap插入查找失败的叶子结点的上一层结点（由q指向）。
若插入新记录和空指针后，q指向的结点的关键字个数未超过m-1，则插入操作成功，否则转入第3步；
以该结点的第 $\lceil m/2 \rceil$ 个关键字 $K_{\lceil m/2 \rceil}$ 为拆分点，将该结点分成3个部分： $K_{\lceil m/2 \rceil}$ 左边部分、 $K_{\lceil m/2 \rceil}$ 、 $K_{\lceil m/2 \rceil}$ 右边部分。 $K_{\lceil m/2 \rceil}$ 左边部分仍然保留在原结点中； $K_{\lceil m/2 \rceil}$ 右边部分存放在一个新创建的结点（由ap指向）中；关键字为 $K_{\lceil m/2 \rceil}$ 的记录和指针ap插入q的双亲结点。因q的双亲结点增加一个新的记录，所以必须对q的双亲结点重复第2步和第3步的操作，依此类推，直至由q指向的结点是根结点，转入第4步。
由于根结点无双亲，则由其分裂产生的两个结点的指针ap和q，以及关键字为 $K_{\lceil m/2 \rceil}$ 的记录构成一个新的根结点。此时，B-树的高度增加1。

3.3.3、算法描述

如下，是在B-树中进行插入的C语言算法描述：

// 在m阶B-树T中结点*q的K[i]与K[i+1]之间插入关键字key
// 若引起结点过大，则沿双亲链进行必要的结点分裂调整，使树T仍是m阶B-树
// q和i是由查找算法SearchBTree返回的信息而得
Status InsertBTree(BTree &T, KeyType key, BTree q, int i) {
    // 初始情况下，x为待插入关键字，ap为一个空指针
    x=key;ap=NULL;finished=FALSE;

    while(q && !finished) {
        // 将x和ap分别插入到q->key[i+1]和q->ptr[i+1]
        Insert(q, i, x, ap);
        // 插入完成
        if(q->keynum<m) finished=TRUE;
        // 分裂结点
        else {
            // 将q->K[s+1..m],q->ptr[s..m]和q->recptr[s+1..m]移入新结点*ap
            s=(m+1)/2;
            split(q,s,ap);
            x=q->K[s];
            q=q->parent;
            // 在双亲结点*q中查找x的插入位置
            if(q) i=Search(q,x);
        }
    }

    // T是空树（参数q初值为NULL）或根结点分裂为结点*q和*ap
    if(!finished)
        // 生成含信息(T,x,ap)的新的根结点*T，原T和ap为子树指针
        NewRoot(T,q,x,ap);

    return OK;
}

3.4、删除

m阶B-树的删除操作就是从树的某个结点中删除指定关键字及其相邻的指针。

删除关键字时，可能要进行相应地调整，使树仍然满足B-树的定义，即要保证每个结点的关键字数目范围为 $[\lceil m/2 \rceil-1,m]$ 。

删除关键字的同时还要删除与关键字相邻的指针。若待删关键字所在结点为最下层的非终端结点，由于其指针均为空，删除后不会影响其他结点，可直接删除；若待删关键字所在结点不是最下层的非终端结点，则邻近的指针指向一棵子树，不可直接删除。此时可这样处理：用待删除记录右（左）邻指针所指子树中的关键字最小（大）的记录（该记录必定在最下层的非终端结点中）替代待删除记录。采用这种方法，无论待删除的记录所在的结点是否为最下层的非终端结点，都可归结为在最下层的非终端结点中删除记录的情况。

例如，从下图所示的B-树中删去关键字45，可先用结点*f中的50替代45，然后将结点*f中的50删去。

综上，删除操作只需讨论在最下层非终端结点中删除关键字的情形。这有以下3种可能。

待删关键字所在结点中的关键字数目不小于 $\lceil m/2 \rceil$

在这种情况下，只需从待删关键字所在结点中删去关键字 $K_i$ 和其右邻指针 $P_i$ ，树的其他部分不变。例如，从下图所示的B-树中删去关键字12。

待删关键字所在结点中的关键字数目等于 $\lceil m/2 \rceil-1$ ，且与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于 $\lceil m/2 \rceil-1$

在这种情况下，需将待删关键字所在结点的右兄弟（或左兄弟）结点中的最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删关键字所在结点中。例如，从下图所示的B-树中删去关键字50，需将其右兄弟结点*g中的61上移至结点*e中，而将结点*e中的53下移至结点*f，从而使得结点*f和结点*g中关键字数目均不小于 $\lceil m/2 \rceil-1$ ，双亲结点中的关键字数目不变。

待删关键字所在结点和其相邻的兄弟结点中的关键字数目都等于 $\lceil m/2 \rceil-1$ 。

假设待删关键字所在结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针 $P_i$ 所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字 $K_i$ 一起，合并到 $P_i$ 所指兄弟结点中（若没有右兄弟，则合并至左兄弟结点中）。例如，从下图所示B-树中删去53，则应删去结点*f，并将*f的剩余信息（指针“空”）和双亲结点*e中的61一起合并到右兄弟结点*g中。

如果合并操作使双亲结点中关键字数目小于 $\lceil m/2 \rceil-1$ ，则应继续进行合并操作。例如，从下图所示的B-树中删去关键字37之后，双亲结点*b中剩余信息（指针c）应和其双亲结点*a中关键字45一起合并至右兄弟结点*e中。

二、B+树

B+树，是B-树的变形树，多用于文件索引系统。严格来讲，它已经不符合树的定义了。

4.1、B+树和B-树的差异

一棵m阶的B+树和m阶的B-树的差异在于：

有n棵子树的结点中含有n个关键字；
所有的叶子结点包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字大小从小到大顺序链接；
所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。

在B+树中，通常会有两个头指针，一个指向根结点，另一个指向关键字最小的叶子结点。因此，可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。如下图，是一棵3阶的B+树。

4.2、B+树的查找、插入和删除

在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。

查找：若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。B+树查找性能的分析类似于B-树。

B+树不仅能够有效地查找单个关键字，而且很适合查找某个范围内的所有关键字。例如，在B+树上找出范围在[a，b]之间的所有关键字值。处理方法是这样的：通过一次查找，找出关键字a，不管它是否存在，都可以到达可能出现a的叶子结点，然后在叶子结点中查找关键字值等于a或大于a的那些关键字。如果在当前结点中没有发现大于b的关键字，可以使用当前叶子结点的最后一个指针找到下一个叶子结点，并继续进行同样的处理，直至在某个叶子结点中找到大于b的关键字，才停止查找。
插入：仅在叶子结点中进行插入，当结点中的关键字个数大于m时要分裂成两个结点，它们所含关键字的个数分别为 $\lfloor \frac{m+1}{2} \rfloor$ 和 $\lceil \frac{m+1}{2} \rceil$ ；并且，它们的双亲结点中应同时包含这两个结点中的最大关键字。
删除：仅在叶子结点中进行删除，当叶子结点中最大关键字被删除时，其在非终端结点中的值可作为“分界关键字”继续存在。若因删除而使结点中关键字的个数少于 $\lceil m/2 \rceil$ ，则要和兄弟结点合并，该过程和B-树类似。