PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

抽但慕
5 years ago
Views:

1 第十章文件外部排序与搜索赵建华南京大学计算机系

2 文件什么是文件文件是存储在外存上的数据结构文件分操作系统文件和数据库文件操作系统中的文件是流式文件 : 是没有结构的字符流数据库文件是具有结构的数据集合数据结构中讨论的是数据库文件操作系统对文件是按物理记录读写的, 在数据库中文件按页块存储和读写

3 文件的组成文件由记录组成 ; 记录由若干数据项组成记录 : 文件存取的基本单位数据项 : 文件可使用的最小单位逻辑记录 : 面向用户的基本存取单位物理记录 : 面向外设的基本存取单位主关键码项 : 唯一标识一个记录的数据项或数据项集 ;

4 文件的结构文件结构包括 : 逻辑结构存储结构和操作逻辑结构是线性结构, 各个记录以线性方式排列存储结构 : 文件在外存上的组织方式, 与文件特性有关顺序组织直接存取组织 ( 散列组织 ) 索引组织文件的操作 : 在逻辑结构上定义, 在存储结构上具体实现

5 顺序文件 (Sequential File ) 顺序文件 : 记录按进入文件的先后顺序存放, 其逻辑顺序与物理顺序一致通常可存放在顺序存取设备 ( 如磁带 ) 或直接存取设备 ( 如磁盘 ) 当存放在顺序存取设备上时只能按顺序搜索法存取 ; 存放在直接存取设备上时, 可以使用顺序搜索法折半搜索法等存取顺序有序文件 : 文件的记录按主关键码有序顺序无序文件 : 否则

6 直接存取文件 (Direct Access File) 记录的逻辑顺序与物理顺序不一定相同可通过关键码可直接确定记录地址利用散列技术组织文件处理类似散列法, 但它是存储在外存上的

7 索引文件 (Indexed File) 索引文件由索引表和主文件组成 0 1k 2k 3k 4k 5k 6k 7k 索引表数据表未婚教师女林青 51 未婚实验员男胡江 17 已婚教师男周斌 47 已婚教师男岳跋 24 未婚实验员女刘琪 95 已婚教务员男王璐 03 已婚教师男李斯 08 已婚教师女张珊 83 婚否职务性别姓名职工号 3k k 51 5k 47 4k 24 6k 17 1k 08 2k 03 addr key

8 索引文件 (Indexed File) 索引表是按关键码有序的表, 指示逻辑记录与物理记录间的对应关系对顺序文件的索引 : 稀疏索引主文件也按关键码有序一组记录只需要一个索引项对非顺序文件的索引 : 稠密索引主文件中记录未按关键码有序每个主文件记录必须对应一个索引项当对象在外存中按加入顺序存放时, 必须采用稠密索引结构

9 多级索引结构如果文件记录数目大到索引表本身也很大, 则需要通过分批多次读取外存才能把索引表搜索一遍解决方法建立索引的索引 ( 二级索引 ) 二级索引的一个索引项对应一个一级索引块记录该一级索引块的最大关键码及存储地址二级索引可以常驻内存, 如果二级索引仍不能放入内存

10 root (23, ) (49, ) (95, ) (06, ) (15, ) (23, ) (32, ) (41, ) (49, ) (60, ) (95, ) head

11 四级索引三级索引二级索引一级索引数据区多级索引结构形成 m 路搜索树

12 多级索引结构形成 m 叉树每个分支结点表示一个索引块, 最多存放 m 个索引项每个索引项给出各子树结点 ( 较低一级索引块 ) 的最大关键码和结点地址叶结点中各索引项给出在数据表中存放的记录的关键码和存放地址这种 m 叉树用来作为多级索引, 就是 m 路搜索树

13 静态索引结构的 m 路搜索树结构在初始创建数据装入时就已经定型 ; 在整个运行期间, 树的结构不发生变化动态索引结构的 m 路搜索树在系统运行期间, 树的结构随数据的增删及时调整, 以保持最佳的搜索效率

