7.7 多层索引树查找

 

7.7  多层索引树查找

7.7.1  B-树

1．B-树的定义

B-树是一种平衡的多路查找树，适用于组织文件的索引（动态索引）。一棵m阶B-树应满足下列条件：

（1）每个节点至多有m棵子树。

（2）根节点至少有两棵子树。

（3）除根节点外，每个分支节点至少有m/2棵子树。

（4）树的叶子节点在最底层。

（5）有k棵子树的分支节点中恰好包含k-1个关键字以及指向记录的指针。

在B-树中，每个分支节点中的关键字从小到大排列。对于含有k-1个关键字（2≤i≤m），并且不是最下面一层的分支节点x来说，其中第i个关键字（1≤i≤k-1）比x的第i棵子树中的所有关键字都大，比x的第i+1棵子树中的所有关键字都小。另外，树叶不包含任何信息（实际上，这些树叶并不存在，分支节点中指向这些树叶的指针域为空）。

如图7-19所示的是一棵B-树（图中没有标出每个分支节点中的那些指向相应记录的指针）。

图7-19  B-树

2．B-树的查找

B-树的查找过程类似于二叉排序树的查找过程。

例如，要在图7-19所示的B-树中查找关键字为16的记录。其过程是：先找到根节点a，该节点中只有一个关键字10，因16>10，所以顺着右指针找到c节点，该节点有3个关键字14、22、26，因14<16<22，所以顺着第2个指针找到g节点，在该节点中查找到关键字16后，按记录指针（图中没有标出）读出相应的记录。

在上述查找过程中，如果顺着某个指针向下遇到了树叶，则说明要查找的关键字不在B-树中，即查找失败。

B-树中的每个分支节点对应一个物理记录。在上述查找过程中，为得到关键字为16的那个记录在数据区中的存放位置，共访问了3次外存（依次读入a、c、g这3个物理记录）。

3．B-树的插入

和二叉排序的插入方法不同，在往B-树中插入一个关键字时，不是在树中添加一个树叶节点，而是首先在最底层的某个分支节点中添加一个关键字。若插入后该节点的关键字个数不超过m-1，则插入完毕；否则要进行分裂节点的操作，并且这个分裂过程可能会一直波及到根节点。

设某节点已有m-1个关键字，那么在插入一个关键字后，该节点将被分裂成两个节点：左边一个节点包含前ém/2ù-1个关键字，右边一个节点包含后m-ém/2ù个关键字，而第ém/2ù个关键字则被插入到双亲节点中。

【例7-7】 给出向图7-19所示的4阶B-树中依次插入7、9和31等关键字的插入过程。

解：插入3个关键字的过程如下。

（1）通过查找确定插入位置。关键字7应插入到e节点中，由于该节点中原来关键字个数小于3，因此插入完毕。在插入关键字7后，B-树如图7-20（a）所示。

（2）关键字9也应插入到e节点中，由于该节点现在已有3个关键字，因此插入后引起节点的分裂：e节点被分裂成左、右两个节点；关键字7插入到e的双亲节点b中。由于b节点原来只有1个关键字，因此分裂过程结束。在插入关键字9后，B-树如图7-20（b）所示。

（3）关键字21应插入到g节点中。插入后，g节点被分裂成左、右两个节点，即g1和g2节点。当向g节点的双亲节点e插入关键字18时，又引起c节点的分裂，即分裂成c1和c2两个节点。在插入关键字21后，B-树如图7-20（c）所示。

图7-20  插入3个关键字

4．B-树的删除

B-树的删除过程远比二叉排序树复杂。

如果要删除的关键字不在最下面一层的分支节点中，则可先将要删除的关键字与它在B-树中的后继节点对换位置，然后删除该关键字。

例如，为了从图7-19所示的B-树中删除关键字4，可以先将它和关键字6对换位置，然后再进行删除，结果如图7-21（a）所示。

如果要删除的关键字在最下面一层的分支节点中，则将它从所在节点中删除时，可能会导致此节点中关键字少于ém/2ù-1个（即它的孩子节点少于ém/2ù个），因此，需要进行节点的合并操作。节点的合并操作可根据以下两种情况分别进行。

（1）若被删除关键字所在节点中正好有ém/2ù-1个关键字，而与该节点相邻的左兄弟（或右兄弟）节点中的关键字多于ém/2ù-1个，则可将其兄弟节点中最大（或最小）的关键字上移到双亲节点中，而将双亲节点中该上移关键字的后面一个（或前面一个）关键字下移到被删关键字所在节点中。

例如，从图7-21（a）所示的B-树中删除关键字24后，可将g节点中的关键字20上移到c节点，而将c节点中的关键字22下移到h节点，结果如图7-21（b）所示。

（2）若被删除关键字所在节点和其相邻的兄弟节点中的关键字都是ém/2ù-1个，则可将删除了关键字的节点和它的双亲节点中的一个关键字合并到它的兄弟节点中。如果因此使双亲节点中的关键字少于ém/2ù-1个，则需要继续进行合并。

