外部排序数据结构.ppt
外部排序,本章内容,外存信息的存取外部排序的方法多路平衡归并,外存信息存取,外存储器类型：1、顺序存取的设备（磁带）2、随机存取的设备（磁盘）,磁带的信息存取,磁带工作原理：将磁带盘放在磁带机上，驱动器控制磁带盘转动，带动磁带向前移动，通过读/写头就可以向读出或写入信息。磁带信息存贮可记下各种文字信息和二进制信息，按字符组存放，而不是按字符存放。读写的启动停止：磁带不是连续运转的设备，由于读/写需要稳定时进行，因此当启动/停止时，需要一个加速/减速的过程，这个过程磁带不写入任何内容，因而相邻的两个字符组之间要留一个空白，叫做间隙,磁带读写一块信息所需的时间,所需时间由两部分组成：Ti/o=ta+ntwta为延迟时间，即读写头到传输信息所在的物理块的起始位置所需的时间tw为传输一个一个字符所需的时间特点：查找速度慢，检索和修改信息不方便，主要用于处理变化小，只进行顺序存取的大量数据,磁盘信息的存取,磁盘信息的存取磁盘是一种直接存取的存储设备磁盘读写块所需的时间组成：Ti/o=tseek+ta+n*twm tseek：读写头定位的时间 ta：等待信息快的初始位置转到读写头下的时间 twm：传输时间,外部排序的应用对象保存在外存储器上的信息量很大的数据记录文件。外排序与内排序的差别内部排序充分利用内存可以随机存取的特点，如希尔排序中，相隔di的记录关键字可作比较；堆排序中，完全二叉树中父Ri与子R2i，R2i+1可比快速排序中，需正向和逆向访问记录序列外存信息的定位和存取受其物理特性的限制外部排序的实现手段在排序过程中，进行多次内外存之间的数据交换,外部排序的特点,外部排序的方法,由两个独立的阶段组成将外存含n个记录的文件分成若干长度为l的子文件或段，依次读入内存并用内部排序方法排序，将排序后的有序子文件重新写入外存，称为归并段或顺串对这些归并段进行逐趟归并，（有序子文件）由小变大，直到获得整个有序文件,外排序基本方法：归并排序,步骤生成若干初始归并串/顺串(文件预处理)把含有n个记录的文件，按内存缓冲区大小分成若干长度为L的子文件（段）；分别调入内存用有效的内排序方法排序后送回外存；多路合并对初始归并串逐趟合并，直至最后在外存上得到整个有序文件为止,例某文件共10000个记录，设每个物理块可以容纳200个记录，内存缓冲区可以容纳5个物理块 1)经过10次内排序后得到10个初始归并段R1R10 2)采用两路归并，需四趟可以得到排好序的文件 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 2000 2000 2000 2000 2000 4000 4000 8000 10000,外排序基本方法：归并排序,外存上的信息的读/写以“物理块”为单位，假设每个物理块可容纳200个记录，则每一趟归并所需进行50次“读”和50次“写”，4趟归并并加上内部排序所需进行的读写使得外排序总共需进行500读/写,外排序基本方法：归并排序,外部排序所需的总的时间=内部排序所需的时间（m*tis）+外存信息读写的时间（d*tio）+内部归并所需的时间（s*utmg）tis:：得到一个厨师归并段进行内部排序所需时间tio：进行一次外存读/写所需时间utmg：对u个记录进行内部归并所需的时间m：经过内部排序后得到初始归并段的个数s：为归并的趟数d：为总的读/写次数因此：上例进行外派的总的时间为：10tis+500*tio+4*10000tmg，由于tio比tmg大的多，因此提高外排序的效率要降低读/写次数d,提高外排序效率的途径,因为d和归并的趟数s成正比，而s又与m成正比，因此有：1、扩大初始归并段长度，从而减少初始归并段个数m 2、进行多路(k路)归并减少合并趟数s，以减少I/O次数s=logkm,多路平衡归并,通过简单比较进行K路归并存在的问题 设记录总数为n，初始归并段的个数为m，从k个记录中选择一个关键字最小的记录时的比较次数为c则s趟内部归并总的比较次数为：C=sc(n-1)=logkm c(n-1)=log2m/log2k c(n-1)k，s，可减少I/O次数；k，c=(k-1)，归并效率解决矛盾的方法 利用“败者树”选关键字最小的记录 此时c=log2k则 C=log2m(n-1)，与k无关,矛盾,1 2 k,胜者树(树形选择排序),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路合并败者树 重构后的败者树败者树的特点：记录败者，胜者参加下一轮比赛 败者树的优点：重构时修改结点较少,0,1 2 3 4 5 6,4,ls0,5,ls0,1 2 3 4 5 6,0,4 5 2 0 1 3 6 90 0 10 9 20 6 8 12 1 2 3 4 5 6调整败者树的方法:将新补充的结点与其双亲结点比较,败者留在该双亲结点,胜者继续向上直至树根的双亲,以在b4补充15为例,15,4与3比较,4与2比较,4,2与5比较,2,5,调整败者树的方法,7 7 7 7 7 7 7 90 0 10 9 20 6 8 12 1 2 3 4 5 6k-路归并对内存的要求 至少要有k个输入缓冲区和一个输出缓冲区,建败者树的过程,7,-1,初始化败者树,调整b6,6,调整b5,5,调整b4,4,调整b3,3,4,调整b2,2,调整b1,1,2,4,调整b0,0,5,4,建败者树的过程,数据结构(依据：败者树为完全二叉树)主：b0.k b0.k-1k个叶结点，存放k个输入归并段中当前 参加归并的记录（缓冲区）bk虚拟记录，该关键字取可能的最小值minkey辅：ls0.k-1 不含叶结点的败者树 存放最后胜出的编号（ls0）以及所记录的败者编号处理步骤建败者树ls0.k-1重复下列操作直至k路归并完毕将bls0写至输出归并段补充记录(某归并段变空时,补)，调整败者树,多路平衡归并算法,算法描述：建立败者树,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;,算法描述:K路合并,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);,