14 动态 m 路搜索树的递归定义空树是 m 路搜索树, 满足如下性质的树也是 m 路搜索树 : 根最多有 m 棵子树, 并具有如下的结构 : ( n, P 0, K 1, P 1, K 2, P 2,, K n, P n ) 其中, P i 是指向子树的指针, 0 i n<m; K i 是关键码, 1 i n<m K i < K i+1, 1 i < n P i 中的关键码都小于 K i+1 且大于 K i,0 < i < n P n 中的关键码都大于 K n ; P 0 中的关键码都小于 K 1 子树 P i 也是 m 路搜索树,0 i < n

15 一棵 3 路搜索树的示例 a b c d e 35

16 m 路搜索树的最大结点数若已知 m 路搜索树的度 m 和它的高度 h, 则树中的最大结点个数为 : h i 1 m i-1 1 m 1 每个结点中最多有 m-1 个关键码, 在一棵高度为 h 的 m 路搜索树中关键码最大个数为 m h -1 高度 h=3 的二叉搜索树, 关键码最大数为 7; 高度 h=4 的 3 路搜索树, 关键码最大数为 = 80 m h 1

17 m 路搜索树的搜索算法在 m 路搜索树上的搜索过程是一个在结点内搜索和自根结点向下逐个结点搜索的交替的过程 a root 搜索 35 b 10 c d e 35

