第一章树的应用(2014)

1、教师：刘城霞*数据结构综合设计*课程安排*课时安排：课时安排：32学时（讲课学时（讲课 8 上机上机 24）*上机安排：第十二周开始上机安排：第十二周开始*课程要求：先修课程要求：先修 高级程序设计语言，数高级程序设计语言，数据结构据结构*课件公共邮箱：课件公共邮箱：*密码密码:shujujiegou*内容简介*数据结构数据结构是为了让学生学会分析数据对象的特性，设计适合的数据结构，完成相应的运算，把现实世界中的问题转化为计算机可识别的表示,用计算机帮助完成各种任务。*数据结构综合设计数据结构综合设计在原来数据结构的基础上增加了一些针对某种或几种数据结构的实践题目及其讲解。*除此之外，原数据结

2、构中一些较难的理论也单独列出讲解，弥补因数据结构中课时不足等问题造成的部分知识不全面。*内容简介*本书内容共分4章*第1章 树的应用*第2章 外排序算法*第3章 内存管理方法*第4章 文件的基本结构*第一章 树的应用*3.1树和二叉树*树树*树是n (n 0)个结点的有限集合。当n = 0时，集合为空集，称为空树。在任意一棵非空树T中：* 有且仅有一个特定的，称为根(root)的结点。* 当n 1时，除根结点以外的其余结点可分成m (m 0)个互不相交的有限集合T1，T2，Tm。其中每一个集合本身又是一棵树，并称其为根的子树(subtree)。*二叉树*二叉树(binary tree)是n (

3、n 0) 个结点的有限集合，*n = 0时为空集，称为空二叉树；*n0时，二叉树由一个根结点及两棵互不相交、分别称为左子树和右子树的二叉树组成。*二叉树和树在概念上相同的是都有一个且仅有一个根结点，根结点无前驱结点，叶子结点无后继结点。*不相同的是二叉树中每个结点的度小于等于2，而且二叉树的子树有左右子树之分。*二叉树的性质*性质1：二叉树第i层上的结点数目至多为2i-1(i1)。*性质2：深度为k的二叉树至多有2k-1个结点(k1)。*性质3：在任何一棵二叉树中，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1*一棵深度为k且有2k - 1个结点的二叉树称为满二叉树，若

4、在一棵深度为k (k 1) 的二叉树中，第1层到第k-1层构成一棵深度为k-1的满二叉树，第k层的结点不满2k-1个结点，而这些结点都满放在该层最左边，则此二叉树称为完全二叉树。*二叉树的性质*性质4：具有n个结点的完全二叉树的深度为log2n+ 1。*性质5：对一棵有n个结点的完全二叉树的结点按层自左向右编号，则对任一编号为i (1 i n)的结点有下列性质：* 若i = 1，则结点i是二叉树的根，若i 1，则结点i的双亲结点是 i/2；*若2i n，则结点i有左孩子，左孩子的编号是2i，否则结点i无左孩子，并且是叶子结点；* 若2i + 1 n，则结点i有右孩子，右孩子的编号是2i + 1

5、，否则结点i无右孩子。*二叉树链式存储结构#define DATATYPE2 chartypedef struct node1 DATATYPE2 data; struct node1 *lchild, *rchild;BTree;*基本操作*构造、插入、删除、遍历等* 3.2B树和B+树 (1) (1)B-树的概念：平衡多路查找树平衡多路查找树 一棵一棵m m阶的阶的B-B-树，或为空树，或为满足下列特性的树，或为空树，或为满足下列特性的m m叉树叉树1、树中每个结点最多有、树中每个结点最多有m棵子树棵子树2、若根结点不是叶子结点，则至少有两棵子树、若根结点不是叶子结点，则至少有两棵子树3、