例如，从图7-21（b）所示的B-树中删除关键字28后，需将i节点和c节点中的关键字26合并到h节点中，结果如图7-21（c）所示。

从图7-21（c）的B-树中删除8，需要进行两次合并，结果如图7-21（d）所示。

图7-21  B-树的删除过程（续）

图7-21  B-树的删除过程

7.7.2  B+树

1．B+树的定义

B+树是B-树的一种变形树。一棵m阶B+树满足下列条件：

（1）每个节点至多有m棵子树。

（2）根节点或者没有子树或者至少有两棵子树。

（3）除了根节点以外，每个分支节点至少有ém/2ù棵子树。

（4）树叶都在最底层，包含了所有的关键字以及指向相应记录的指针，而且按关键字的大小顺序链接。

（5）有k棵子树的分支节点中含有k个关键字，而且每个关键字都不小于对应子树中最大的关键字。

图7-22所示的是一棵4阶的B+树（图中没有标出每个树叶中那些指向相应记录的指针）。

在B+树上通常有两个表头指针，一个指向根节点，另一个指向关键字最小的树叶。因此，可以对B+树进行两种查找运算：一种是从根节点开始进行树形查找；另一种是从最小关键字开始进行顺序查找。

在B+树上进行树形查找、插入和删除的过程与B-树有所不同。

图7-22  4阶B+树

2．B+树的查找

B+树的查找过程从根节点开始，顺着指针链往下查找。当在某个分支节点中找到待查的关键字时，查找过程并不停止，而是继续沿指针向下一直查到该关键字所在的树叶。这是因为与每个关键字对应的记录指针只在树叶中。

例如，假设要在图7-22所示的B+树中查找关键字为14的记录，从根节点开始查找，在找到c节点后，查找过程并不停止，而是要继续往下，一直查找到f节点，在f节点中根据与关键字14对应的记录指针（图中没有标出）读出相应的记录。

3．B+树的插入

m阶B+树的插入操作首先是在某个树叶中添加一个关键字。若添加后节点中的关键字个数不超过m，则插入完毕；否则要进行分裂节点的操作，分裂后的两个节点分别包含é(m+1) /2ù和?(m+1)/2?个关键字，并且，它们的双亲节点中应同时包含这两个节点的最大关键字。

例如，在图7-22所示的4阶B+树中，g节点已满（4阶B+树中每个节点最多只能有4个关键字），将关键字17插入到g节点后，g节点将分裂成g1和g2两个节点：g1节点中有3个关键字16、17、18，g2节点中有两个关键字20、22。g1节点中最大关键字18必须插入其双亲节点中。最后结果如图7-23所示。

图7-23  插入关键字17

4．B+树的删除

删除m阶B+树的操作步骤是，首先，在某个树叶中删除一个关键字。若被删除的关键字是节点中最大的关键字，则删除这个关键字后，其上层节点中的值可以作为一个“分界关键字”保留。

例如，在图7-22所示的4阶B+树中，从e节点中删除关键字10后，其在上层b节点和a节点中的值可以继续保留，如图7-24所示。

图7-24  删除关键字10

若因删除操作而使节点中关键字的个数少于ém/2ù个，则需进行节点的合并操作。节点的合并操作可根据以下3种情况分别进行。

（1）被删除关键字所在节点y中正好有ém/2ù个关键字，而其左兄弟节点x中的关键字多于ém/2ù个。此时，可将x节点中最大关键字移入y节点，并在它们的双亲节点中，修改与x节点对应的关键字（用x节点中原先次最大关键字取而代之）。

（2）被删除关键字所在节点y中正好有ém/2ù个关键字，而其右兄弟z中的关键字多于ém/2ù个。此时，可将z节点中最小关键字k移入y节点，并在它们的双亲节点中，修改与y节点对应的关键字（用关键字k取而代之）。

例如，在图7-23所示的4阶B+树中，假定要从g2节点中删除关键字20，此时可将g1节点（g2的左兄弟）中最大关键字18移入g2节点，并用g1节点中次最大关键字17替换双亲节点c中的关键字18，结果如图7-25（a）所示。也可将h节点（g2的右兄弟）中最小关键字24移入g2节点，并用这个关键字替换双亲节点c中的关键字22，结果如图7-25（b）所示。

图7-25  删除关键字20的两种情况

（3）被删除关键字所在节点y和其左右兄弟中的关键字都是ém/2ù个。此时，可将y节点中的关键字移入左兄弟节点或右兄弟节点中，并在删除y节点的同时，从其双亲节点中删除一个关键字。

例如，在图7-24所示的4阶B+树中，假定要从e节点中删除关键字6。此时可将e节点中的剩余关键字8移入d节点（e的兄弟节点），在删除e节点的同时，从双亲节点b中删除关键字4。于是，又引起上层节点的合并：c节点中最小关键字14被移入b节点，a节点中的关键字10被替换成14。最终结果如图7-26所示。

图7-26  删除关键字6