18 template <class T> Triple<T> Mtree<T>::Search (const T& x) { /* 用关键码 x 搜索驻留在磁盘上的 m 路搜索树各结点格式为 n,p[0],(k[1],p[1]),,(k[n],p[n]), n < m 函数返回一个类型为 Triple(r,i,tag) 的记录 tag = 0, 表示 x 在结点 r 中找到, 该结点的 k[i] 等于 x; tag = 1, 表示没有找到 x, 可插入结点为 r, 插入到该结点的 k[i] 与 k[i+1] 之间 */

19 Triple result; // 记录搜索结果三元组 GetNode (root); // 从盘上读取结点 root MtreeNode<T> *p = root, *q = NULL; //p 是扫描指针,q 是父结点指针 while (p!= NULL) { // 从根开始检测, 直到叶子结点 int i = 0; p->key[(p->n)+1] = MaxValue; // 结束标记 while (p->key[i+1] < x) i++; // 在结点内搜索 // 循环结束时,i 指向结点中最后一个小于 x 的元素 }; if (p->key[i+1] == x) { // 结点内搜索成功 result.r = p; result.i = i+1; result.tag = 0; return result; } q = p; p = p->ptr[i]; // 此时 p->key[i+1] 必大于 x // 本结点无 x, q 记下当前结点, p 下降到子树 GetNode(p); // 从磁盘上读取结点 p } result.r = q; result.i = i; result.tag = 1; return result; // 搜索失败, 返回插入位置

20 m 路搜索树的效率考虑提高搜索树的路数 m, 可改善搜索性能但 m 过大可导致一个结点不能一次读入内存也导致读入一个结点的时间增加对于给定的 m 当搜索树平衡时, m 路搜索树的性能接近最佳 B 树 : 一种平衡的 m 路搜索树

21 B 树一棵 m 阶 B 树是一棵平衡的 m 路搜索树或者是空树, 或者是满足下列性质的树 : 根结点至少有 2 个子女除根结点以外的所有结点 ( 不包括失败结点 ) 至少有 m/2 个子女所有的失败结点都位于同一层失败结点当 x 不在树中时到达的结点这些结点实际不存在, 指向它们的指针为 NULL 它们不计入树的高度

22 m 阶 B 树是特殊的 m 路搜索树原来 m 路搜索树定义中的规定在 m 阶 B 树中都保留额外的规定是为了提高搜索效率, 避免退化在 B 树的每个结点包含有一组指针 recptr[m+1], 指向实际记录的存放地址 key[i] 与 recptr[i] 形成索引项 (key[i], recptr[i]), 通过 key[i] 可找到某个记录的存储地址 recptr[i] 在讨论 B 树结构的操作时先不涉及 recptr[i], 因此在后续讨论中该指针不出现

23 一棵 B 树是平衡的 m 路搜索树, 但一棵平衡的 m 路搜索树不一定是 B 树非 B 树 root B 树 30 root

24 B 树类和 B 树结点类的定义 template <class T> class Btree : public Mtree<T> { //B 树类定义 // 继承 m 叉搜索树的所有属性和操作, //Search 从 Mtree 继承, MtreeNode 直接使用 public: Btree(); // 构造函数 bool Insert (const T& x); // 插入关键码 x bool Remove (T& x); // 删除关键码 x };

25 B 树的搜索算法 B 树的搜索算法就是 m 路搜索树 Mtree 上的搜索算法交替进行结点内搜索以及循某一路径向下搜索搜索成功 : 报告结点地址及在结点中的关键码序号 ; 搜索不成功 : 报告最后停留的叶结点地址及新关键码在结点中可插入的位置 B 树的搜索时间与 B 树的阶数 m 和 B 树的高度 h 直接有关, 必须加以权衡

26 在 B 树上进行搜索, 搜索成功所需时间 : 关键码所在的层次 ; 搜索不成功所需时间 : 树的高度 B 树高度 h 与关键码个数 N 的关系如下 : 让 B 树每层结点个数达到最大, 得到最小高度每个结点有 m 个子结点 N (m h -1) h log m (N+1)

27 让 m 阶 B 树中每层结点个数最少, 高度达到最大设树中关键码个数为 N, 从 B 树的定义知 : 1 层 :1 个结点 2 层 : 至少 2 个结点 3 层 : 至少 2 m/2 个结点 4 层 : 至少 2 m/2 2 个结点如此类推, h 层 : 至少有 2 m/2 h-2 个结点失败结点在第 h+1 层, 失败结点个数为 N+1 关键码有 N 个, 而失败数据与已有关键码交错排列

28 因此, 有 N+1 = 失败结点数 = 位于第 h+1 层的结点数 2 m/2 h-1 N 2 m/2 h-1-1 h-1 log m/2 ((N+1)/2) h log m/2 ((N+1)/2)+1 示例 : 若 B 树的阶数 m = 199, 关键码总数 N = , 则 B 树的高度 h 不超过 log = 4

29 m 值的选择如何选择 m 值, 使得在 B 树中找到关键码 x 的时间总量达到最小这个时间由两部分组成 : 从磁盘中读入结点 ( 耗时 ) 在结点内搜索 x( 较快 ) 因此搜索时间和高度相关提高 B 树的阶数 m 减少高度减少读入结点的次数, 减少读磁盘的次数减少搜索时间但是,m 受到内存可使用空间的限制

30 B 树的插入 B 树中, 每个非失败结点的关键码个数 [ m/2-1, m-1] 插入的过程在某个叶结点开始如果插入后关键码个数超出 m-1, 则分裂结点 ; 否则不需要其它操作 ; 叶结点的分裂可能引起父结点的分裂 ; 分裂过程可能逐步向上传播

31 节点分裂的原则在已经有 m-1 个关键码的结点 p 中再插入一个关键码后 : ( m, P 0, K 1, P 1, K 2, P 2,, K m, P m ) 结点 p 分裂成两个结点 p 和 q: 结点 p: ( m/2-1, P 0, K 1, P 1,, K m/2-1, P m/2-1 ) 结点 q: (m- m/2, P m/2, K m/2 +1, P m/2 +1,, K m, P m ) 中间的关键码 K m/2 与指向新结点 q 的指针形成一个二元组 ( K m/2, q ), 插入到父结点中去父结点中关键码加一, 可能引起父结点的进一步分裂

32 结点分裂的示例 p p n P0 K1 P1 K2 P m = 3 n P0 K1 P1 K2 P2 K3 P 加入 139, 结点溢出结点分裂 P n P0 K1 P n P0 K1 P q n P0 K1 P

33 示例 : 从空树开始建立 3 阶 B 树 n=1 加入 n=2 加入 n=3 加入 n=5 加入 49, n=6 加入

34 n=7 加入设 B 树高 h, 则搜索时最多读盘 h 次在插入时, 需要首先进行搜索, 然后可能自底向上地分裂结点最坏情况下从被插关键码所在叶结点到根的路径上的所有结点都要分裂

35 B 树的插入算法 template <class T> bool Btree<T>::Insert (const T& x) { // 将关键码 x 插入到一个 m 阶 B 树中 Triple<T> loc = Search(x); // 搜索 x 的插入位置 if (!loc.tag) return false; //x 已存在, 不插入 MtreeNode<T> *p = loc.r, *q; MtreeNode<T> *ap = NULL, *t; //r 是插入结点 //ap 是右邻指针

36 T K = x; int j = loc.i; //(K,ap) 形成二元组, 插入到 p 指向的结点中 while (1) { if (p->n < m-1) { // 简单情况, // 关键码个数未超出 insertkey (p, j, K, ap);// 插入, 且 p->n 加 1 PutNode (p); // 输出结点 p return true;} int s = (m+1)/2; // 准备分裂结点 insertkey (p, j, K, ap); // 先插入 q = new MtreeNode<T>; // 建立新结点 q // 把 p 中结点第 s 到第 m 个关键码 // 移动到 q move(p, q, s, m);

37 K = p->key[s]; ap = q; //(K,ap) 形成新二元组, 插入到 p 的父结点 if (p->parent!= NULL) { // 非根的情况 t = p->parent; GetNode(t); // 读取父结点 t j = 0; t->key[(t->n)+1] = MAXKEY;// 设监视哨 while (t->key[j+1] < K) j++; // 顺序搜索 q->parent = p->parent; // 新结点的双亲 PutNode(p); PutNode(q);// 输出结点到外存 p = t; //p 上升到双亲, 继续调整 } //else 处理根结点的分裂, 见下页

38 }; else { } }//end of while(2) // 原来 p 指向根结点, 需要要产生新根 root = new MtreeNode<T>; root->n = 1; root->parent = NULL; root->key[1] = K; root->ptr[0] = p; root->ptr[1] = ap; q->parent = p->parent = root; PutNode(p); PutNode(q); PutNode(root); return true; 当分裂一个非根的结点时需要向磁盘写出 2 个结点, 当分裂根结点时需要写出 3 个结点

39 算法效率分析假设内存工作区足够大, 向下搜索时读入的结点在插入完成前不需要再次读入在完成插入操作时读 / 写磁盘的最大次数找插入 ( 叶 ) 结点向下读盘次数 + + 分裂非根结点时写盘次数 + + 分裂根结点时写盘次数 = = h+2(h-1)+3 = 3h+1

40 B 树的删除在 B 树中删除一个关键码分成两大步骤 : 第一步 : 找到并删除关键码通过数据移动, 换为叶结点上的删除操作第二步 : 如果叶子结点的关键码数量低于下界, 通过合并调整二叉树, 使之满足 B 树的要求

41 B 树的删除第一步删除过程找到关键码所在结点, 删去这个关键码若所在结点不是叶结点, 且被删关键码为 K i,1 i n, 将该结点的 P i 所指子树中的最小关键码 x 移动到 K i 所在的位置 ; 然后在 x 所在的叶结点中删除 x 实际上把所有的删除操作变成了叶结点上的删除操作

42 m = 3 删除 50 删除 50 b 30 a d 10 e 40 f g 65 h c 用 55 取代非叶结点删除

43 1. 被删关键码在根结点, 且删除前关键码个数 n 2, 则直接删去该关键码, 并写回磁盘 m = 3 叶结点的删除删除被删关键码不在根结点, 且删除前关键码个数 n m/2, 则直接删去该关键码, 写回磁盘

44 m = 3 b 30 a d 10 e 40 f g 65 h c 删除 55 简单删除 b 30 a 50 删除 d 10 e 40 f 58 g 65 h c

45 被删关键码所在叶结点删除前关键码个数 n = m/2-1, 则需要进行调整 a) 向兄弟结点借关键码 : 右兄弟 ( 或左兄弟 ) 结点的关键码个数 n m/2 ; 从父结点获取一个关键码 ; 再从兄弟结点移动一个关键码到父结点 ; 这个过程不会向上传递 b) 兄弟也没有余粮 : 右兄弟 ( 或左兄弟 ) 结点的关键码个数 n= m/2-1; 合并两个兄弟结点父结点中两个兄弟之间的关键码一起移动到新结点父结点的关键码数量减少, 可能会引起进一步的调整!

