文档介绍：外存的存取特性
计算机的存储器分为内存储器和外存储器，分别简称为内存和外存。
1．磁盘信息的存取
磁盘是一种随机存取的设备，可以直接存取设备上的数据。磁盘由盘片、磁头、盘片主轴、磁头控制器等组成，其中，盘片是用于存储数据的。盘片被划分为多个同心圆，称为磁道，磁道由外向内从0开始顺序编号，所有的数据信息被记录在磁道上。磁盘一般由多个盘片构成，每一个盘片包含两个面，其中，最上面和最下面的外侧的一面不存储信息。例如，一个磁盘由6个盘片组成，则有10个面可保存信息。
第1页/共21页
外存的存取特性
所有的盘面的同一磁道构成一个圆柱，称为柱面，位于同一柱面上的磁道由上往下从0开始编号。每个磁道还可以进行划分为若干个部分，被称为扇区，每个扇区的大小是512字节。扇区所在的磁道地址称为扇区号。
例如，某磁盘有10个有效记录面，记录面上有效记录区域的内径为20cm，外径是30cm，道密度为10道/mm，每个磁道有16个扇区，每个扇区记录512字节，则该磁盘的容量是：记录面数×磁道数×磁道扇区数×扇区的字节数=10×(30-20)/2×10×10×16×512=40960000字节≈39M字节。
第2页/共21页
外存的存取特性
要存取某一数据信息，首先需要找到数据所在的柱面，移动磁头到所在的柱面即磁道，然后移动磁头到具体的数据存放位置，因此，要存取磁盘上的数据信息所需要的时间由3个部分构成：寻道时间、等待时间和传输时间。其中，寻道时间tseek就是读写磁头寻找数据所在磁道并定位的时间，等待时间tw就是将磁头移动到数据信息所在的起始位置，传输时间trw就是读或写数据所需要的时间。读写数据的所用时间可表示为T=tseek+tw+trw。
第3页/共21页
外存的存取特性
磁带作为主要的存储介质，一般磁带长3600英尺、。磁带可以分为7道带和9道带，7道带的磁带，每一排可以存储8位即一个字节，其中7位是数据位，1位奇偶校验位。通常情况下，磁带的存储密度是每英寸800位或1600位，磁带的移动磁头速度是每秒200英寸。
磁带是一种启停设备，当磁头正在读写磁带上的记录，如果要停止读写，必须经过一个减速的过程，然后才能停止。同样，从磁头静止，到开始读写数据时，磁头是经过一个加速旋转的过程，然后才能匀速的旋转达到稳定状态。因此，在磁带的每个相邻的记录之间，需要一个空白区域，这个空白区域就称为间隙。-。。
第4页/共21页
磁盘排序
归并排序的基本方法
在外排序中，归并排序的基本思想方法可分为两步：
（1）第一步：将待排序的n个记录文件按照内存缓冲区的大小，分割为长度为m的若干个子文件，将这些子文件分批地不断调入内存，进行归并排序，生成有序的若干个子文件，并放在外存。将这些有序的子文件称为归并段。
（2）第二步：对已经有序的归并段继续不断在内存和外存互换，从而进行归并排序，直到待排序文件构成一个有序的序列。
第5页/共21页
磁盘排序
按照以上方法归并R3和R4，得到有序的600条记录。然后分别对两个新生成的归并段继续归并，直到待排序文件中所有记录都已经有序，则该文件的1200条记录均为有序序列。。
第6页/共21页
磁盘排序
因此，总的归并时间可计算如下：（1）读入1200条记录并进行归并，则需要的时间为12tio+4tis；（2）将两个归并段即R1和R2归并为R1，R3和R4归并为R2，则需要花费的时间为12tio+1200tm；（3）然后将R1和R2归并为R1的需要的时间为12tio+1200tm。总共需要的时间为36tio+4tis+2400tm。
第7页/共21页
磁盘排序
多路归并排序
多路归并可以有效的减少时间的开销。对于上面提到的2路归并，在初始时，如果归并段是m个，则将构成的归并树的层数是+1，需要进行趟归并才能完成排序。而对于k路归并，就是将k个归并段进行归并，则将构成+1层的归并树，也就是需要进行趟的归并。例如，如果k=4，。
第8页/共21页
磁盘排序
选择树是一种完全二叉树，在该完全二叉树中，叶子结点存放各个归并段的当前待排序的元素，非叶子结点则表示对应孩子结点的最小的一个，从叶子结点开始，依次将当前互为兄弟