6、除根之外的所有非终端（叶子）结点至少有、除根之外的所有非终端（叶子）结点至少有 棵子树棵子树2/m4、所有非终端结点中包含下列信息数据、所有非终端结点中包含下列信息数据(n, A0, K1, A1, K2, A2, , Kn, An)5、所有叶子结点都在同一层，不带信息。、所有叶子结点都在同一层，不带信息。 (可可以看作是外部结点或查找失败的结点，实际上以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空这些结点不存在，指向这些结点的指针为空)a. na. n为关键字的个数，多个关键字自小至大有序为关键字的个数，多个关键字自小至大有序排列，即：排列，即：K K1 1

7、K K2 2 K key1.keynump-key1.keynum中找中找i,i,使得使得p-keyiKkeyi+1p-keyiKkeyi+1 if(i0 & p-keyi=K) found=TRUE if(i0 & p-keyi=K) found=TRUE;/;/找到找到 else q=p; p=p-ptri; else q=p; p=p-ptri; if(found) return (p,i,1); if(found) return (p,i,1); /成功，返回位置成功，返回位置 else return(q,i,0); else return(q,i,0);/不成功，返回

8、应插入位置不成功，返回应插入位置 B-树查找性能分析树查找性能分析 一般情况下，一般情况下，B-树文件存储在磁盘上，则树文件存储在磁盘上，则 前一查中操作是在磁盘中进行的，即在磁盘上前一查中操作是在磁盘中进行的，即在磁盘上找到指针所指的结点。找到指针所指的结点。 后一查找为内存中进行的，也就是将所查结点后一查找为内存中进行的，也就是将所查结点内容读入内存，利用顺序查找或者折半查找找到内容读入内存，利用顺序查找或者折半查找找到关键字。关键字。 又因为磁盘查找比内存查找耗时多的多，所又因为磁盘查找比内存查找耗时多的多，所以以在在B-B-树中进行查找时，其查找时间主要花费在树中进行查找时，其查找时间

9、主要花费在搜索结点（访问外存）上，即主要取决于搜索结点（访问外存）上，即主要取决于B-B-树的树的深度。深度。问：问：1 1）含）含 N N 个关键字的个关键字的 m m 阶阶 B-B-树可能达到的树可能达到的最大深度最大深度 H H 为多少？为多少？B-树查找性能分析树查找性能分析2 2）深度为）深度为H+1H+1的的B-B-树中，至少含有多少个结点？树中，至少含有多少个结点？第第 2 层层 2 个个先推导每一层所含最少结点数：先推导每一层所含最少结点数：第第 1 层层 1 个个第第 H+1 层层 2 ( m/2 ) H-1 个个第第 4 层层 2 ( m/2 )2 个个第第 3 层层 2m

10、/2 个个 B-树查找性能分析树查找性能分析假设假设 m m 阶阶 B-B-树的深度为树的深度为 H+1H+1，由于第，由于第 H+1 H+1 层为层为叶子结点，而当前树中含有叶子结点，而当前树中含有 N N 个关键字，则叶子个关键字，则叶子结点必为结点必为 N+1N+1 个，个， N+12( m/2 )H-1 H-1log m/2 (N+1)/2) Hlog m/2 (N+1)/2)+1由此可推得下列结果：由此可推得下列结果：B-树查找性能分析树查找性能分析在含在含 n n 个关键字的个关键字的 B-B-树上进行一次查找，需访树上进行一次查找，需访问的结点个数不超过问的结点个数不超过结论：结

