数据结构第9章查找3B树课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.定义,一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:,(l)所有的非终端结点的结构如下:,其中,k1,k2,.,kn为n个按从小到大顺序排列的键值;,p0,pl,p2,.,pn为(n+1)个指针,用于指向该结点的(n+l)棵子树,p0所指向子树中的所有关键字的值均小于kl,pn所指向子树中的所有关键字的值均大于kn,pi(1in-1)所指向子树中的所有关键字的值均大于ki且小于ki+1;,n(nm-1)为键值的个数,即子树个数为(n+l)。,n,p,0,k,1,p,1,k,2,p,2,k,i,p,i,k,n,p,n,一、B-树的基本概念,1.定义np0k1p1k2p2kipiknpn一、B-树,1,1.定义,(2)树中每个结点至多有m棵子树。,(3)除非根结点为叶子结点,否则至少有两棵子树。,(4)除根之外的所有非终端结点至少有m/2棵子树。,(5)所有叶子结点在同一个层次上,且不含有任何信息。,2.说明,(1)对于非根结点的所有分支结点,n的取值范围为 m/2-1nm-1。,(2)对于根结点,n的取值范围为1nm1。,(3)对于叶子结点,其子树均为空树(即没有子结点),又规定不含有任何信息,可以把它看作不在树中的外部结点。,(4)B-树的阶m可以事先任意指定,一旦指定后就固定不变。,1.定义,2,1,50,1,30,1,95,1,25,1,55,2,70,90,2,35,40,a,t,b,c,d,f,g,e,h,图 B-树,3,75,80,85,下图是一棵由10个键值生成的四阶B_树的示意图,该树共有四层,所有叶子点均在第四层上。,1501301951251552709023540atbcd,3,二、B-树的查找,1.查找方法,由B-树的定义可知,在B-树上进行查找的过程与二叉排序树的查找类似。,根据给定的键值k,先在根结点的键值的集合中采用顺序(当m较小时)或二分(当m较大时)查找方法进行查找。,若有k=ki,则查找成功,根据相应的指针即可取记录；否则,若k在ki和ki+1之间,取指针pi所指的结点,重复这个查找过程,直到在某结点中查找成功,或在某结点处出现pi 为空,查找失败.,二、B-树的查找1.查找方法,4,在B-树中进行查找时，其查找时间,主要花费在搜索结点（访问外存）上，,即主要取决于,B-树的深度,。,问：含,N,个关键字的,m,阶,B-,树可能达到的,最大深度,H,为多少？,查找性能的分析,在B-树中进行查找时，其查找时间问：含 N 个关键字,5,第 2 层,2 个,先推导每一层所含最少结点数：,第 1 层,1 个,第 H+1 层,2,(,m/2,),H-1,个,第 4 层,2,(,m/2,),2,个,第 3 层,2,m/2,个,反过来问：深度为H的B-树中，,至少含有多少个结点？,第 2 层 2 个先推导每一层所含最少,6,假设,m,阶 B-树的深度为,H,+1,，由于,第 H+1 层为,叶子,结点，而当前树中含有,N,个关键字，则叶子结点必为,N+1,个，,N+12(,m/2,),H-1,H-1log,m/2,(N+1)/2),Hlog,m/2,(N+1)/2)+1,由此可推得下列结果：,假设 m 阶 B-树的深度为 H+1，由于,7,在含,N,个关键字的,B-,树上进行一次查找，需访问的结点个数不超过,log,m/2,(N+1)/2)+1,结论：,在含 N 个关键字的 B-树上进行一次查找，需访问的结点,8,在查找不成功之后，需进行插入。,显然，关键字,插入,的,位置,必定在,最下,层的非叶结点,，有下列几种情况：,1）插入后，该结点的关键字个数nm，,不修改指针,;,三、B-树的插入和删除,在查找不成功之后，需进行插入。1）插入后，该结点的关键字个数,9,2）,插入后，该结点的关键字个数,n=m，,则需进行“结点分裂”，令 s=,m/2,，,在原结点中保留,（A,0,，K,1,，K,s-1,，A,s-1,）；,建新结点,（A,s,，K,s+1,，K,n,，A,n,）；,将（K,s,，p）插入双亲结点；,3）若双亲为空，则建新的根结点。,2）插入后，该结点的关键字个数 n=m，3）若双亲为空，则建,10,例如:下列为 3 阶B-树,50,20,40,80,插入关键字=,60,60,80,90,60,80,90,90,50,80,60,30,40,20,30,50 80,80,30,50,例如:下列为 3 阶B-树50 20 40 80,11,2、B-树的删除,在深度为(h+l)的m阶B-树中删除一个键值k,首先要查到键值k所在的结点及在结点中的位置。若k在非终端节点中，则把该结点的右边(或左边)指针所指子树中的最小(或最大)键值与k对调，使k移到终端节点。,在终端节点中删除一个键值后,使得该结点的值个数n减1,此时应分以下三种情况进行处理：,(1)若删除后结点中键值数目n m/21,在该结点中删去键值k连同右边的指针。,(2)若删除后结点中键值数目n m/2 1,且左(或右)兄弟结点的关键字数目 m/21,则把左(或右)兄弟结点中最大(或最小)键值移到父结点中,再把父结点大于(或小于)上移键值的键值下移到被删关键字所在结点中。,2、B-树的删除在深度为(h+l)的m阶B-树中删除一个键值,12,(3)若删除后结点中键值数目n m/2 1,及其左、右兄弟结点的键值数目都等于m/21,则就必须进行结点的“合并”,即把应删的键值删去后,将该结点中的剩余键值和指针连同父结点中指向该结点指针的左边(或右边)一个键值k,i,一起合并到左兄弟(或右兄弟)结点中,将ki从父结点中删去。如果因此使父结点中关键字数目 m/21,则对此父结点做同样处理,以致于可能直到对根结点做这样的处理而使整个树减少一层。,(3)若删除后结点中键值数目n m/2 1,及其左、,13,30,65 80,25,40,55 60,70 75,85,50,(a)由上图删除35后的3阶B_树,30,65 80,25,35 40,55 60,70 75,85,50,3065 8025 4055 6070 7,14,30,65 75,25,40,55 60,70,80,50,(b)删除85后的B_树,30,65 80,25,40,55 60,70 75,85,50,3065 7525 4055 6070 8050,15,30,65,25,40,55 60,70 75,50,(c)删除80后的B_树,30,65 75,25,40,55 60,70,80,50,(b)删除85后的B_树,3065 25 4055 6070 7550(,16,30,65,25,40,55 60,70 75,50,(c)删除80后的B_树,50 65,70 75,30 40,55 60,(d)删除25后的B_树,3065 25 4055 6070 7550(,17,四、B+树,对于m阶的B+树和m阶的B-树,主要的差异是:,在B+树中,具有n个关键字的结点则含有n棵子树,即每个关键字对应一棵子树,而在B-树中,具有n个键值的结点含有(n+1)棵子树;,在B+树中,每个结点(除树根结点外)中的键值个数n的取值范围是m/2nm,根结点n的取值范围是1nm;而在B_树中,它们的取值范围分别是m/21nml 和 lnm1。,四、B+树对于m阶的B+树和m阶的B-树,主要的差异是:,18,B+树中的所有叶子结点包含了全部键值,即其他非叶结点中的键值包含在叶结点中,而在B-树中,叶结点包含的键值与其他结点包含的键值是不重复的。,B+树中所有非叶结点仅起到索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该键值对应记录的存储地址。而在B-树中,每个键值对应一个记录的存储地址。,通常在B+树上有两个头指针,一个指向根结点,另一个指向键值最小的叶子结点,所有叶结点链接成一个不定长的线性链表。,B+树中的所有叶子结点包含了全部键值,即其他非叶结点中的键值,19,40 65,35 40,60 65,55 65,40 45 55,20 25 30,15 30 40,10 15,root,head,图 B+树,40 6535 4060 6555 6540,20,二、B+树查找,在B+树中可以采用两种查找方式,一种是直接从最小键值开始进行顺序查找,另一种就是从B+树的根结点开始进行随机查找。这种查找方式与B-树的查找方法相似,只是在分支结点上的键值与查找值相等时,查找并不结束,要继续查到叶结点为止,此时若查找成功,则按所给指针取出对应记录即可。因此,在B+树中,不管查找成功与,否,每次查找都是经过了一条从树根结点到叶子结点的路径。,二、B+树查找,21,三、B+树插入,与B-树的插入操作相似,B+树的插入也从叶子结点开始,当插入后结点中的键值个数大于m时要分裂成两个结点,它们所含键值个数分别为(m+1)/2和,(m+1)/2,同时要使得它们的双亲结点中包含有这两个结点的最大键值和指向它们的指针。若双亲结点的键值数目因此而大于m,应继续分裂,依此类推。,三、B+树插入,22,四、B+树删除,B+树的删除也是从叶子结点开始,当叶结点中最大键值被删除时,分支结点中的值可以作为“分界键值”存在。若因删除操作而使结点中键值个数少于m/2时,则从兄弟结点中调剂键值或和兄弟结点合并,其过程和B-树相似。,四、B+树删除,23,作业,对下面的3阶B-树，依次执行下列操作，画出各步操作的结果。（1）插入90 （2）插入25 （3）插入45 （4）删除60 （5）删除80。,作业对下面的3阶B-树，依次执行下列操作，画出各步操作的结果,24,谢谢！,谢谢！,25,数据结构第9章查找3B树课件,26,