数据结构与算法第十章

第十章文件，外部排序与外部搜索

动态$m$路搜索树，满足：

（1）根最多有$m$棵子树，并具有如下结构：

$$(n,P_0,K_1,P_1,K_2,P_2,\cdots,K_n,P_n)$$，其中$P_i$是指向子树的指针，$K_i$是关键码，且保持递增。

（2）子树$P_i$中所有关键码均小于$K_{i+1}$，且大于$K_i$，$P_0,P_n$仅需满足一侧条件。

（3）子树$P_i$也是$m$路搜索树。

已知$m$路搜索树的度$m$与高度$h$，树中最大结点个数为$\displaystyle (m-1)\cdot \sum_{i=1}^{h}m^{h-1}=m^h-1$

B树与B+树

$m$阶B树是一棵平衡的$m$路搜索树，满足：

（1）根节点至少有2个子女

（2）除根结点以外所有结点（不包括失败结点）至少有$\displaystyle \lceil \frac{m}{2}\rceil$个子女

（3）所有失败结点位于同一层（失败结点指$x$不在树中时能到达的结点，实际不存在，不计入树高）

B树的搜索过程是一个在结点内搜索和循某一条路径向下一层搜索交替进行的过程。

搜索成功时间取决于关键码所在层次，搜索不成功时间取决于树高

设树中关键码有$N$个。

（1）当B树每层结点个数达到最大$m-1$时：

