《外部排序》PPT课件

《《外部排序》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1、外存信息的存取2、外部排序的方法3、多路平衡归并的实现4、置换-选择排序5、最佳归并树第11章外部排序1、外存信息的存取1、外部排序：内部排序：信息一次可全部调入内存，信息在内存中的处理时间是主要的时间耗费。外部排序：信息量巨大，无法一次调入内存。只能驻留在带、盘、CD-ROM上。特点为内存运行时间短，内、外存进行交换需要时间长。减少I/O时间成为主要矛盾。记录（Record）：数据项的集合存于内存，称之为结点。如果存之于外存，则叫做记录。原因起源于是在历史上研究管理应用和计算机科学的两部分人员的习惯。域（场）：记录中的每个数据项，称之为域（Field）。文件：记录的集合。关键

2、字：唯一标识记录的域，称之为关键字。有序文件：文件根据关键字的大小。排成递增或递减的序列。2、基本术语：3、常用外存：磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度幔。1、外存信息的存取3、常用外存：磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取设备。查找费时、速度慢。带信息的表示：一种磁化方向、代表1另一种磁化方向，代表001001001101011111、外存信息的存取3、常用外存：磁带：由磁带介质、读、写磁头、驱动器、接收盘和原始盘组成。便宜、可反复使用、是一种顺序存取

3、设备。查找费时、速度慢（尤其是查找末端记录时）。..磁带机走向读出头写入头原始盘接收盘带文件的组织：记录1记录3记录2IRG（InterRecordGap）记录间隙1、外存信息的存取3、常用外存：带文件的组织：记录1记录3记录2IRG（InterRecordGap）记录间隙vt可靠读写区IRG：.5~.75inch，带来的问题是什么？带的利用率下降，如：密度800byteperinch的带。设每个记录有80byte，共1000个记录。如果，IRG＝.6inch;带的利用率？1000×(80/800)＝100inch(file)1000×0.6＝600inch(totalIRG)利用

4、率＝1/7=14%必须改进带的利用率!带文件的读写时间：Ti/o=ta+n×twta延迟时间：读写头到达相应的记录起始位置的时间。tw读/写一个字符的时间；n字符数。读写头1、外存信息的存取3、常用外存：带文件的组织的改进：块1块3块2IBG（InterBlockGap）块间间隙IBG：.5~.75inch，带来的好处是什么？每一块是一个物理记录，包含若干个逻辑记录。B.F（块因子）＝一个物理记录包含逻辑记录的个数带的利用率上升，如上例：设B.F=1001000/100×0.6＝6inch(totalIBG)1000×80/800＝100inch(file)利用率＝100/106=

5、94.3%1、外存信息的存取3、常用外存：磁盘：由存取装置、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。速度快、容量大、直接存取设备。种类：固定头磁盘、活动头磁盘固定头磁盘：每个磁道都有一个磁头（速度快）活动头磁盘：每个盘面共用一个磁头，增加了找道的时间，应用广泛。柱面：各盘面的直径相同的磁道的总和。物理位置：盘组号、若干个磁盘构成一组，系统可能有许多组。柱面号、磁道号、块（扇区号）盘文件的读写时间：Ti/o=tseck+tla+n×twmtseck：找道时间tla：等待时间twm：传输时间/字符，n字符数。2、外部排序的方法1、步骤：生成合并段（run）：读入文件的部分

6、记录到内存－>在内存中进行内部排序－>将排好序的这些记录写入外存，形成合并段－>再读入该文件的下面的记录，往复进行，直至文件中的记录全部形成合并段为止。外部合并：将上一阶段生成的合并段调入内存，进行合并，直至最后形成一个有序的文件。平衡合并分类法：被合并的初始合并段均匀分布在K条磁带上，即分布在T1、T2、……Tk上。对这K条带进行合并，将生成的中间归并段分布在TK+1、TK+2、……T2K上。然后，循环往复，直至最后形成一个单一的合并段为止。e.g:平衡2路归并，K＝2。2K=4,需4条磁带。六个初始合并段均匀分布在T1、T2上。每个合并段有1000个记录。T3、T4初始为空。合

7、并过程如下：初始分布：R（1……1000）R（2001…2000）R（4001...5001）R（1001……2000）R（3001…4000）R（5001...6000）T1T2T4：空T3：空7、15、198、11、1316、23、315、122、外部排序的方法初始分布：R（1……1000）R（2001…3000）R（4001...5001）R（1001……2000）R（3001…4000）R（5001...6000）T1T2T4：空T3：空第一趟归并：T1：空T