《外部排序》PPT课件.ppt

1、外存信息的存取2、外部排序的方法3、多路平衡归并的实现4、置换-选择排序5、最佳归并树,第11章外部排序,1、外存信息的存取,1、外部排序：内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、CD-ROM上。特点为内存运行时间短，内、外存进行交换需要时间长。减少I/O时间成为主要矛盾。,记录（Record）：数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记录。原因起源于是在历史上研究管理应用和计算机科学的两部分人员的习惯。域（场）：记录中的每个数据项，称之为域（Field）。文件：记录的集合。关键字：唯一标识记录的域，称之为关键字。有序文件：文件根据关键字的大小。排成递增或递减的序列。,2、基本术语：,3、常用外存：,磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度幔。,1、外存信息的存取,3、常用外存：,磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢。带信息的表示：,一种磁化方向、代表1,另一种磁化方向，代表0,01001001,10101111,1、外存信息的存取,3、常用外存：,磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢（尤其是查找末端记录时）。,.,.,磁带机走向,读出头,写入头,原始盘,接收盘,带文件的组织：,记录1,记录3,记录2,IRG（InterRecordGap）记录间隙,1、外存信息的存取,3、常用外存：,带文件的组织：,记录1,记录3,记录2,IRG（InterRecordGap）记录间隙,v,t,可靠读写区,IRG：.5.75inch，带来的问题是什么？带的利用率下降，如：密度800byteperinch的带。设每个记录有80byte，共1000个记录。如果，IRG.6inch;带的利用率？1000(80/800)100inch(file)10000.6600inch(totalIRG)利用率1/7=14%必须改进带的利用率!,带文件的读写时间：Ti/o=ta+ntwta延迟时间：读写头到达相应的记录起始位置的时间。tw读/写一个字符的时间；n字符数。,读写头,1、外存信息的存取,3、常用外存：,带文件的组织的改进：,块1,块3,块2,IBG（InterBlockGap）块间间隙,IBG：.5.75inch，带来的好处是什么？每一块是一个物理记录，包含若干个逻辑记录。B.F（块因子）一个物理记录包含逻辑记录的个数带的利用率上升，如上例：设B.F=1001000/1000.66inch(totalIBG)100080/800100inch(file)利用率100/106=94.3%,1、外存信息的存取,3、常用外存：,磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。速度快、容量大、直接存取设备。种类：固定头磁盘、活动头磁盘固定头磁盘：每个磁道都有一个磁头（速度快）活动头磁盘：每个盘面共用一个磁头，增加了找道的时间，应用广泛。,柱面：各盘面的直径相同的磁道的总和。,物理位置：盘组号、若干个磁盘构成一组，系统可能有许多组。柱面号、磁道号、块（扇区号）,盘文件的读写时间：Ti/o=tseck+tla+ntwmtseck：找道时间tla：等待时间twm：传输时间/字符，n字符数。,2、外部排序的方法,1、步骤：,生成合并段（run）：读入文件的部分记录到内存在内存中进行内部排序将排好序的这些记录写入外存，形成合并段再读入该文件的下面的记录，往复进行，直至文件中的记录全部形成合并段为止。,外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文件。,平衡合并分类法：被合并的初始合并段均匀分布在K条磁带上，即分布在T1、T2、Tk上。对这K条带进行合并，将生成的中间归并段分布在TK+1、TK+2、T2K上。然后，循环往复，直至最后形成一个单一的合并段为止。e.g:平衡2路归并，K2。2K=4,需4条磁带。六个初始合并段均匀分布在T1、T2上。每个合并段有1000个记录。T3、T4初始为空。合并过程如下：初始分布：,R（11000）,R（20012000）,R（4001.5001）,R（10012000）,R（30014000）,R（5001.6000）,T1,T2,T4：空,T3：空,7、15、198、11、1316、23、315、12,2、外部排序的方法,初始分布：,R（11000）,R（20013000）,R（4001.5001）,R（10012000）,R（30014000）,R（5001.6000）,T1,T2,T4：空,T3：空,第一趟归并：,T1：空,T2：空,T3：,T4：,R（12000）,R（40016000）,R（20014000）,2、外部排序的方法,第二趟归并：,T3：空,T4：空,T1：,T2：,R（14000）,R（40016000）,第三趟归并：,T3：,T4：空,T1：空,T2：空,R（16000）,2、外部排序的方法,e.g:平衡3路归并，K3。2K=6,需6条磁带。六个初始合并段均匀分布在T1、T2、T3上。每个合并段有1000个记录。T4、T5、T6初始为空。合并过程如下：初始分布：,R（11000）,R（30014000）,R（10012000）,R（40015000）,T1：,T2：,T4：空,T3：,R（20013000）,R（50016000）,T5：空,T6：空,第一趟归并：,R（13000）,R（30016000）,T4：,T5：,T1：空,T2：空,T3：空,T6：空,2、外部排序的方法,e.g:平衡3路归并，K3。2K=6,需6条磁带。六个初始合并段均匀分布在T1、T2、T3上。每个合并段有1000个记录。T4、T5、T6初始为空。合并过程如下：,第一趟归并：,R（13000）,R（30016000）,T4：,T5：,T1：空,T2：空,T3：空,T6：空,第二趟归并：,R（16000）,T1：,T2：空,T3：空,T4：空,T5：空,T6：空,2、外部排序的方法,时间分析:归并趟数:logkmwherek是路数；m是初始合并段数。在上例中：log26=3而log36=2此外，还有一次生成所有合并段的时间。对文件中的所有的记录全部读写一次。每一趟归并时，对文件中的所有的记录都要全部读写一次。K大，趟数减少，读写记录的总数将减少。但K大，需要的内存将越多。减少初始合并段数m,将使趟数减少，读写记录的总数将减少。这就要求在内存一定且进行内部排序时，生成尽可能长的归并段，从而减少归并段的总数。,输入、输出缓冲区的安排:设进行平衡2路归并，K2。2K=4,需4条磁带。六个初始合并段均匀分布在T1、T2。每个合并段有1000个记录。T3、T4初始为空。,R（11000）,R（20012000）,R（4001.5001）,R（10012000）,R（30014000）,R（5001.6000）,T1,T2,T4：空,T3：空,2、外部排序的方法,输入、输出缓冲区的安排:设进行平衡2路归并，K2。2K=4,需4条磁带。六个初始合并段均匀分布在T1、T2。每个合并段有1000个记录。T3、T4初始为空。设每个物理块包含250个记录，则每个初始合并段包含4个物理块。K路合并，K个输入输入缓冲区和一个输出缓冲区。,R（11000）,R（20012000）,R（4001.5001）,R（10012000）,R（30014000）,R（5001.6000）,T1,T2,T4：空,T3：空,250个记录,T1,T2,250个记录,250个记录,250个记录,250个记录,250个记录,250个记录,250个记录,IBG（InterBlockGap）,初始合并段(R（11000）),250个记录,T3,250个记录大,250个记录大,K(2)个输入缓冲区,250个记录大,1个输出缓冲区,读入内存,读入内存,写入磁带,注意：对于缓冲区的安排，有一定的原则。,2、外部排序的方法,10100,T1,T2,150200,220300,350400,112,1314,1516,1718,初始合并段(R（18）),T3,K(2)个输入缓冲区,110,1个输出缓冲区,读入内存,读入内存,写入磁带,缓冲区的安排举例：,10100,112,110,另一个初始合并段(R（18）),i,j,2、外部排序的方法,10100,T1,T2,150200,220300,350400,112,1314,1516,1718,初始合并段(R（18）),T3,K(2)个输入缓冲区,12,1个输出缓冲区,缓冲区的安排举例：,10100,112,110,另一个初始合并段(R（18）),i,j,2、外部排序的方法,10100,T1,T2,150200,220300,350400,112,1314,1516,1718,初始合并段(R（18）),T3,K(2)个输入缓冲区,12,1个输出缓冲区,读入内存,读入内存,缓冲区的安排举例：,10100,1314,110,另一个初始合并段(R（18）),i,j,2、外部排序的方法,10100,T1,T2,150200,220300,350400,112,1314,1516,1718,初始合并段(R（18）),T3,K(2)个输入缓冲区,1个输出缓冲区,读入内存,缓冲区的安排举例：,10100,1314,110,另一个初始合并段(R（18）),i,j,2、外部排序的方法,10100,T1,T2,150200,220300,350400,112,1314,1516,1718,初始合并段(R（18）),T3,K(2)个输入缓冲区,1个输出缓冲区,读入内存,写入磁带,缓冲区的安排举例：,10100,1314,110,另一个初始合并段(R（18）),i,j,1314,1314,3、多路平衡归并的实现,时间分析:logkm趟K大，趟数减少，读写记录的总数将减少。但K大，会带来什么问题呢？,1、带、盘的平衡多路归并的性质：,e.g:K=2时,m个归并串。总共n个记录。,合并段1,合并段2,合并段m-1,合并段m,中间合并段,中间合并段,中间合并段,中间合并段,有序文件,层数：log2m+1归并趟数：log2m,3、多路平衡归并的实现,1、带、盘的平衡多路归并的性质：,e.g:K2时,趟数将会减少。m个归并串。总共n个记录。,合并段1,合并段k,合并段m-1,合并段m,中间合并段,中间合并段,有序文件,层数：logkm+1归并趟数：logkm,设从k个元素中挑选一个最小的元素需(k-1)次比较。每次比较耗费的时间代价为:tmg，那么在进行k路平衡归并时，总的比较时间耗费不会超过：logkm(k-1)(n-1)tmg=log2m/log2k(k-1)(n-1)tmgklog2m/log2k(k-1),大,大,3、多路平衡归并的实现,1、带、盘的平衡多路归并的性质：,设从k个元素中挑选一个最小的元素需(k-1)次比较。每次比较耗费的时间代价为:tmg，那么在进行k平衡归并时，总的时间耗费不会超过：logkm(k-1)(n-1)tmg=log2m/log2k(k-1)(n-1)tmgklog2m/log2k(k-1),大,大,改进：采用胜者树或者败者树，从K个元素中挑选一个最小的元素仅需log2k次比较，这时总的时间耗费将下降：logkmlog2k(n-1)tmglog2m(n-1)tmg,2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名。,9,5,3、多路平衡归并的实现,2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名。,7,29,5,9,5,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出缓冲区,5,5,9,5,7,29,9,7,6,5,4,3,2,1,5,注意：挑出冠军需要进行k-1次比较，此处需要比较3次。,9,7,3、多路平衡归并的实现,2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名。,7,29,16,9,7,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出缓冲区,7,7,9,16,7,29,9,7,6,5,4,3,2,1,57,注意：挑出亚军需要进行log2k次比较，此处需要比较2次。,9,12,3、多路平衡归并的实现,2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名。,12,29,16,9,9,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出缓冲区,9,12,9,16,12,29,9,7,6,5,4,3,2,1,579,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,3、多路平衡归并的实现,2、胜者树及其使用胜者进入下一轮，直至决出本次比赛的冠军。决出冠军之后，充分利用上一次比赛的结果，使得更快地挑出亚军、第三名。决出第一名需比较：k-1次决出第二名需比较：log2k次决出第三名需比较：log2k次,结果：采用胜者树后，从K个元素中挑选一个最小的元素仅需log2k次比较，这时总的时间耗费下降为：logkmlog2k(n-1)tmglog2m(n-1)tmg有意思的是该结果和k无关，这是通过多用空间换来的。,改进：采用胜者树，K个元素中最小的元素输出之后，从根结点到它的相应的叶子结点路径上的结点都需要进行修改，为了加快程序运行的速度产生了败者树。,29,7,3、多路平衡归并的实现,3、败者树及其使用,7,29,5,9,9,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出缓冲区,9,7,29,5,7,29,9,7,6,5,4,3,2,1,5,注意：挑出冠军需要进行k-1次比较，此处需要比较3次。,5,0,0,5,29,16,3、多路平衡归并的实现,7,29,16,9,9,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出缓冲区,57,注意：挑出亚军需要进行log2k次比较，此处需要比较2次。,3、败者树及其使用,1,7,0,9,16,29,16,7,29,9,7,6,5,4,3,2,1,0,5,29,16,3、多路平衡归并的实现,3、败者树及其使用,12,29,16,9,12,516495278,712258491,2938576671,922474859,7,6,5,4,3,2,1,输入缓冲区,输出缓冲区,579,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,9,0,16,16,29,16,12,29,9,7,6,5,4,3,2,1,0,9,3、多路平衡归并的实现,3、败者树的程序实现typedefintLoserTreek;typedefstructKeyTypekey;Exnode,Externalk+1;,VoidK_Merge(LoserTree/将含最大关键字MAXKEY的记录写至输出归并段/K_Merge,3、多路平衡归并的实现,3、败者树的程序实现,VoidAdjust(LoserTree/Adjust,VoidCreateLoserTree(LoserTree/CreateLoserTree,k,k,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,k,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,k,0,存于b0bk-1之中注意：bk=-,存于ls0lsk-1之中,3,3,k,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,k,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,k,0,存于b0bk-1之中注意：bk=-,存于ls0lsk-1之中,3,2,k,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,3,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,k,0,存于b0bk-1之中注意：bk=-,存于ls0lsk-1之中,3,2,1,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,3,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,k,0,存于b0bk-1之中注意：bk=-,存于ls0lsk-1之中,3,2,1,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,3,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,0,0,存于b0bk-1之中注意：bk=-,存于ls0lsk-1之中,3,5,2,1,3、多路平衡归并的实现,败者树程序实现：,7,29,5,9,3,516495278,712258491,2938576671,922474859,3,2,1,0,2,1,输入缓冲区,输出缓冲区,注意：在输出缓冲区被写满之后，全部内容输出至带或盘。,1,1,0,0,存于b0bk-1之中注意：bk=-,存于ls0lsk-1之中,3,5,2,1,3、多路平衡归并的实现,败者树程序实现：记录输出结束后，可能出现如下情况。此时bls0=+，程序结束。,3,3,2,1,0,2,1,输入缓冲区,输出缓冲区,注意：每一个归并段的最后加一个字段为+，即书上所说的MAXKEY，作为结束条件。,1,1,0,0,存于b0bk-1之中注意：bk=-,存于ls0lsk-1之中,3,+,+,+,+,+,+,+,+,4、置换-选择排序,1、作用：产生尽可能长的初始归并段。在内存长度一定时，按照通常的排序方法，产生的初始归并段的长度只能和内存长度相同，但采用本方法之后可以产生却可以生成两倍内存长度的初始归并段（平均情况下）。,2、实例：F1：31、21、19、12、26、41、11、37、15、23、29在带1上F2：输出磁带2假定使用的内存只有3个记录长，利用置换-选择分类法产生初始合并段。,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)31,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)315(11)、41、(12)41,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)315(11)、41、(12)416(11)、(37)、(12)#,第一个初始合并段,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)315(11)、41、(12)416(11)、(37)、(12)#711、37、1211,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)315(11)、41、(12)416(11)、(37)、(12)#711、37、1211815、37、1212,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)315(11)、41、(12)416(11)、(37)、(12)#711、37、1211815、37、1212915、37、2315,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)315(11)、41、(12)416(11)、(37)、(12)#711、37、1211815、37、1212915、37、23151029、37、2323,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)315(11)、41、(12)416(11)、(37)、(12)#711、37、1211815、37、1212915、37、23151029、37、23231129、3729,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)315(11)、41、(12)416(11)、(37)、(12)#711、37、1211815、37、1212915、37、23151029、37、23231129、3729123737,4、置换-选择排序,实例的实现过程：F1：31、21、19、12、26、41、11、37、15、23、29在带1上,步数内存缓冲区内容（由F1输入）输出结果（至带F2）131、21、1919231、21、(12)21331、26、(12)26431、41、(12)315(11)、41、(12)416(11)、(37)、(12)#711、37、1211815、37、1212915、37、23151029、37、23231129、372912373713#,第二个初始合并段,第一个初始合并段,4、置换-选择排序,3、长度分析：设内存可以存放m个记录，则首先从文件读入m记录到内存。这m个记录肯定可以归入本初始合并段内。这样，必须从文件中读入m个记录。这m个记录中平均有一半可以归入本合并段，一半归入下一合并段。因此，合并段的平均长度为：m+m/2+m/4+=2m所以，在平均情况下，合并段的平均长度为2m。书上介绍：该结论由：EFMoore在1961年从置换选择排序同扫雪机的类比中得到的。不过我认为这种证明完全是胡扯。,4、程序实现：可以用败者树的办法加以实现。,3,2,1,4,4、置换-选择排序,5、败者树实现置换-选择排序,5,2,29,0,1,0,51、49、39、46、38、29、14、61、15,461,391,491,511,291,381,5,4,3,3,2,0,4,4、置换-选择排序,5、败者树实现置换-选择排序,5,2,2938,0,1,1,51、49、39、46、38、29、14、61、15,461,391,491,511,142,381,5,4