有$N\le m^h-1\to h\ge \lceil\log_m(N+1\rceil$

（2）当B树每层结点个数达到最小时，设树中关键码个数为$N$：第一层：$1$个结点，第二层:至少$2$个结点，第三层：至少$\displaystyle 2\lceil \frac{m}{2}\rceil$个结点，第$h$层，至少$\displaystyle 2\lceil\frac{m}{2}\rceil^{h-2}$个结点。失败结点个数在$h+1$层，个数为$N+1$。

失败数据一般与已有关键码交错排列，有$N+1=NUM_{h+1}\ge\displaystyle 2\lceil\frac{m}{2}\rceil^{h-1}$

$h\le \log_{\lceil\frac{m}{2}\rceil}\displaystyle (\frac{N+1}{2}+1)$

插入，在B树中，每个非失败结点的关键码个数在$[\displaystyle \lceil\frac{m}{2}\rceil-1,m-1]$之间。

在某叶节点开始，若插入关键码后数量溢出$(>m-1)$，则需分裂结点。

取位于中间的关键码$K_{\lceil\frac{m}{2}\rceil}$，将其移至双亲结点内，其左部结点、右部结点这两个集合分裂为两个子女结点。

最坏时，从被插关键码所在叶结点到根的路径上所有结点都要分裂。

删除

若结点中所剩关键码个数小于下限$(<\displaystyle \lceil\frac{m}{2}\rceil-1)$，应考虑结点的调整与合并问题。

（1）删除非叶结点：被删关键码为$K_i$，删去$K_i$之后, 以该结点$P_i$所指示子树中的最小关键码$x$来代替$K_i$位置（大于$K_i$的最小数$x$），转为删除叶结点$x$操作。

（2）删除叶结点（直接删除，无后续处理）：是根结点且结点关键码个数$n\ge 2$，或是非根节点且结点关键码个数$\displaystyle n\ge \lceil\frac{m}{2}\rceil$，则直接删去此关键码，将修改结点回写磁盘。

（3）（有后续处理）左右兄弟够用：被删关键码所在叶结点删除前关键码个数$\displaystyle n= \lceil\frac{m}{2}\rceil-1$，若这时与该结点相邻右兄弟 (左兄弟) 结点关键码个数$\displaystyle n\ge \lceil\frac{m}{2}\rceil$，可按以下步骤处理：

将双亲结点中刚大于 (小于) 被删关键码$K_{remove}$的关键码$K_i$下移；
将右兄弟 (左兄弟) 结点中的最小 (最大) 关键码上移到双亲结点的$K_i$位置；
将右兄弟 (左兄弟) 结点中的最左 (最右) 子树指针移到被删关键码所在结点中最后 (最前) 子树指针位置；
在右兄弟 (左兄弟) 结点中，将被移走的关键码和指针位置用剩余关键码和指针填补调整。再将结点关键码个数减1。

（4）（有后续处理）左右兄弟不够用：被删关键码所在叶结点删除前关键码个数$n=\displaystyle \lceil\frac{m}{2}\rceil-1$，若这时与该结点相邻的右兄弟 (或左兄弟) 结点的关键码个数均为$$n=\displaystyle \lceil\frac{m}{2}\rceil-1$$, 则必须按以下步骤合并这两个结点。

若要合并$P$中的子树指针$P_i$与$P_{i+1}$所指的结点, 且保留$P_i$所指结点, 则把$P$中的关键码$K_{i+1}$下移到$P_i$所指的结点中。
把$P$中子树指针$P_{i+1}$所指结点中的全部指针和关键码都照搬到$P_i$ 所指结点的后面。删去$P_{i+1}$所指的结点。（此时$P_i$关键码被填满）
在结点$P$中用后面剩余的关键码和指针填补关键码$K_{i+1}$和指针$P_{i+1}$。（结点前移）
修改结点$P$和选定保留结点的关键码个数。

在合并结点的过程中, 双亲结点中的关键码个数减少了。

若双亲结点是根结点且结点关键码个数减到 0, 则将该双亲结点删去, 合并后保留的结点成为新的根结点否则结束删除处理。
若双亲结点不是根结点且关键码个数减到$\displaystyle \lceil\frac{m}{2}\rceil-2$，又要与它自己的兄弟结点合并, 重复上面步骤。

B+树与B树不同处：

（1）所有关键码都存放在叶结点，上层非叶结点的关键码是其子树中最小（或最大）关键码的复写。

（2）叶结点包含了全部关键码及指向相应数据记录存放地址的指针，且叶结点本身按关键码从小到大顺序链接。

按最大关键码复写原则组织：

（1）每个结点最多有$m$棵子树；

（2）根结点最少有1棵子树，除根结点外，其他结点至少有$\displaystyle \lceil\frac{m}{2}\rceil$棵子树；

（3）有$n$棵子树的结点有$n$个关键码；

（4）所有非叶结点可以看成是叶结点的索引，结点中关键码$K_i$与指向子树的指针$P_i$构成对子树 (即下一层索引块) 的索引项$(K_i,P_i)$，$K_i$是子树中最大的关键码。

（5）所有叶结点在同一层，按从小到大的顺序存放全部关键码，各个叶结点顺序链接。

B+树中有两个头指针：

（1）指向B+树的根结点（2）指向关键码最小的叶结点。

可对B+树进行两种搜索运算：

（1）循叶结点自己拉起的链表顺序搜索

（2）从根开始进行自顶向下直到叶结点的随机搜索。

B+树的插入

插入仅在叶结点进行，当插入后叶结点关键码个数$n>m$时，分裂叶结点为两个结点，分别包含$\displaystyle \lceil \frac{m+1}{2}\rceil,\lfloor\frac{m+1}{2}\rfloor$个结点。

B+树的删除

仅在叶结点进行，若删除索引项后，结点索引项个数仍不少于$\displaystyle \lceil\frac{m}{2}\rceil$时，属于简单删除。若删除结点的最大关键码，上层副本仍可保留。

若删除后，结点索引项个数少于$\displaystyle \lceil\frac{m}{2}\rceil$，则必须做结点的调整/合并。

若右兄弟结点关键码数大于$\displaystyle \lceil\frac{m}{2}\rceil$，从右兄弟结点中把最左侧索引项移到此被删关键码所在结点，并修改上层分界关键码的值。
若右兄弟结点关键码数不足，则做合并，将右兄弟中所有索引项移入被删关键码所在结点，删去右兄弟结点，同时此合并导致双亲结点分解关键码的减少，需要逐层查询双亲结点是否应该调整或合并。