46 3. 所在叶结点删除前关键码个数 n = m/2-1, 右兄弟 ( 或左兄弟 ) 结点的关键码个数 n m/2 : a) 父结点中刚大于 ( 或小于 ) 被删关键码的关键码 K i (1 i n) 下移 ; b) 右兄弟 ( 或左兄弟 ) 结点中最小 ( 或最大 ) 关键码上移到父结点中 K i 位置 ; c) 右兄弟 ( 或左兄弟 ) 结点中最左 ( 或最右 ) 子树指针平移到被删关键码所在结点中最后 ( 或最前 ) 子树指针位置 ; d) 右兄弟 ( 或左兄弟 ) 结点中, 将被移走的关键码和指针位置用剩余的关键码和指针填补调整再将结点中的关键码个数减 1

47 m = 3 a 50 删除 65 b 30 d 10 e 40 f g 65 h 结点联合调整 b 30 a 50 c d 10 e 40 f g 70 h 80 c 调整 g,c,h 删除 65

48 4. 所在叶结点删除前关键码个数 n = m/2-1, 若右兄弟 ( 或左兄弟 ) 结点的关键码个数 n = m/2-1 设它们的父结点是 p, 两个结点分别是 P i 与 P i+1 按如下方法合并结点 a) 保留 P i 所指结点, 把 p 中的关键码 K i+1 下移到 P i 所指的结点中 b) 把 P i+1 所指结点中的全部指针和关键码都照搬到 P i 所指结点的后面删去 P i+1 所指的结点 c) 移动结点 p 中后面的关键码和指针, 填补因删除关键码 K i+1 和指针 P i+1 留下的空位 d) 修改结点 p 和选定保留结点的关键码个数

