最新十章节外部排序精品课件.ppt
十章节外部排序十章节外部排序p外存信息的存取p外部排序的基本方法归并排序法p多路平衡归并p置换-选择排序 6 8 6 8 9 8 9 6 8 90 9 15 8 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 90 10 9 20 15 8 12 90 14 22 24 15 16 17 92 14 22 24 25 16 17 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并胜者树路合并胜者树 重构后的胜者树重构后的胜者树 重构胜者树时，从根结点至新补入记录的叶结点的重构胜者树时，从根结点至新补入记录的叶结点的路径上的所有结点都必须更新。路径上的所有结点都必须更新。 5 2 2 0 4 0 1 3 6 90 1 3 6 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 90 10 9 20 15 8 12 90 14 22 24 15 16 11 92 14 22 24 25 16 11 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并败者树 重构后的败者树败者树的特点：记录败者，胜者参加下一轮比赛 败者树的优点：重构时修改结点较少01 2 3 4 5 64ls05ls01 2 3 4 5 60 4 5 2 0 1 3 6 90 0 10 9 20 6 8 12 1 2 3 4 5 6调整败者树的方法: 将新补充的结点与其双亲结点比较, 败者留在该双亲结点,胜者继续向上直至树根的双亲以在b4补充15为例154与3比较4与2比较42与5比较25 7 7 7 7 7 7 7 90 0 10 9 20 6 8 12 1 2 3 4 5 6k-路归并对内存的要求路归并对内存的要求 至少要有k个输入缓冲区和一个输出缓冲区建败者树的过程7 -1初始化败者树调整b66调整b55调整b44调整b334调整b22调整b1124调整b0054数据结构数据结构 (依据：败者树为完全二叉树)p主：b0. k b0. k-1k个叶结点 ，存放k个输入归并段中当前 参加归并的记录（缓冲区） bk虚拟记录，该关键字取可能的最小值minkeyp辅：ls0. k-1 不含叶结点的败者树 存放最后胜出的编号（ls0）以及所记录的败者编号处理步骤处理步骤p建败者树ls0. k-1p重复下列操作直至k路归并完毕n将将bls0写至输出归并段写至输出归并段n补充记录补充记录(某归并段变空时某归并段变空时,补补 )，调整败者树，调整败者树void CreateLoserTree() bk = MINKEY; for (i = 0; i = 0; i+) Adjust(i);void Adjust(int s) for (t = (s + k) / 2; t 0; t /= 2) if (bs blst) s lst; ls0 = s;void K_Merge() for (i = 0; i k; i+) input(i); /* 第i路输入一个元素到bi */ CreateLoserTree(ls); while (bls0 != MAXKEY) q = ls0; output(bq); input(q); Adjust(q); 置 换 - 选 择 排 序目标目标 扩大初始归并段长度，突破内存工作区容量(设w个记录)的限制。置换置换-选择排序原理选择排序原理 内存 外存 原始文件 内存工作区 FI WA 初始归并段文件 (w个记录) FO 为简化问题，设每个物理块存放一个记录为简化问题，设每个物理块存放一个记录1) 从FI输入w个记录到工作区WA；2) 在FO中标记一个归并段开始；3) 从WA中选出最小关键字记录，记为minimax记录；4) 将minimax记录输出到FO中；5) 从FI输入下一个记录到WA中；6) 在WA中的关键字比minimax大的记录中选出关键字最小的记录 6.1) 若不能选到，在FO中标记一个归并段结束； 若由于WA为空而未选出，则结束处理； 否则，标记下一个归并段开始，转 3) 6.2) 否则，将选出的记录作为新的minimax记录，转 4) FO WA(4个记录) FI 空 空 36,21,33,87,23,7,62,16, 54,43,29, 空 36,21,33,87 23,7,62,16,54, 43,29, 21 36,23,33,87 7,62,16,54, 43,29, 21,23 36,7,33,87 62,16,54,43,29, 21,23,33 36,7,62,87 16,54,43,29, 21,23,33,36 16,7,62,87 54,43,29, 21,23,33,36,62 16,7,54,87 43,29, 21,23,33,36,62,87 16,7,54,43 29, 21,23,33,36,62,87|7 16,29,54,43 p处理步骤处理步骤 1)初始化败者树： 1.1)所有外部结点： rnum=0; key=0；所有内部结点置0； 1.2)对外部结点从编号w-1至0 从外存FI读入记录，置段号为1，并调整败者树 2)置当前段号为1； 3)若ls0指示的外部结点属于当前段，输出该记录； 否则,当前段号+1，输出段标后再输出该记录； 4)若FI未空，从FI补充记录， 若补充key此前输出记录的key，则rnum=当前段号+1 否则rnum=当前段号 否则补虚记录：key=; rnum=当前段号+1； 5)调整败者树 转3）直至所有记录被输出调整败者树原则：段号小者为胜者段号相同，关键字小的为胜者p所得初始排序段的长度不等p当输入文件记录的关键字大小随机分布时，初始归并段的平均长度为内存工作区大小w的两倍最 佳 归 并 树文件经过置换文件经过置换-选择排序之后，得到长度不等的初始归并选择排序之后，得到长度不等的初始归并段，进行段，进行k路归并时，初始归并段的不同搭配，会导致路归并时，初始归并段的不同搭配，会导致归并过程中归并过程中I/O的次数的次数不同。不同。设有9个初始归并段，记录个数(长度)分别为： 9，30，12，18，3，17，2，6，24 121 121 51 38 32 30 32 59 9 30 12 18 3 17 2 6 24 11 9 12 17 18 24 2 3 6(9+30+12+18+3+17+2+6+24)2 (2+3+6) 3+(9+12+17+(51+38+32) 2 +18+24) 2+30 1 2=484 =4463-路归并所有叶结点加权外通路长度的所有叶结点加权外通路长度的2 2倍倍IO方案二方案一最佳归并树即k叉(阶)哈夫曼树。 设初始归并段为m个，进行k-路归并1）若 (m-1) mod (k-1) 0 则需附加(k-1)- (m-1) mod (k-1) 个长度为0的虚段，以使每次归并都可以对应k个段2）按照哈夫曼树的构造原则（权值越小的结点离根结点越远）构造最佳归并树。 长度分别为2，3，6，9，12，17，18，24的8个初始归并段进行3路归并，求最佳归并树。 91 20 24 47 5 6 9 12 17 18 0 2 3I/O次数： (2+3)3 + (6+9+12+17+18)2 + 241 2 = 3261. 假设一次I/O的物理块可容纳150个记录，每次可对750个记录进行内部排序，那么对含有150000个记录的磁盘文件进行4-路平衡归并排序时，共需进行多少次I/O？2.已知某文件经过置换-选择排序之后，得到长度分别为47，9，31，18，4，12，23和7（单位均为物理块）的8个初始归并段。试为3-路平衡归并设计一个读写外存次数最少的归并方案，并求出读写外存的次数。3.在外排序中怎样减少排序的总时间？
