资源描述
,7、B_树和B+树1、为什么采用B_树和B+树：大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。在1970年由Rbayer和Emacreight提出用B_树作为索引组织文件。提高访问速度、减少时间。,内存,E.G:用二叉树组织文件，当文件的记录个数为100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！,50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,数据文件,文件头，可常驻内存,文件访问示意图：索引文件、数据文件存在盘上,7、B_树和B+树2、B_树是一种多分支数，首先介绍m阶B_树：定义：m阶B_树满足或空，或：A、根结点要么是叶子，要么至少有两个儿子B、除根结点和叶子结点之外，每个结点的儿子个数为:m/2K1且Kn的结点的地址（指在该B_树中）注意：K1=K2=.m/2-1;则借一个关键字过来。处理结束。C、并：若该结点的左或右邻居结点的关键字的个数为m/2-1;则执行合并结点的操作。如结点原为：（.(Ki,Ai),(Ki+1,Ai+1),.）（A0,(K1,A1)）（A0,(K1,A1)）K1L,第L层：找到了被删结点的替身。,7、B_树和B+树,例如：3阶B_树的删除操作。m=3,m/2-1=1;至少1个关键字，二个儿子结点。,3,24,45,5390,37,100,50,61，70,被删关键字,3,24,45,6190,37,100,53,70,借：向被删结点方向旋转,假定再删除该关键字,3,24,45,90,37,100,61，70,假定再删除该关键字,3，24,45,90,100,61，70,3，24,4590,100,61，70,并,并,并,并：和父结点的一个关键字、及邻居合并。有可能进行到根，使B_树的深度降低一层！,B+树,B+树可以看作是B_树的一种变形，在实现文件索引结构方面比B_树使用得更普遍。一棵m阶B+树可以定义如下：树中每个非叶结点最多有m棵子树；根结点(非叶结点)至少有2棵子树。除根结点外,其它的非叶结点至少有m/2棵子树；有n棵子树的非叶结点有n-1个关键码。所有叶结点都处于同一层次上，包含了全部关键码及指向相应数据对象存放地址的指针，且叶结点本身按关键码从小到大顺序链接；,每个叶结点中的子树棵数n可以多于m，可以少于m，视关键码字节数及对象地址指针字节数而定。若设结点可容纳最大关键码数为m1，则指向对象的地址指针也有m1个。结点中的子树棵数n应满足nm1/2,m1。若根结点同时又是叶结点，则结点格式同叶结点。所有的非叶结点可以看成是索引部分，结点中关键码Ki与指向子树的指针Pi构成对子树(即下一层索引块)的索引项(Ki,Pi)，Ki是子树中最小的关键码。,特别地，子树指针P0所指子树上所有关键码均小于K1。结点格式同B_树。叶结点中存放的是对实际数据对象的索引。在B+树中有两个头指针：一个指向B+树的根结点，一个指向关键码最小的叶结点。可对B+树进行两种搜索运算：,循叶结点链顺序搜索另一种是从根结点开始，进行自顶向下，直至叶结点的随机搜索。在B+树上进行随机搜索、插入和删除的过程基本上与B_树类似。只是在搜索过程中，如果非叶结点上的关键码等于给定值，搜索并不停止，而是继续沿右指针向下，一直查到叶结点上的这个关键码。B+树的搜索分析类似于B_树。B+树的插入仅在叶结点上进行。每插入一个关键码-指针索引项后都要判断结点中的子树棵数是否超出范围。,当插入后结点中的子树棵数nm1时，需要将叶结点分裂为两个结点，它们的关键码分别为(m1+1)/2和(m1+1)/2。并且它们的双亲结点中应同时包含这两个结点的最小关键码和结点地址。此后，问题归于在非叶结点中的插入了。在非叶结点中关键码的插入与叶结点的插入类似，但非叶结点中的子树棵数的上限为m，超出这个范围就需要进行结点分裂。在做根结点分裂时，因为没有双亲结点，就必须创建新的双亲结点，作为树的新根。这样树的高度就增加一层了。,B+树的删除仅在叶结点上进行。当在叶结点上删除一个关键码-指针索引项后，结点中的子树棵数仍然不少于m1/2，这属于简单删除，其上层索引可以不改变。如果删除的关键码是该结点的最小关键码，但因在其上层的副本只是起了一个引导搜索的“分界关键码”的作用，所以上层的副本仍然可以保留。如果在叶结点中删除一个关键码-指针索引项后，该结点中的子树棵数n小于结点子树棵数的下限m1/2，必须做结点的调整或合并工作。,删除18,删除12,如果右兄弟结点的子树棵数已达到下限m1/2，没有多余的关键码可以移入被删关键码所在的结点，这时必须进行两个结点的合并。将右兄弟结点中的所有关键码-指针索引项移入被删关键码所在结点，再将右兄弟结点删去。,删除33进行结点合并,结点的合并将导致双亲结点中“分界关键码”的减少，有可能减到非叶结点中子树棵数的下限m/2以下。这样将引起非叶结点的调整或合并。如果根结点的最后两个子女结点合并，树的层数就会减少一层。,郑州诚诺数据恢复正式加入海月数据恢复成功签约成为海月(国际)郑州数据恢复中心网站总部分部希望大家以后多多关注谢谢大家,
展开阅读全文