单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第十一章外部排序,11.1,外存信息的存取,11.1.1,磁带信息的存取,11.1.2,磁盘信息的存取,11.2,外部排序的方法,1,11.1,外存信息的存取,11.1.1,磁带信息的存取,磁带,：一条薄薄涂上一层磁性材料的窄带（现在使用的磁带大,多数有,1/2,英寸宽，最长可达,3600,英尺，绕在一个卷盘上）。它是,一种顺序存取的存储设备。,磁带的,工作原理,：使用时，将磁带放在磁带机上，驱动器控制,磁带盘转动，带动磁带向前移动。通过读,/,写头就可以读出磁带上的,信息或者把信息写入磁带中。,7,道带,：在,1/2,英寸宽的带面上记录,7,位二进制信息的磁带。,9,道带,：在,1/2,英寸宽的带面上记录,9,位二进制信息的磁带。每,一横排可表示一个字符（,8,位表示一个字符，剩下的一位作奇偶校,验位）。,信息密度,：每英寸的二进制字符数。通常为每英寸,800,位或,1600,位或,6250,位。,移动速度,：每秒,200,英寸。,2,间隙,IRG,（,Inter Record Gap,）：磁带上相邻两组字符组（记录）,之间的空白区。根据启停时间的需要，这个间隙通常为,1/43/4,英寸。,例如，若每个字符组的长度是,80,个字符，,IRG,为,3/4,英寸，则对密,度为每英寸,1600,个字符的磁带，其利用率仅为,1/16,，有,15/16,的带用于,IRG,。如图,11.1(a),所示。,块间间隙,IBG,（,Inter Block Gap,）：将若干个字符组合并成块，每,个字符组间没有,IRG,，而变成块间的间隙。,例如，图,11.1(b),表示将,20,个长度为,80,字符的字符组存放在磁带上的,一个物理块中的情况。,IRG IRG IRG,记 录,(a),字符组长,80,字符的磁带,IBG,IBG,IBG,20,个记录,20,个记录,20,个记录,(b),成块存放的磁带,图,11.1,磁带上信息存放示意图,3,磁带上读写一块信息所需的时间为：,T,I/O,=,t,a,+n*,t,w,其中：,t,a,为延迟时间，读,/,写头到达传输信息所在物理块起始位置所需,时间（显然，延迟时间和信息在磁带上的位置、当前读,/,写头所在位置,有关）；,t,w,为传输一个字符的时间。,成块的优点：,（,1,）可以减少,IRG,的数目，从而提高磁带的利用率，块的长度大于,IBG,的长度。,（,2,）可以减少,I/O,操作。因为一次,I/O,操作可把整个物理块都读到内,存缓冲区中，然后再从缓冲区中取出所需要的信息（一个字符组）。,每当要读一个字符组时，首先要查缓冲区中是否已有，若有，则不必执,行,I/O,操作，直接从缓冲区读取即可。,4,11.1.2,磁盘信息的存取,磁盘,：是一个扁平的圆盘，盘面上有许多称为磁道的圆圈，信息,就记载在磁道上。它是一种直接存取的存储设备（,DASD,）。,磁盘的,工作原理,：盘片装在一个主轴上，并绕主轴高速旋转，当,磁道在读,/,写头下通过时，便可进行信息的读,/,写。读,/,写信息的功能由,磁盘驱动器执行。,固定头盘,：固定头盘的每一磁道上都有独立的磁头，这些磁头固,定不动，专负责读,/,写某一磁道上的信息。,活动头盘,：活动头盘的磁头是可以移动的。一个盘面上只有一个,磁头，磁头装在一个动臂上，可以从该面上的一道移动到另一道。,5,11.1.2,磁盘信息的存取,在磁盘上表明一个具体信息必须用一个,三维地址,：柱面号（确定,读,/,写头的径向运动,),、盘面号、块号,(,确定信息在盘片圆圈上的位置）。,访问一块信息,：,（,1,）找柱面,移动臂使磁头移动到所需柱面上,(,称为定位或寻查,),；,（,2,）等待要访问的信息转动磁头之下；,（,3,）读,/,写所需信息。,磁盘上读写一块信息所需的,时间,为：,T,I/O,=,t,seek,+,t,la,+n*,t,wm,其中：,t,seek,为寻查时间（,seek time,）：即读,/,写头定位的时间；,t,la,为等待时间（,latency time,）：即等待信息块的初始位置旋到,读,/,写头下的时间；,t,wm,为传输时间（,transmission time,）。,6,7,8,