数据结构第九章0.ppt

3、B-树和B+树 B-树是一种平衡的多路查找树，它在文件系统中很有用，主要用作文件的索引，它的查找涉及外存的存取。 （1）B-树的定义： 一棵m阶的B-树，或者为空树，或为满足下列特性的m叉树： ① 树中每个结点至多有m棵子树； ② 若根结点不是叶子结点，则至少有两棵子树； ③ 除根结点之外的所有非终端结点至少有?m/2? 棵子树； ④ 所有的非终端结点中包含以下信息数据： (n, A0, K1, A1, K2, …, Kn，An); 其中：Ki（i=1,2,…,n）为关键字，且KiKi+1; Ai (i=0,1,…,n)为指向子树根结点的指针，且指针Ai-1 (i=1,2, …n-1)所指子树中所有结点的关键字均大于Ki，小于Ki+1 ，A0所指子树中所有结点的关键字均小于K1，An所指子树中所有结点的关键字均大于Kn; ?m/2? -1≤n≤m -1 ，n为关键字的个数。 ⑤ 所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。 （2）B-树的查找： B-树的查找类似二叉排序树的查找，所不同的是B-树每个结点上是多关键字的有序表。 若查找某个关键字，则在到达某个结点时，先在结点（有序表）中查找，若找到，则查找成功；否则，到按照对应的指针信息指向的子树中去查找，当到达叶子结点时，则说明树中没有对应的关键字，查找失败。 即在B-树上的查找过程是一个顺指针查找结点和在结点中查找关键字交叉进行的过程。 例如：查找关键字41 （3）B-树的查找分析： B-树的查找是由两个基本操作交叉进行的过程，即： ⑴在B-树上找结点； ⑵在结点中找关键字。 由于B-树通常是存储在外存上的，操作⑴是在磁盘上进行的，就是通过指针在磁盘相对定位，将结点信息读入内存；操作(2)是在内存中进行的，即对结点中的关键字进行顺序查找或折半查找。 因为在磁盘上读取结点信息比在内存中进行关键字查找耗时多，所以，在磁盘上读取结点信息的次数，即B-树的层次树是决定B-树查找效率的首要因素。 那么，对含有n个关键字的m阶B-树，最坏情况下达到多深呢？可按二叉平衡树进行类似分析，讨论深度为k+1的m阶B-树所具有的最少结点数。 由B-树定义： 第一层至少有1个结点； 第二层至少有2个结点； 由于除根结点外的每个非终端结点至少有?m/2?棵子树，则第三层至少有2(?m/2?)个结点； … 依此类推，第k+1层至少有2(?m/2?)k-1个结点。 而k+1层的结点为叶子结点。若 m 阶B－树有n个关键字，则叶子结点即查找不成功的结点为n+1(即n个有序关键字形成的n+1个中间区域) ； 由此可得 即：在含有n个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过 （4）B-树的插入： B-树的生成也是从空树起，逐个插入关键字而得。在B-树上插入关键字与在二叉排序树上插入结点不同，关键字的插入不是在叶结点上进行的，而是在最底层的某个非终端结点中添加一个关键字。 添加关键字分两种情况： 1．若添加后，结点上关键字个数小于等于m-1(对应每个结点至多有m棵子树的限定条件)，则插入结束； 2．若添加后，该结点上关键字个数为m个，因而使该结点的子树超过了m棵，这与B-树定义不符，所以要进行调整，即结点的“分裂”。 结点的“分裂”方法为：关键字加入结点后，将结点中的关键字分成三部分，使得前后两部分关键字个数均大于等于??m/2????，而中间部分只有一个结点(即第?m/2?个关键字)。前后两部分成为两个结点，中间的一个结点将其插入到父结点中。 若插入父结点而使父结点中关键字个数为m个，则父结点继续分裂，直到插入某个父结点，其关键字个数小于m。 可见 树是从底向上生长的。 B- （5）B-树的删除： 分两种情况： 第一种情况：删除最底层结点中关键字 ① 若结点中关键字个数大于?m/2? ?1(对应每个非终端结点至少有?m/2?棵子树的限定条件)，直接删去，如下图所示： 删除12 ② 若被删结点中关键字个数等于?m/2? ?1，删除后结点中关键字个数小于?m/2? ?1，不满足B-树定义，需调整。也有两种情况： a) 与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( ?m/2? ?? )，则需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中，而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。 删除50 b) 若被删结点