49 双亲结点中的关键码个数减少了, 可能引起进一步合并和移动若双亲结点是根结点如果结点关键码个数减到 0: 删去双亲结点, 合并得到的结点成为新的根结点 ; 否则将双亲结点与合并后保留的结点都写回磁盘删除处理结束若双亲结点不是根结点如果关键码个数减到 m/2-2, 又要进行下一轮调整最坏情况下这种结点合并处理要自下向上直到根结点否则将需要的结点写回磁盘删除处理结束

50 m = 3 a 50 删除 55 b 30 d 10 e 40 f 55 g 60 h 结点合并 b 30 a 50 c d 10 e 40 f h 80 c 80 删除 55 合并 f, g

51 m = 3 删除 50 删除 50 b d 10 e 40 f g 65 h 删除 55 b a a c 非叶结点删除删除 55 d 10 e 40 f 58 g 65 h c 用 55 取代用 58 取代

52 b 30 a d 10 e 40 f g 65 h c 合并 f, g b 30 a d 10 e 40 f h c 结点合并与调整删除 70

53 删除 70 用 75 取代 b 30 a d 10 e 40 f h c 删除删除 75 用 80 取代调整 f, c, h d b 30 a e 40 f h c

54 a 58 删除 10 b 30 c 65 d 10 e 40 f 60 h 80 b d f 60 h 80

