《b树的结构详细讲解》由会员分享，可在线阅读，更多相关《b树的结构详细讲解（20页珍藏版）》请在金锄头文库上搜索。
1、,7、B_ 树和 B+ 树 1、为什么采用B_ 树和 B+ 树： 大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次 访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。 在 1970 年由 R bayer 和 E macreight 提出用B_ 树作为索引组织文件。提高访问速度、减少时间。,内存,E.G: 用二叉树组织文件，当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！,50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索
2、引文件,数据文件,文件头，可常驻内存,文件访问示意图：索引文件、数据文件存在盘上,7、B_ 树和 B+ 树 2、B_ 树是一种多分支数，首先介绍 m 阶 B_ 树： 定义： m 阶 B_ 树满足或空，或： A、根结点要么是叶子，要么至少有两个儿子 B、除根结点和叶子结点之外，每个结点的儿子个数为: m/2 K1 且 Kn 的结点的地址（指在该 B_ 树中） 注意：K1 =K2 = . = Kn D、所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。,7、B_ 树和 B+ 树 例如：m = 4 阶 B_ 树。除根结点和叶子结点之外，每个结点的儿子个数 至少为 m/2 = 2
3、个；结点的关键字个数至少为 1 。该 B_ 树的深度为 4。 叶子结点都在第 4 层上。,1，99,3，47，58，64,1，39,1，27,1，11,2，43，78,1，18,1，35,第 1 层,第 2 层,第 3 层(L层),第 4 层(L1层),7、B_ 树和 B+ 树 3、B_ 树的查找代价分析： 查找过程，类似于二叉树的查找。如查找关键字为 KEY 的记录。 从根开始查找，如果 Ki = KEY 则查找成功，Ri 为关键字为 KEY 的记录的地址。 若 Ki Kn; 查找 An指向的结点 若 找到叶子，则查找失败。 注意：每次查找将去掉 （s-1）/s 个分支，比二分查找快得多。
4、设关键字的总数为 N ，求 m阶 B_ 树的最大层次 L。 层次 结点数 关键字的个数（最少） 1 1 1 2 2 2（ m/2 -1） 3 2（ m/2 ） 2（ m/2 ） （ m/2 -1） 4 2（ m/2 ） 2 2（ m/2 ）2 （ m/2 -1） L 2（ m/2 ）L-2 2（ m/2 ）L-2 （ m/2 -1） L+1 2（ m/2 ）L-1 所以，N=1 2（ m/2 -1） +.+ 2（ m/2 ）L-2 （ m/2 -1） = 2 m/2 L-1 -1 故：Llog （N+1）/2）+ 1,7、B_ 树和 B+ 树 3、B_ 树的查找代价分析： 设关键字的总数为 N
5、 ，求 m阶 B_ 树的最大层次 L。 故：Llog m/2 （N+1）/2）+ 1 设 N 1000，000 且 m256 ，则 L = 3；最多 3 次访问外存可找到所有的记录。,4、B_ 树的插入操作 1、确定插入位置，将结点插入到第 L 层（注意：第 L+1 层为叶子结点） 2、找到插入位置，将关键字和其它信息按序插入。 3、若被插入结点的关键字个数 m-1, 则该结点满。必须分裂成两个结点。否则不满结束。 如结点原为： （m-1, A0, (K1, A1), (K2, A2), (Km-1, Am-1)） 插入一个关键字之后变为： （m, A0, (K1, A1), (K2, A2)
6、, (Km, Am)） 该结点将进行分裂： . (K m/2 , p ) . （m/2-1, A0, (K1, A1), (K m/2 , A m/2 )） （m- m/2 , A m/2 , (Km, Am)） 生成新结点 p, 将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。,P,P,(K m/2 , p ) 数据项插入上层结点之中,7、B_ 树和 B+ 树,例如：3 阶 B_ 树的插入操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个儿子结点。,3，12,7 24 30,24，30,45，70,53,90,26,100,39,50,61,85,3,45
7、，70,53,90,26,100,39,50,61,85,12,30,3,24 45 70,53,90,26,100,39,50,61,85,12,7,30,3,24,53,90,26,100,39,50,61,85,12,7,45,70,7插入,7、B_ 树和 B+ 树,5、B_ 树的删除操作 1、查找具有给定键值的关键字 Ki 2、如果 在第 L 层，可直接删除（注意：第 L+1 层为叶子结点），转 4 。 3、否则，则首先生成 “替身”。用 的右子树中的最左面的结点的关键字值，即 处于第 L 层上的最小 关键字值取代 。然后，删除第 L 层上的该关键字。 4、从第 L 层开始进行删除。
8、A、不动：若删除关键字值的那个结点的关键字的个数仍处于 m/2 -1和 m-1之间。则结束。 B、借：若删除关键字值的那个结点的关键字的个数原为 m/2 -1 。而它们的左或右邻居结 点的关键字的个数 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_ 树的删除操作。
9、m=3, m/2 - 1 = 1; 至少 1 个关键字，二个儿子结点。,3,24,45,53 90,37,100,50,61，70,被删关键字,3,24,45,61 90,37,100,53,70,借：向被删结点方向旋转,假定再删除该关键字,3,24,45,90,37,100,61，70,假定再删除该关键字,3，24,45,90,100,61，70,3，24,45 90,100,61，70,并,并,并,并：和父结点的一个关键字、及邻居合并。有可能进行到根，使B_ 树的深度降低一层！,B+树,B+树可以看作是B_树的一种变形，在实现文件索引结构方面比B_树使用得更普遍。 一棵 m 阶B+树可以定
10、义如下： 树中每个非叶结点最多有 m 棵子树； 根结点 (非叶结点) 至少有 2 棵子树。除根结点外, 其它的非叶结点至少有 m/2 棵子树；有 n 棵子树的非叶结点有 n-1 个关键码。 所有叶结点都处于同一层次上，包含了全部关键码及指向相应数据对象存放地址的指针，且叶结点本身按关键码从小到大顺序链接；,每个叶结点中的子树棵数 n 可以多于 m，可以少于 m，视关键码字节数及对象地址指针字节数而定。 若设结点可容纳最大关键码数为 m1，则指向对象的地址指针也有 m1 个。 结点中的子树棵数 n 应满足 n m1/2, m1。 若根结点同时又是叶结点，则结点格式同叶结点。 所有的非叶结点可以看
11、成是索引部分，结点中关键码 Ki 与指向子树的指针 Pi 构成对子树 (即下一层索引块) 的索引项 ( Ki, Pi )，Ki 是子树中最小的关键码。,特别地，子树指针 P0 所指子树上所有关键码均小于 K1。结点格式同B_树。 叶结点中存放的是对实际数据对象的索引。 在B+树中有两个头指针：一个指向B+树的根结点，一个指向关键码最小的叶结点。 可对B+树进行两种搜索运算：,循叶结点链顺序搜索 另一种是从根结点开始，进行自顶向下，直至叶结点的随机搜索。 在B+树上进行随机搜索、插入和删除的过程基本上与B_树类似。只是在搜索过程中，如果非叶结点上的关键码等于给定值，搜索并不停止，而是继续沿右指针
12、向下，一直查到叶结点上的这个关键码。 B+树的搜索分析类似于B_树。 B+树的插入仅在叶结点上进行。每插入一个关键码-指针索引项后都要判断结点中的子树棵数是否超出范围。,当插入后结点中的子树棵数 n m1 时，需要将叶结点分裂为两个结点，它们的关键码分别为 (m1+1)/2 和 (m1+1)/2。并且它们的双亲结点中应同时包含这两个结点的最小关键码和结点地址。此后，问题归于在非叶结点中的插入了。 在非叶结点中关键码的插入与叶结点的插入类似，但非叶结点中的子树棵数的上限为 m，超出这个范围就需要进行结点分裂。 在做根结点分裂时，因为没有双亲结点，就必须创建新的双亲结点，作为树的新根。这样树的高度
13、就增加一层了。,B+树的删除仅在叶结点上进行。当在叶结点上删除一个关键码-指针索引项后，结点中的子树棵数仍然不少于 m1/2，这属于简单删除，其上层索引可以不改变。 如果删除的关键码是该结点的最小关键码，但因在其上层的副本只是起了一个引导搜索的“分界关键码”的作用，所以上层的副本仍然可以保留。 如果在叶结点中删除一个关键码-指针索引项后，该结点中的子树棵数 n 小于结点子树棵数的下限 m1/2，必须做结点的调整或合并工作。,删除18,删除12,如果右兄弟结点的子树棵数已达到下限m1/2，没有多余的关键码可以移入被删关键码所在的结点，这时必须进行两个结点的合并。将右兄弟结点中的所有关键码-指针索引项移入被删关键码所在结点，再将右兄弟结点删去。,删除33进行 结点合并,结点的合并将导致双亲结点中“分界关键码”的减少，有可能减到非叶结点中子树棵数的下限 m/2 以下。这样将引起非叶结点的调整或合并。 如果根结点的最后两个子女结点合并，树的层数就会减少一层。,郑州诚诺数据恢复正式加入海月数据恢复成功签约成为 海月(国际)郑州数据恢复中心 网站总部 分部 希望大家以后多多关注 谢谢大家,
