第 10 章外部排序.ppt

(内存)外部存储器(外存)顺序存取设备(磁带存储器)直接存取设备(磁盘存储器)内存的存储容量小,但工作速度高;外存的存储容量大,但速度较低。:存储容量大,使用方便,价格便宜。:磁带存储器主要由磁带、读/写磁头和磁带驱动器组成,如下图所示。目前常用的典型磁带长2400英尺,,。磁带表面上涂有磁性材料,可分为七道或九道磁带。七道磁带的每一横排中有六个二进制数据位和一个奇偶校验位。九道磁带的每一横排中有八个二进制数据位和一个奇偶校验位。这样的一排二进制数据位组成一个字节。。所谓顺序存取,就是将记录在存储器上一个接一个地依次存放,为得到第i个记录,必须先读第i-1个记录。由于磁带机不是连续运转的设备,而是一种启停设备,所以在启停时间内,不能对磁带进行正常读写,因此磁带上的信息通常分为若干记录块,块与块之间留有一定的间隙,该间隙一般为1/4~3/4英寸。由上可知,用磁带存储信息时需要在每段信息之间留有空隙,且此空隙占用了大量的存储空间。为了减少存储空间的浪费,通常采用把若干个记录组合成页块进行存储的办法,将记录间的间隙变成页块间的间隙。:既能进行顺序存取,又能进行直接存取(随即存取),并且存取速度快。。磁盘组由若干个盘片组成,每个盘片有上下两个面,盘面上涂有光滑的磁性物质。盘面上能够存储信息的盘面称为记录面。在记录盘面上有许多称为磁道的圆圈,信息就记载在磁道上。磁盘驱动器由主轴和读/写磁头组成,每个盘面都配有一个读/写磁头。看狼吾帮示墒岗罚孪挑贝逮脱队炸巳允旨扣垮深肺警栖凝夸涯脖城使盼宰第10章外部排序第10章外部排序磁盘可分为固定臂盘和活动臂盘两种。固定臂盘的每个盘面的每一磁道上都有独立的磁头,它是固定不动的,专门负责读写某一磁道上的信息。如图:,一般采用把记录组合成页块的方式来进行内外存数据的交换。一个页块(简称块)是磁盘上的一个物理记录,通常可以容纳多个逻辑记录,内存中设置的缓冲区应该与页块的大小相等。每次访问记录时,需要把一个页块读入一个缓冲区或者把一个缓冲区的数据写到一个页块。。这种方法由两个阶段组成:第一阶段是把文件逐段输入到内存,用有效的内排序方法对文件的各个段进行排序,经排序的文件段称为顺串(或归并段),当它们生成后立即写到外存上,这样在外存上就形成了许多初始顺串;第二阶段是对这些顺串用某种归并方法(如2路归并法)进行多边归并,使顺串的长度逐渐由小至大,直至变成一个顺串,即整个文件有序为止。:假设磁盘上存有一文件,共有3600个记录(A1,A2,…,A3600),页块长为200个记录,供排序使用的缓冲区可提供容纳600个记录的空间,现要对该文件进行排序,排序过程可按如下步骤进行:第一步:每次将三个页块(600个记录)由外存读到内存,进行内排序,整个文件共得到6个初始顺串R1~R6(每一个顺串占三个页块),然后把它们写回到磁盘上去。。第二步:将供内排序使用的内存缓冲区分为三块相等的部分(即每块可容纳200个记录),其中两块作为输入缓冲区,一块作为输出缓冲区,然后对各顺串进行两路归并。。,如果初始顺串有m个,[log2m]+1层,要对数据进行[log2m]遍扫描。采用多路归并可以减少扫描遍数,如图所示。1234 56789101**********