55 B 树的删除算法 template <class T> bool Btree<T>::Remove (const T& x) { Triple<T> loc = Search (x); // 搜索 x if (loc.tag == 1) return false; // 未找到, 不删除 MtreeNode<T> *p = loc.r, *q, *s; // 找到, 开始删除 // 接下来 : // 首先删除关键码, 如果关键码在内部结点中, // 则通过移动转换成为对叶结点的删除 // 如果有必要, 进行调整 / 合并处理

56 删除步骤 int j = loc.i; if (p->ptr[j]!= NULL) { // 非叶结点 s = p->ptr[j]; GetNode (s); // 读取子树结点 q = p; // 找最左下结点 while (s!= NULL) {q = s; s = s->ptr[0];} p->key[j] = q->key[1]; // 从叶结点替补 compress (q, 1); // 在叶结点删除 p = q; //p 指向叶结点 } else compress (p, j); // 直接删除

57 int d = (m+1)/2; // 求 m/2 while (1) { // 调整或合并 if ( p->n < d-1 ) { // 小于最小限制 j = 0; q = p->parent; // 找到双亲 GetNode (q); // 读取双亲结点 while ( j <= q->n && q->ptr[j]!= p ) j++; // 在双亲结点中确定 p 子树的序号 if (j == 0) LeftAdjust (p, q, d, j); // 调整 else RightAdjust (p, q, d, j); p = q; // 向上调整 if (p == root) break; } else break; }

58 } if (root->n == 0) { // 调整后根的 n 减到 0 p = root->ptr[0]; delete root; root = p; // 删根 root->parent = NULL; // 新根 }

59 当调整一个结点时需要从磁盘读入 1 个兄弟结点及写出 2 个结点当调整到根的子女时则需要写出 3 个结点如果我们所用的内存工作区足够大, 使得在向下搜索时, 读入的结点在做删除时不必再从磁盘读入, 那么, 在完成一次删除操作时需要读写磁盘的最大次数 = 找删除元素所在结点向下读盘次数 + 调整结点时读写盘次数 h+ 3(h-1)+1 = 4h-2

60 B+ 树一棵 m 阶 B+ 树是 B 树的特殊情形, 它与 B 树的不同之处在于 : 所有关键码都存放在叶结点中上层的非叶结点的关键码是其子树中最小 ( 或最大 ) 关键码的复写叶结点包含了全部关键码及指向相应数据记录存放地址的指针, 叶结点本身按关键码从小到大顺序链接每个非叶结点结构有两种方式处理按下层结点最大关键码复写和最小关键码复写

61 按最大关键码复写原则组织一棵 m 阶 B+ 树的结构定义如下 : 每个结点最多有 m 棵子树 ; 根结点最少有 1 棵子树, 除根结点外, 其他结点至少有 m/2 棵子树 ; 有 n 个子树的结点有 n 个关键码所有非叶结点可以看成是叶结点的索引, 结点中关键码 K i 与指向子树的指针 P i 构成对子树 ( 即下一层索引块 ) 的索引项 ( K i, P i ),K i 是子树中最大的关键码所有叶结点在同一层, 按从小到大的顺序存放全部关键码, 各个叶结点顺序链接

62 叶结点中存放的是对实际数据记录的索引, 每个索引项 ( K i, P i ) 给出数据记录的关键码及实际存储地址例如, 在一棵 4 阶 B+ 树中所有非叶结点中的子树棵数 2 n 4, 所有的关键码都出现在叶结点中, 在叶结点中关键码有序地排列上面各层结点中的关键码都是其子树上最大关键码的副本

63 m = root

64 通常在 B+ 树中有两个头指针 : 一个指向 B+ 树的根结点, 一个指向关键码最小的叶结点因此, 可以对 B+ 树进行两种搜索运算 : 循叶结点自己拉起的链表顺序搜索 ; 从根开始进行自顶向下直到叶结点的随机搜索

65 B+ 树与 B 树的不同关键码的分布, 叶结点包含了所有的关键码叶结点的定义失败结点的定义 ( 叶结点不一定符合 m 阶, 它依赖于关键码字节数与指针字节数而定为 m1)

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 六 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语树的链式存储结构子结点表表示方法静态左孩子 / 右兄弟表示法动态表示法动态左孩子 / 右兄弟表示法父指针表示法及其在并查集中的应用