11、论：1)21(log2/NmB-树插入结点树插入结点在查找不成功之后，需进行插入。显然，在查找不成功之后，需进行插入。显然，关键字关键字插入的位置必定在最下层的非叶结点插入的位置必定在最下层的非叶结点，有下列几，有下列几种情况：以三阶种情况：以三阶B B树为例来说树为例来说1 1）插入后，该结插入后，该结点的关键字个数点的关键字个数nmnptri+1* if(q-keynumkeys; /将将q-keys+1.m, q-ptrs.m和和q-recptrs+1.m 移入新结点移入新结点*ap* q=q-parent;* if(q) i=Search(q,x);* *If(!finished) /

12、T为空树或根结点已分裂为空树或根结点已分裂* newRoot(T,q,x,ap);*Return OK;*B-树删除结点树删除结点删除操作和插入结点的考虑相反删除操作和插入结点的考虑相反1 1）首先必须找到待删关键字所在结点，并且要求删除）首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于之后，结点中关键字的个数不能小于 m/2m/2 -1-12 2）否则，要从其左）否则，要从其左( (或右或右) )兄弟结点兄弟结点“借调借调”关键字关键字3 3）若其左和右兄弟结点均无关键字可借）若其左和右兄弟结点均无关键字可借( (结点中只有最结点中只有最少量的关键字少量的关键字)

13、,),则必须进行结点的则必须进行结点的“合并合并”。B-树删除结点树删除结点1.被删除结点上关键字个数不少于被删除结点上关键字个数不少于 m/2 -1，那么只，那么只需从该结点上删除该关键字需从该结点上删除该关键字Ki和相应的指针和相应的指针Ai。例如下图例如下图3-阶阶B树中删除关键字树中删除关键字12时，直接将时，直接将12 删除删除即可。即可。53 9024 50 100 3 12 37 45 61 70 3 abcdefghB-树删除结点树删除结点2.2.如果被删除结点上关键字个数等于如果被删除结点上关键字个数等于 m/2m/2 -1 -1，而与其相邻的右兄弟结点（或左兄弟）结点中关而

14、与其相邻的右兄弟结点（或左兄弟）结点中关键字的个数大于键字的个数大于 m/2m/2 -1 -1 则需将其兄弟结点中最小（或最大）的关键则需将其兄弟结点中最小（或最大）的关键字上移至双亲结点中，而将双亲结点中小于（或字上移至双亲结点中，而将双亲结点中小于（或大于）大于）, ,且紧靠该上移关键字的关键字移至被删且紧靠该上移关键字的关键字移至被删关键字所在结点中。关键字所在结点中。B-树删除结点树删除结点下图为删除下图为删除5050前、后的前、后的3 3阶阶B-B-树。图中树。图中6161为上移为上移关键字，而关键字，而5353为小于为小于6161且紧靠且紧靠6161的下移到被删关的下移到被删关键字

15、所在结点中。键字所在结点中。53 9024 50 100 3 37 45 61 70 abcdefgh 70 61 90 53 B-树删除结点树删除结点3.3.被删除关键字所在结点和其相邻的右兄弟结点被删除关键字所在结点和其相邻的右兄弟结点（或左兄弟）结点中关键字的个数均等于（或左兄弟）结点中关键字的个数均等于 m/2m/2 -1 -1，假设该结点有右兄弟，且其右兄弟结点地址由双亲假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针结点中的指针AiAi所指，所指，则在删去关键字之后，它所在结点中剩余的关键字则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键和指针，加上

16、双亲结点中的关键KiKi一起，合并到一起，合并到AiAi所指兄弟结点中（若没有右兄弟，则合并到左兄弟所指兄弟结点中（若没有右兄弟，则合并到左兄弟结点中）。结点中）。9061 90B-树删除结点树删除结点24 100 3 37 45abcdefgh 70 53 删除关键字删除关键字53 61 70 90B-树删除结点树删除结点24 100 3 37 45abcdegh练习：从下面的练习：从下面的B树中删除关键字树中删除关键字37 61 70 90B-树删除结点树删除结点24 100 37 45abcdegh删除关键字删除关键字37 61 70 3 2437没有右兄弟且其左兄弟也只有一个关键字，没

17、有右兄弟且其左兄弟也只有一个关键字，把把37 双亲结点中小于双亲结点中小于37 的关键字的关键字24 与左兄弟中的与左兄弟中的3合并成一个结点。合并成一个结点。此时，发现左右子树高度不同，必须调整成此时，发现左右子树高度不同，必须调整成B-树。树。 3 45 90 100 ech3 24 61 70 g45 90B-树删除结点树删除结点 100 ech3 24 61 70 g调整后的调整后的B-树，如下所示树，如下所示B-树删除算法步骤树删除算法步骤E1:E1:查找算法到要删除关键字位置，删除该关键字。查找算法到要删除关键字位置，删除该关键字。E2:E2:判断删除后关键字个数，如少于判断删除后

18、关键字个数，如少于 m/2m/2 -1 -1则进入则进入3 3，否则删，否则删除完成。除完成。E3:E3:找到其双亲结点（找到其双亲结点（parentparent指针），判断其左兄弟关键字个数，指针），判断其左兄弟关键字个数，如大于如大于 m/2m/2 -1, -1,则将其最大关键字取出（删除）后插入双亲则将其最大关键字取出（删除）后插入双亲结点，将双亲结点中的关键字插入该结点最左边。否则对其右结点，将双亲结点中的关键字插入该结点最左边。否则对其右兄弟做相同的处理。如均不满足则进入兄弟做相同的处理。如均不满足则进入E4E4。E4:E4:其兄弟结点的关键字和该结点的关键字合并，并且将其双亲其兄弟

19、结点的关键字和该结点的关键字合并，并且将其双亲中相应关键字取出也插入合并结点中，形成一个新的结点。如中相应关键字取出也插入合并结点中，形成一个新的结点。如双亲结点删除一个关键字后满足双亲结点删除一个关键字后满足E2E2要求，则结束；否则重复要求，则结束；否则重复E3E3。E5:E5:删除完成后判断是否平衡，不平衡则调整。（平衡树的调整删除完成后判断是否平衡，不平衡则调整。（平衡树的调整参照平衡二叉树调整过程）参照平衡二叉树调整过程）*B+树是是B-树的一种变型。树的一种变型。1）有有n n棵子树的结点中含有棵子树的结点中含有n n个关键字个关键字2）所有的叶子结点中包含了全部关键字的信息，所有

20、的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，并且，所有叶及指向含这些关键字记录的指针，并且，所有叶子结点彼此相链接构成一个有序链表，其头指针子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；指向含最小关键字的结点；3）每个非叶结点中的关键字）每个非叶结点中的关键字K Ki i 即为其相应指针即为其相应指针A Ai i 所指子树中关键字的最大值；所指子树中关键字的最大值；*一个3阶B+树 50 96 15 5062 78 96 71 7884 89 96 56 6220 43 50 3 8 15sqroot*B+树索引的总体结构 B B+ +树索引是一个多级

21、索引；树索引是一个多级索引； B B+ +树索引采用平衡树结构，即每个叶结树索引采用平衡树结构，即每个叶结点到根的路径长度都相同；点到根的路径长度都相同； 每个非叶结点有每个非叶结点有 m/2m/2 到到m m个子女，个子女，m m对对特定的树是固定的；特定的树是固定的； B B+ +树的所有结点结构都相同，它最多包树的所有结点结构都相同，它最多包含含m m个关键字值个关键字值K K1 1、K K2 2、K Km m，以及，以及m+1m+1个指个指针针P P1 1、P P2 2、P Pm m、 P Pm+1m+1, ,每个结点中的关键每个结点中的关键字值按次序存放，即如果字值按次序存放，即如果

22、ijij，那么，那么K Ki iKKj j。*B+树索引的叶结点 指针指针P Pi i(i=1,2,n)(i=1,2,n)指向具有关键字值指向具有关键字值K Ki i的一个文件记录的一个文件记录( (或一个指针桶，桶中的每或一个指针桶，桶中的每个指针指向具有关键字值个指针指向具有关键字值KiKi的一个文件记录。的一个文件记录。指针桶只在文件不按关键字顺序物理存储时指针桶只在文件不按关键字顺序物理存储时才使用才使用) )。指针。指针P Pm+1m+1链接下一个叶节点；链接下一个叶节点；2*B+树索引的叶结点* 每个叶结点最多可有每个叶结点最多可有m m个关键字值，最少也要有个关键字值，最少也要有

23、 m/2m/2 个关键字值。各个叶结点中关键字值的范围个关键字值。各个叶结点中关键字值的范围互不相交。互不相交。*B+B+树索引如果为稠密索引，数据文件中的各关键字树索引如果为稠密索引，数据文件中的各关键字值都必须出现在某个叶结点中且只能出现一次。值都必须出现在某个叶结点中且只能出现一次。2*B+树索引的叶结点 由于各叶结点按照所含的关键字值从小到大排由于各叶结点按照所含的关键字值从小到大排列，所以可以利用各个叶结点的指针列，所以可以利用各个叶结点的指针P Pm+1m+1将叶结点链将叶结点链接在一起。这个顺序链能够高效地对文件进行顺序检接在一起。这个顺序链能够高效地对文件进行顺序检索，而索，而

24、B B+ +树索引的其他结构能够高效地对文件进行随树索引的其他结构能够高效地对文件进行随机检索。机检索。*B+树索引的非叶结点 B B+ +树索引的非叶结点形成叶结点上的一树索引的非叶结点形成叶结点上的一个多级（稀疏）索引；个多级（稀疏）索引；非叶结点的结构和叶结点的结构相同，即非叶结点的结构和叶结点的结构相同，即含有能够存储含有能够存储m m个关键字值和个关键字值和m+1m+1个指针的存个指针的存储单元的数据结构。只不过非叶结点中的所储单元的数据结构。只不过非叶结点中的所有指针都指向树中的结点；有指针都指向树中的结点；*B+树索引的非叶结点 如果一个非叶结点有如果一个非叶结点有n n个指针，

25、则个指针，则 m/2m/2 nmnm。若。若nmnm，则非叶结点中指针，则非叶结点中指针P Pn n之后的所有之后的所有空闲空间作为预留空间如图空闲空间作为预留空间如图nnn*B+树索引的非叶结点 在一个含有在一个含有m m个指针的非叶结点中，指针个指针的非叶结点中，指针P Pi i(i=2,m)(i=2,m)指向一棵子树，该子树的所有结点指向一棵子树，该子树的所有结点的关键字值大于的关键字值大于K Ki-1i-1而小于等于而小于等于K Ki i。*B+树索引的根结点 根结点的结构也与叶结点相同；根结点的结构也与叶结点相同； 根结点包含的指针数可以小于根结点包含的指针数可以小于 m/2m/2

26、。但是，除非整棵树只有一个结点，否则根结但是，除非整棵树只有一个结点，否则根结点必须至少包含两个指针。点必须至少包含两个指针。*B+树在索引文件中的应用*用用B+B+树组织索引顺序文件时，用主文件的每个页块树组织索引顺序文件时，用主文件的每个页块作作B+B+树的一个外部结点，并且这些页块之间相互链树的一个外部结点，并且这些页块之间相互链接。接。B+B+树的树叶层是主文件的稀疏索引，整个树的树叶层是主文件的稀疏索引，整个B+B+树树构成多级索引。索引项就是构成多级索引。索引项就是B+B+树中一个关键字和它树中一个关键字和它对应的指针所构成的二元组。对应的指针所构成的二元组。*在用在用B+B+树组

27、成的索引顺序文件中，当主文件中需要树组成的索引顺序文件中，当主文件中需要增加或减少一个页块时，只需在增加或减少一个页块时，只需在B+B+树中为之插入或树中为之插入或删除一个索引项，问题归结为删除一个索引项，问题归结为B+B+树本身的运算。树本身的运算。*B+树的操作*B+B+树的查找可以分为两类：树的查找可以分为两类：*一是顺序查找，即从叶结点的顺序链表中依次查找需一是顺序查找，即从叶结点的顺序链表中依次查找需要的记录。要的记录。*二是按索引查找，这种查找方法类似于二是按索引查找，这种查找方法类似于B-B-树，只是在树，只是在查找时，若非终端节点上的关键字等于给定值，并不查找时，若非终端节点上

28、的关键字等于给定值，并不终止，而是继续向下直到叶子结点。终止，而是继续向下直到叶子结点。*E1:E1:初始化，从根开始查找。初始化，从根开始查找。*E2:E2:查找结点内关键字查找结点内关键字, ,要求要求Key(i-1)K=Key(i)Key(i-1)KKey(m)KKey(m)或或KKey(1)Kkey1.keynump-key1.keynum中找中找I I / /使得使得p-keyip-keyi1Kkeyi1Kkeyi if(i0 & i0 & iptri; p=p-ptri; else else return (p,i,0); return (p,i,0); *If(p

29、 If(p 是叶子）是叶子）i=Search(p, K); i=Search(p, K); if(i0 & ikeyi) if(i0 & ikeyi) return return （p,i,1p,i,1）; ; else else return (p,i,0); return (p,i,0);*B+树的插入*在查找不成功之后，需进行插入。显然，在查找不成功之后，需进行插入。显然，关键字插入关键字插入的位置必定在最下层的叶子结点的位置必定在最下层的叶子结点，有下列几种情况：，有下列几种情况：*当结点中的关键字个数小于等于当结点中的关键字个数小于等于m m时直接插入；时直接插入；1

30、.1.当结点中的关键字个数大于当结点中的关键字个数大于m m时要分裂成两个结点时要分裂成两个结点, ,并且要在双亲结点中插入新增了的结点的最大关键字。并且要在双亲结点中插入新增了的结点的最大关键字。操作类似于操作类似于B-B-树。树。B+树插入结点树插入结点1 1、3 3阶阶 B+ B+树插入关键字树插入关键字60,9060,9040 80 20 40 8060 80 60 80 9040 902、3阶阶B树插入关键字树插入关键字7040 9020 40 60 80 90 60 70 80 90 60 70 80 90 40 70 90*插入步骤*E1:E1:从树根开始查找要插入位置，并记录从

31、树根开始查找要插入位置，并记录查找路径。查找路径。*E2:E2:建立新关键字及指针信息，插入叶子建立新关键字及指针信息，插入叶子结点中。结点中。*E3:E3:判断结点关键字个数，若判断结点关键字个数，若=mmm，则分裂结点，将新的最大，则分裂结点，将新的最大关键字插入双亲结点，重复关键字插入双亲结点，重复E3E3。*E4:E4:若根结点需要分裂，则新建根结点。若根结点需要分裂，则新建根结点。*使用B+树索引结构插入记录的算法* p= p=根结点根结点; ;* 栈栈S S清空清空; ; / S/ S存储结点的父结点存储结点的父结点* while p while p不是叶结点不是叶结点 * pus

32、h(p,S);q= push(p,S);q=树中树中p p结点子指针数结点子指针数; ;/父结点入栈父结点入栈* if if （k k p-kp-k1 1）* p=p-p p=p-p1 1* else else * 找找i i 满足满足p-kp-ki-1i-1kkp-ki i ;p=p-p ;p=p-pi i ; ; * 若若p-kp-kn n k k 则则 p=p-p p=p-pn n ; ; * i=Search(p, K); i=Search(p, K); * if(i0 & ikeyi) if(i0 & ikeyi) * 记录已存在记录已存在;return;return

33、;*elseelse* 建索引项建索引项(k,d),(k,d),数据指针数据指针d d指向新记录指向新记录; ;*if if 叶点叶点* *p p 不满不满 * insert(p,k,d) / insert(p,k,d) / 插到插到* *p p的正确位置的正确位置*else else /对满叶结点对满叶结点* *p p作分裂处理作分裂处理* 把满叶结点把满叶结点* *p p的索引项复制到的索引项复制到tmp;tmp; /准备分裂准备分裂* 把索引项把索引项(k,d)(k,d)按序插入到按序插入到tmptmp的正确位置的正确位置; ;* 建立一个空的新叶结点建立一个空的新叶结点new;new;

34、* 用用tmptmp的前的前ceil(m/2)ceil(m/2)个索引项覆盖结点个索引项覆盖结点* *p p的信息的信息; ;* 把把tmptmp的其余索引项及相邻叶指针存入的其余索引项及相邻叶指针存入new;new;* p-P p-Pnextnext=new=new的地址的地址 ; k; k* *= =新的最大关键字新的最大关键字; ;* Finish=false; Finish=false; /准备把准备把(k(k* *,new),new)插入父亲插入父亲( (内内) )结点结点* *While (!finish)While (!finish)* if if 栈栈S S空空* root=N

35、ewRoot(m,k root=NewRoot(m,k* *,new); /,new); /建立新空根结点建立新空根结点* finish=true; finish=true; * else else* * *p=pop(S); p=pop(S); /取出父结点取出父结点* if if 内结点内结点* *p p不满不满* 把把(k(k* *,new) ,new) 插入到插入到* *p;finish=true;p;finish=true;* else else* 复制满内结点复制满内结点* *p p到到tmp; tmp; * 对满内结点对满内结点* *p p分裂分裂; ; * *B+树的删除*B+

36、B+树的删除也仅在叶子结点上进行，当叶子结树的删除也仅在叶子结点上进行，当叶子结点中的最大关键字被删除时，在非终端结点中点中的最大关键字被删除时，在非终端结点中修改成当前最大关键字值。若因删除使结点中修改成当前最大关键字值。若因删除使结点中关键字的个数少于关键字的个数少于 m/2m/2 时，需要从兄弟结点中时，需要从兄弟结点中借一个关键字，如兄弟结点无法借出，则和其借一个关键字，如兄弟结点无法借出，则和其兄弟结点进行合并，过程同兄弟结点进行合并，过程同B-B-树。树。80 9961 80 99B树删除结点树删除结点24 45 88 993 2437 4545 99abcdefgh70 80 5

37、3 613阶阶B+树删除树删除53 61 61 70 80*B+树删除的步骤E1:E1:查找算法到要删除关键字位置，删除该关键字。查找算法到要删除关键字位置，删除该关键字。E2:E2:判断删除后关键字个数，如少于判断删除后关键字个数，如少于 m/2m/2 则进入则进入E3E3，否则删除完成。否则删除完成。E3:E3:找到其双亲结点（找到其双亲结点（parentparent指针），判断其右兄弟关指针），判断其右兄弟关键字个数，如大于键字个数，如大于 m/2m/2 , ,则将其最小关键字取出则将其最小关键字取出（删除）插入该结点最右边，修改双亲结点中的最大（删除）插入该结点最右边，修改双亲结点中的

38、最大关键字值。否则对其左兄弟做相同的处理。如均不满关键字值。否则对其左兄弟做相同的处理。如均不满足则进入足则进入E4E4。E4:E4:其兄弟结点的关键字和该结点关键字合并，形成一其兄弟结点的关键字和该结点关键字合并，形成一新的结点。且将其双亲中相应关键字删除，如双亲结新的结点。且将其双亲中相应关键字删除，如双亲结点删除一个关键字后满足点删除一个关键字后满足E2E2要求则结束；否则重复要求则结束；否则重复E3E3。E5:E5:删除完成后判断是否平衡，不平衡则调整。删除完成后判断是否平衡，不平衡则调整。*B+的特性总结*B+B+的特性：的特性：*所有关键字都出现在叶子结点的链表中，且链表中的所有关键字都出现在叶子结点的链表中，且链表中的关键字是有序的；关键字是有序的；*查找不可能在非叶子结点命中；查找不可能在非叶子结点命中；*非