数据结构与算法-文件与外部排序

教学要求掌握文件的相关概念；文件的各种组织方法及特点；查询、更新操作及其算法；掌握外部排序的一般过程，熟练掌握适合外存特点的归并排序的相关技术。主要内容7.1文件及文件操作7.2文件组织7.3磁盘文件的归并排序7.4磁带文件的归并排序7.1文件及文件操作1、相关概念文件是用于表示驻留在外存储器中的数据，是同性质记录的有序集合。记录学号姓名性别年龄数学语文物理其它A003孙喆B008陈益C009史硕刚D010许艺洪E011张爽F012沈键关键字：主关键字and次关键字文件的逻辑结构和物理结构：逻辑结构：呈现给用户，描述记录间的逻辑关系物理结构：存储结构，记录在存储器中的组织，连续，链式等2、文件操作操作：

●INSERT，在文件中插入记录

●DELETE，从文件中删除记录

●MODIFY，修改满足条件的记录

●

RETRIEVE，检索满足条件的记录检索方式：实时or成批更新方式：实时or成批文件更新文件检索3、查询方式

Q1简单查询：查询单个关键字值等于给定值的记录

如：性别=男

Q2范围查询：查询单个关键字值满足指定范围的记录

如：数学>80

Q3函数查询：对于某个关键字的函数，查询满足指定函数

值的记录

如：物理>平均分

Q4布尔查询：对Q1Q2Q3进行组合的查询，查询满足布尔

表达式的记录如：(性别=男)and(年龄=18)

布尔运算：andornotMain(){FILE*fp;……}Sourcefile.c输入数据原始数据磁盘/带文件处理结果输出数据文件指针文件结构体——FILEtypedefstruct{int_fd;//文件号

int_cleft;//缓冲区中剩下的字符数

int_mode;//文件操作方式

char*_next;//文件当前读写位置

char*_buff;//文件缓冲区位置}FILE;Stdio.hFILE*变量名；文件信息用系统定义的名为FILE的结构体描述Intfclose(FILE*fp)FILE*fopen(char*name,char*mode)

fread(buffer,size,count,fp);

fwrite(buffer,size,count,fp);

标准输入：键

盘-------stdin

标准输出：显示器-------stdout标准出错输出：显示器-------stderr#include"stdio.h"

main(intargc,char*argv[]){FILE*in,*out;if(argc!=3){printf("Youforgottoenterafilename\n");exit(0);}if((in=fopen(argv[1],"r"))==NULL){printf("Cannotopeninfile!\n");exit(0);}if((out=fopen(argv[2],"w"))==NULL){printf("Cannotopenoutfile!\n");exit(0);}

while(!feof(in))fputc(fgetc(in),out);fclose(in);fclose(out);}？按用途

系统文件、库文件、用户文件

按保护级别

可执行文件、只读文件、读写文件按信息流向

输入文件、输出文件、输入输出文件按存放时限

临时文件、永久文件、档案文件按设备类型

磁盘文件、磁带文件、卡片文件、打印文件

按文件组织结构逻辑文件(流式文件、记录式文件)、物理文件（顺序文件、链接文件、索引文件）4、文件分类FAT：FileAllocationTableNTFS：NewTechnologyFilesSyatemWinFS：WindowsFutureStorage操作系统FAT12Fat16Fat32NTFSNTFS5.0WinFSDOS3.0以下是支

持

末

来

的

操

作

系

统Dos3.0是DOS4.0是Windows3.X是Windows95是Windows95OSR2是是Windows98是是Windows98SE是WindowsMe是是WindowsNT是是Windows2000是是是是WindowsXP是是是是Windows2003是是是是Unix

是

Linux

是是(软盘引导)

文件大小限制最大支持8M最大支持2G不能大于4G单文件最大64GB单文件最大2TBWindows不同版本操作系统

的文件格式7.2文件组织常用的文件组织方式：顺序方式索引方式散列方式链接方式另外还有……

ISAMVSAMUNIX问题：文件驻留外存，数据量大

每次读入一个物理快文件操作复杂为使操作方便，要研究设计有效的存储机制7.2.1顺序方式文件的各个记录按逻辑顺序存放在外存的连续区内记录的顺序往往是按主关键字的大小排列的适合于Q1型查询，且检索与更新是成批进行的适合磁带或磁盘1、基本术语【顺序文件（SequentialFile）】是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。【串联文件】物理记录之间的次序由指针相链接表示的顺序文件。【连续文件】次序相继的两个物理记录在存储介质上的存储位置是相邻的顺序文件。2、特点顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。特点是：①存取第i个记录，必须先搜索在它之前的i-1个记录。②插入记录时要批量移动记录，或加在文件末尾的溢出区。

③删除记录时要批量移动记录，或标记记录④若要更新文件中某个记录，则必须将整个文件进行复制。3、磁带上顺序文件的批处理主文件：待修改的原始文件。事务文件：所有的修改请求集中构成的一个文件。磁带文件的批处理过程：首先对事务文件进行排序，然后将主文件和事务文件归并成一个新的主文件。

其中，主文件、事务文件和新的主文件分别存放在一台磁带上。主文件按关键字自小至大（或自大至小）顺序有序，事务文件必须和主文件有相同的有序关系。事务文件举例：新调来35人调走28人涨工资343人事务总数406件文件修改程序事务文件职工老文件职工新文件

终端事务文件排序有序的事务文件主文件新主文件

在归并的过程中，顺序读出主文件与事务文件中的记录，比较它们的关键字并分别进行处理。对于关键字不匹配的主文件中的记录，则直接将其写入新主文件中。“更改”和“删除”记录时，要求其关键字相匹配。“删去”不用写入，而“更改”则要将更改后的新记录写入新主文。“插入”时不要求关键字相匹配，可直接将事务文件上要插入的记录写到新主文件的适当位置。算法实现：f—主文件；g—事务文件；h—新主文件。它们都按关键字递增排序。事务文件的每个记录中，增设一个代码以示修改要求，其中：“I”表示插入；“D”表示删去；“U”表示更改。voidMergeFile(FILE*f,FILE*g,FILE*h){

fread(*fr,sizeof(RcdType),1,f); fread(*gr,sizeof(RcdType),1,g);while(!feof(f)||!feof(g)){switch{ casefr.key<gr.key: //复制“旧”主文件中记录

fwrite(*fr,sizeof(RcdType),1,h); if(!feof(f)) fread(*fr,sizeof(RcdType),1,f); break; casegr.code==‘D’&&fr.key==gr.key: //删除”旧”主文件中记录,不复制

if(!feof(f)) fread(*fr,sizeof(RcdType),1,f); if(!feof(g)) fread(*gr,sizeof(RcdType),1,g); break; casegr.code==‘I’&&fr.key>gr.key: //插入,函数P把gr加工为h的结构

fwrite(P(gr),sizeof(RcdType),1,h); if(!feof(g)) fread(*gr,sizeof(RcdType),1,g); break; casegr.code==‘U’&&fr.key==gr.key: //更改”旧”主文件中记录

fwrite(Q(fr,gr),sizeof(RcdType),1,h); //函数Q将fr和gr归并成一个h结构的记录

if(!feof(f)) fread(*fr,sizeof(RcdType),1,f); if(!feof(g)) fread(*gr,sizeof(RcdType),1,g); break; defaultERROR(); //其他均为出错情况

}//switch}//while}//MergeFile分析批处理算法的时间：假设主文件包含n个记录，事务文件包含m个记录。一般情况下，事务文件较小，可以进行内部排序，则时间复杂度为O(m*logm)。内部归并的时间复杂度为O(n+m)，则总的内部处理时间为O(m*logm+n)。4、磁盘上顺序文件的批处理磁盘上顺序文件的批处理和磁带文件类似，只是当修改项中没有插入，且更新时不增加记录的长度时，可以不建立新的主文件，而直接修改原来的主文件即可。显然，磁盘文件的批处理可以在一个磁盘上进行。

假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区大小为s（个记录），则整个批处理过程中读/写外存的次数为：n：主文件包含的记录数，m：事务文件包含记录数7.2.2索引方式【定义】索引指的是记录的关键字值与记录驻留在外存的地址组成数对的集合。每个数对称为一个索引项。索引文件在存储器上分两区：索引区和数据区查找记录：分两步进行删除记录：只删除索引插入记录：先存数据，然后登记索引并重新排序建立文件：按数据存入的先后顺序建立索引，最后索引排序示例：序号姓名记录内容记录位置柱面号盘面号1AnCai…11人事档案示意文件柱面的最大关键字柱面号CaiLong1柱面索引盘面的最大关键字盘面号PiHong1盘面索引1、基本术语

索引表：除了文件本身（称做数据区）之外，另建立的一张指示逻辑记录和物理记录之间一一对应关系的表。

索引项：索引表中的每一项。总是按关键字（或逻辑记录号）顺序排列。索引文件：包括文件数据区和索引表两大部分的文件。索引顺序文件：数据区中的记录也按关键字顺序排列的

文件。通常为索引顺序文件建立“溢出区”索引非顺序文件：数据区中的记录不按关键字顺序排列。

在记录输入建立数据区的同时建立一个索引表，表中的索引项按记录输入的先后次序排列，待全部记录输入完毕后再对索引表进行排序。2、索引表的生成索引表是由系统程序自动生成的。

非稠密索引：数据文件中的记录按关键字顺序有序，则可对一组记录建立一个索引项，这种索引表称为非稠密索引。

稠密索引：由于数据文件中记录不按关键字顺序排列，则必须对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。

由于索引项的长度比记录小得多，则通常可将索引表一次读入内存，由此在索引文件中进行检索只访问外存两次，即一次读索引，一次读记录。并且由于索引表是有序的，则查找索引表时可用折半查找法。3、索引文件的检索检索方式：直接存取或按关键字（进行简单询问）存取。

检索过程：首先，查找索引表，若索引表上存在该记录，则根据索引项的指示读取外存上该记录;否则说明外存上不存在该记录，也就不需要访问外存。

上述的多级索引是一种静态索引，索引均为顺序表结构。其结构简单，但修改很不方便，每次修改都要重组索引。当记录变动较多时，应采用动态索引。

【如】二叉排序树（或二叉平衡树）、B-树以及键树。5、多级索引查找表：对索引表建立的索引。通常最高可有四级索引：4、索引文件的修改删除操作：删除一个记录时，仅需删去相应的索引项；插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再索引表中插入索引项；更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时修改索引表中相应的索引项。多级索引结构形成m路搜索树数据区一级索引二级索引三级索引四级索引多级索引结构形成m叉树每个分支结点表示一个索引块，最多存放m个索引项每个索引项给出各子树结点(较低一级索引块)的最大关键码和结点地址。叶结点中各索引项给出在数据表中存放的记录的关键码和存放地址。这种m叉树用来作为多级索引，就是m路搜索树7.2.3散列方式用散列（HASH）法组织的文件。特点是用一个散列函数H(key)，将关键字key映射为记录的地址，即:

记录地址=HASH(key)基本步骤:确定记录数存储单位（桶）记录数确定桶数设计HASH(key)函数1、基本术语直接存取文件指的是利用哈希（Hash）法进行组织的文件。它类似于哈希表，既根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故又称散列文件。与哈希表不同，磁盘上的文件记录通常是成组存放的。又称直接存取文件2、溢出处理若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶（Bucket）。假若一个桶能存放m个记录，m个同义词的记录可以存放在同一地址的桶中，当第m＋1个同义词出现时才发生“溢出”。解决溢出：链地址法当发生“溢出”时，需要将第m＋1个同义词存放到另一个桶中，通常称此桶为“溢出桶”；相对地，称前m个同义词存放的桶为“基桶”。溢出桶和基桶大小相同，相互之间用指针相链接。当在基桶中没有待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。3、图形表示例如，某一文件有18个记录，其关键字分别为278，109，063，930，589，184，505，269，008，083，164，215，330，810，620，110，384，355。桶的容量为m＝3，桶数b＝7。用除留余数法作哈希函数H(key)＝keyMOD7。由此得到的直接存取文件如图所示。桶编号 基桶 溢出桶00631841589505008 33023269164410962052782158101103556930083384直接存取文件示例a为存取桶数的期望值（相当于哈希表中的平均查找长度），对链地址处理溢出来说，a=1+α/2；te为存取一个桶所需的时间；ti为在内存中顺序查找一个记录所需的时间。4、查找操作查找过程：首先根据给定值求得哈希地址（即基桶号），将基桶的记录读入内存进行顺序查找，若找到关键字等于给定值的记录，则检索成功；否则，若基桶内没有填满记录或其指针域为空，则文件内不含有待查记录；否则根据指针域的值的指示将溢出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。因此，总的查找时间为T=a(te+ti)，其中：α为装载因子，在散列文件中：其中：n为文件的记录数，b为桶数，m为桶的容量。5、删除操作在直接存取文件中删除记录时，仅需对被删记录作一标记即可。6、直接存取文件的优缺点

优点：文件随机存放，记录不需进行排序；插入、删除方便，存取速度快，不需要索引区，节省存储空间。

缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式限于简单询问，并且在经过多次的插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时亦需重组文件。最大学号204060改进方法：索引链接文件，将链表分拆成多个较多的小链表7.2.4链接方式文件和多重链表文字把文件中的关键字按照主关键字的某种次序用链接字连接起来，整个文件对应一个链表。在记录中保存链接。特点：顺序查找，速度较慢。记录B记录A记录E记录C记录F记录D多关键字文件

特点：在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对关键字进行其他类型的询问检索。1、多重表文件多重表文件（MultilistFile）的特点是：记录按主关键字的顺序构成一个串联文件，建立主关键字的索引（主索引）；对每一个次关键字项建立次关键字索引（次索引），所有具有同一次关键字的记录构成一个链表。主索引为非稠密索引，次索引为稠密索引。每个索引项包括次关键字、头指针和链表长度。数据文件：一个多重表其中，学号为主关键字，记录按学号顺序链接，为了查找方便，分成3个子链表，其索引如图(b)所示，索引项中的主关键字为各子表中的最大值。(b)主关键字索引纪录号姓名学号专业已修学分选修课程01王雯135002软件0241203丙02丁0302马小雁135103软件0739807甲04丙0303阮森135204计算机05436^乙05丙04丁0504苏明明1353^应用0640208甲06丙0805田永135406计算机^38402乙07丁0906杨青135507应用0935610甲0707薛平平135608软件08398^甲08乙^08崔子健1357^软件^40801甲09丙^09王洪135810应用1037005甲10丁^10刘倩1359^应用^36409甲^主关键字头指针135301135705135909(d)“已修学分”索引(e)“选修课目”索引多重表文件示例(c)“专业”索引专业、已修学分和选修课目为3个次关键字项，具有相同次关键字的记录链接在同一链表中。它们的索引如图(c)～(e)所示。次关键字头指针长度软件014计算机032应用044次关键字头指针长度甲027乙033丙015丁014次关键字头指针长度350-399066400-449044记录职工号姓名职务指针性别指针婚否指针工资A29丁一程序员^男E婚E898B05王二维修员E男G婚A456C02赵忠程序员G女D婚B1200D38张三工程师H女F否H2400E31王五维修员F男^婚F456F43刘玉维修员^女H婚^456G17李芳程序员A男A否D1200H46张洪工程师^女^否^3000次关键字长度指针程序员3C维修员3B工程师2D次关键字长度指针男4B女4C次关键字长度指针婚5C否3G职务索引性别索引婚否索引【例7-1】多重链表文件结构2、倒排文件——在索引中保存链接倒排文件和多重表文件的区别在于次关键字索引的结构不同。通常称倒排文件中的次关键字索引为倒排表，具有相同次关键字的记录之间不设指针链接，而在倒排表中该次关键字的一项中存放这些记录的物理记录号。

倒排表作索引的好处在于检索记录较快。特别是对某些询问，不用读取记录，就可得到解答，如询问“软件”专业的学生中有否选课程“乙”的，则只要将“软件”索引中的记录号和“乙”索引中的记录号作求“交集”的运算即可。

在插入和删除记录时，倒排表也要作相应的修改，值得注意的是倒排表中具有同一次关键字的记录号是有序排列的，则修改时要作相应移动。(a)专业倒排表(b)已修学分倒排表(c)选修课目倒排表【例7-2】上例文件的倒排表纪录号姓名学号专业已修学分选修课程01王雯135002软件0241203丙02丁0302马小雁135103软件0739807甲04丙0303阮森135204计算机05436^乙05丙04丁0504苏明明1353^应用0640208甲06丙0805田永135406计算机^38402乙07丁0906杨青135507应用0935610甲0707薛平平135608软件08398^甲08乙^08崔子健1357^软件^40801甲09丙^09王洪135810应用1037005甲10丁^10刘倩1359^应用^36409甲^软件01,02,07,08计算机03,05应用04,06,09,10350-39902,05,06,07,09,10400-44901,03,04,08甲

02,04,06,07,08,09,10乙

03,05,07丙

01,02,03,04,08丁01,03,05,09

若数据文件非串链文件，而是索引顺序文件（如ISAM文件），则倒排表中应存放记录的主关键字而不是物理记录号。倒排文件的缺点：维护困难在同一索引表中，不同的关键字其记录数不同，各倒排表的长度不等，同一倒排表中各项长度也不等。记录职工号姓名职务性别婚否工资A29丁一程序员男婚898B05王二维修员男婚456C02赵忠程序员女婚1200D38张三工程师女否2400E31王五维修员男婚456F43刘玉维修员女婚456G17李芳程序员男否1200H46张洪工程师女否3000次关键字指针程序员CGA维修员BEF工程师DH次关键字指针男BGAE女CDFH次关键字指针婚CBAEF否GDH职务索引性别索引婚否索引【例7-3】倒排文件结构参考7-1：ISAM文件1、基本属于索引顺序存取方法ISAM(IndexedSequentialAccessMethod)：是一种专为磁盘存取设计的文件组织方式，采用静态索引结构。

由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。①磁道索引项基本索引项关键字：表示该磁道中最末一个记录的关键字（在此为最大关键字）指针：指示该磁道中第一个记录的位置。溢出索引项关键字：表示该磁道溢出的记录的最大关键字。指针：指示在溢出区中的第一个记录。②柱面索引项关键字：表示该柱面中最末一个记录的关键字（最大关键字）。指针：指示该柱面上的磁道索引位置。主索引柱面索引磁道索引基本数据区ISAM文件结构示意图图为存放一个磁盘组上的ISAM文件。每个柱面建立一个磁道索引，每个磁道索引项由基本索引项和溢出索引项两部分组成。ISAM文件结构示例

柱面索引存放在某个柱面上，若柱面索引较大，占多个磁道时，则可建立柱面索引的索引——主索引。2、ISAM文件的检索在ISAM文件上检索记录的过程：先从主索引出发找到相应的柱面索引，再从柱面索引找到记录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至找到为止；反之，若找遍该磁道而不存在此记录，则表明该文件中无此记录。3、溢出区和插入操作溢出区是为插入记录所设置的。每个柱面的基本区是顺序存储结构，而溢出区是链表结构。同一磁道溢出的记录由指针相链。溢出区的设置方法：①集中存放：整个文件设一个大的单一的溢出区。②分散存放：每个柱面设一个溢出区。③集中与分散相结合：溢出时记录先移至每个柱面各自的溢出区，待满之后再使用公共溢出区。当插人新记录时，首先找到它应插入的磁道,若该磁道不满，则将新记录插入该磁道的适当位置上即可；若该磁道已满，则新记录或者插在该磁道上，或者直接插入到该磁道的溢出链表上。插入后，可能要修改磁道索引中的基本索引项和溢出索引项。

(3)插入R83，因为80<83<90，则83直接插入溢出区T11’2中，其指针指向T11’0，并修改磁道1的溢出链表，使得表头指向T11’2。(2)插入R95，使得T2中的R145溢出至溢出区T11’1，修改相应磁道索引。

(1)插入R65，首先将1柱面1磁道中大于65的记录顺次后移，导致R90溢出至溢出区T11’0(11磁道0块中)，造成磁道T1中最大关键字成为R80，修改磁道索引，将基本项中最大关键字90修改为80，将溢出项中最大关键字改为90，指针指向T11’0（溢出链表头在11磁道0块中），然后在相应位置插入R65。T11,05、柱面索引的位置假设文件占有n个柱面，柱面索引在第x柱面上，则磁头移动距离的平均值为： 令，得到。这就是说，柱面索引应放在数据文件的中间位置的柱面上。4、删除操作

ISAM文件中删除记录，只需找到待删除的记录，在其存储位置上做删除标记即可，而不需要移动记录或改变指针。但在经过多次的增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出区，而基本区中又浪费很大空间。由此，通常需要周期地整理ISAM文件。把记录读入内存，重新排列，复制成一个新的ISAM文件，填满基本区而空出溢出区。参考7-2：VSAM文件控制区域（ControlRange）：顺序集中一个结点连同对应所有控制区间形成的一个整体。1、基本术语

虚拟存储存取方法VSAM（VirtualStorageAccessMethed）.它也是一种索引顺序文件的组方式，采用B+树作为动态索引结构。该方法利用了操作系统的虚拟存储器的功能，给用户提供方便。对用户来说，文件只有控制区间和控制区域等逻辑存储单位，与外存储器中柱面、磁道等具体存储单位没有必然的联系。控制区间（ControlInterval）：它是一个I/O操作的基本单位，由一组连续的存储单元组成。同一文件上控制区间的大小相同。每个控制区间可视为一个逻辑磁道，而每个控制区域可视为一个逻辑柱面。

在VSAM文件中，记录可以是不定长的，则在控制区间中除了存放记录本身以外，还有每个记录的控制信息和整个区间的控制信息，控制区间的结构如图所示。

在控制区间上存取一个记录时需从控制区间的两端出发同时向中间扫描。

记 记 未利用记录n记录1控制空录录 的的的控制间的控

1n 空闲空间控制信息信息制信息

控制区间的结构示意图2、删除操作在VSAM文件中删除记录时，需将同一控制区间中较删除记录关键字大的记录向前移动，把空间留给以后插入的新记录。若整个控制区间变空，则需修改顺序集中相应的索引项。3、插入操作

VSAM文件中没有溢出区，解决插入的办法是在初建文件时留有空间。每个控制区间内不填满记录，在最末一个记录和控制信息之间留有孔隙；在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。当插入记录时，大多数的新记录能插入到相应的控制区间内，但要注意为了保持区间内记录的关键字自小至大有序，则需将区间内关键字大于插入记录关键字的记录向控制信息的方向移动。若在若干记录插入之后控制区间已满，则在下一个记录插入时要进行控制区间的分裂，既将近乎一半的记录移到同一控制区域中全空的控制区间中，并修改顺序集中相应索引。若控制区域中已经没有全空的控制区间，则要进行控制区域的分裂，此时顺序集中的结点亦要分裂，由此尚需修改索引集中的结点信息。4、VASM文件的特点优点：动态地分配和释放存储空间，不需要对文件进行重组，并能较快地对插入的记录进行查找，查找一个后插入记录的时间与查找一个原有记录的时间是相同的。缺点：占有较多的存储空间，一般只能保持约75％的存储空间利用率。1、UNIX的多重索引

规定每个文件的索引表使用13个登记项（每个登记项有4个字节），前10个登记项直接指出存放文件信息的磁盘块号。如果10个磁盘块不够容纳该文件信息，则利用第11个登记项指向一个磁盘块，该磁盘块作为文件的一级间接索引共有128个登记项（每个登记项为4个字节），可分别指向128个磁盘块。于是，文件的长度可达到138个磁盘块的容量。对于大型文件还可利用第12和第13两个登记项作为二级和三级间接索引参考7-3：了解UNIX文件结构利用主存缓冲区可以把多个逻辑记录一次性保存到磁盘块上。也就是当记录要求存盘时，先存入主存缓冲区，缓冲区的大小等于最大逻辑长度乘以成组的块因子，就是块的大小。在缓冲区未存满时，不启动磁盘写，这样就提高了存储空间的利用率，减少启动外设的次数，提高了系统的工作效率。2、记录的成组：把若干个逻辑记录合成一组存入一块的工作称为“记录的成组”。每块中逻辑记录的个数称“块因子”3、记录的分解：记录成组的一个逆过程。先从磁盘中找到记录所在的块，并将本块读入主存缓冲区，再从缓冲区取出所需要的记录送到用户工作区。如果用户所需的记录已经在缓冲区中，则不需要启动外设读块信息，这也可以提高系统工作效率。归并方法：首先将文件中的数据输入到内存，采用内部分类方法进行分类（归并段），然后将有序段写回外存；对多归并段进行多遍归并，最后形成一个有序序列。7.3磁盘文件的归并分类磁盘信息的存取

磁盘：是一个扁平的圆盘，盘面上有许多称为磁道的圆圈，信息就记载在磁道上。它是一种直接存取的存储设备（DASD）。

磁盘的工作原理：盘片装在一个主轴上，并绕主轴高速旋转，当磁道在读/写头下通过时，便可进行信息的读/写。读/写信息的功能由磁盘驱动器执行。

固定头盘：固定头盘的每一磁道上都有独立的磁头，这些磁头固定不动，专负责读/写某一磁道上的信息。

活动头盘：活动头盘的磁头是可以移动的。一个盘面上只有一个磁头，磁头装在一个动臂上，可以从该面上的一道移动到另一道。

在磁盘上表明一个具体信息必须用一个三维地址：柱面号（确定读/写头的径向运动)、盘面号、块号(确定信息在盘片圆圈上的位置）。磁盘结构：由磁盘驱动器、读、写磁头、活动臂、盘片（磁道、扇区）、旋转主轴构成。速度快、容量大、直接存取设备。访问一块信息：（1）找柱面,移动臂使磁头移动到所需柱面上(称为定位或寻查)；（2）等待要访问的信息转动磁头之下；（3）读/写所需信息。磁盘上读写一块信息所需的时间为：TI/O=tseek+tla+n*twm其中：tseek为寻查时间（seektime）：读/写头定位的时间；

tla为等待时间（latencytime）：

等待信息块的初始位置旋到读/写头下的时间；

twm为传输时间（transmissiontime）。【例7-4】假设一个磁盘文件，由4500个记录组成，分别记为A1,A2,……,A4500设系统提供容纳750个记录的内存共分类使用，每次磁盘读写250个记录的数据块，则可设计分类过程如下：(1)每次从文件中输入三个数据块（750个记录）到工作空间，进行内部分类。分类结果写回磁盘，构成6个初始归并段：R1,R2,R3,R4,R5,R6R1R2R3R4R5R61-750751-15001501-22502251-30003001-37503751-4500（2）将内存空间三等分，每块250个记录，其中2块为输入缓冲区，1块为输出缓冲区。归并R1和R2，输出到输出缓冲区，若输出缓冲区满，则写盘。同样，若R1和R2的缓冲区出现空，则继续读盘，直到归并结束为止。R12=R1+R2；同样得到：R34=R3+R4,R56=R5+R6；R12、R34、R56分别都包含1500个记录。（3）类似（2）的方法，可将R12和R34归并成R1234,，再将R1234和R56进行归并。得到最后的排序结果。R1R2R3R4R5R6R12R34R56R1234R12346×750记录3×1500记录12×250记录18×250记录K路归并……...遍数[log2m]层数[log2m]+1M个归并段的归并过程R1R2Rm-1Rm2…KK+1…2K……m...logkm+1levers(1)多路归并——减少归并遍数并行操作的缓冲区处理——使输入、输出和CPU处理尽可能重叠(3)初始归并段的生成讨论问题：logkm遍比较次数：扩大初始归并段长度，从而减少初始归并段个数m进行多路(k路)归并减少合并趟数s，以减少I/O次数

s=logkm提高外排序效率的途径：(1)多路归并——减少归并遍数m个初始段进行2路归并，需要log2m遍归并;m个初始段，采用k路归并，需要logkm遍归并。显然，k越大，归并遍数越少，可提高归并的效率。

在k路归并时，从k个关键字中选择最小记录时，要比较K-1次。若记录总数为n，每遍要比较的次数为：

n*(k-1)[log2m/log2k]可以看出，随着k增大，(k-1)/log2k也增大，当归并路数多时，CPU处理的时间也随之增多。为此要选择好的分类方法，以减少分类中比较次数。610920689901796817681516203820301525155011161001101820

选择树(Selectiontree)或败者树(treeofloser)分析：第一次建立选择树的比较所花时间为:O(k-1)=O(k)而后每次重新建造选择树所需时间为：

O(log2k)n个记录处理时间为初始建立选择树的时间加上n-1次重新选择树的时间：

O((n-1)·

log2k)+O(k)=O(n·

log2k)这就是k路归并一遍所需的CPU处理时间。归并遍数为logkm，总时间为：

O(n·

log2k·

logkm)=O(n·

log2m)(k路归并CPU时间与k无关)最佳归并树

将哈夫曼树进行拓展，不仅对2叉树，同样可形成3叉、4叉、…、k叉树，亦称为哈夫曼树，同样可求得带权路径长度最小。对长度不等的m个初始归并段，构造哈夫曼树作为归并树，可使在进行外部归并时所需要对外存进行的读写次数达到最小。

最佳归并树中，并不只是只有度为k和0的结点，会有缺额。当初始归并段的数目不足时，需附加长度为0的虚段，按照哈夫曼树的构造原则，权为0的叶子结点应离树根最远。问题：起因：由于初始归并段通常不等长,进行归并时,长度不同的初始归并段归并的顺序不同,读写外存的总次数也不同。目的：减少读写外存的次数。【例7-5】9个初始归并段，记录数分别为9、30、12、18、3、17、2、6、24。如果进行3-路归并，请讨论在各种情况下的对外存的读写次数。从外存读121个记录写入外存121个记录从外存读121个记录写入外存121个记录30129317186242513832121总共读写外存484个记录读写磁盘次数=∑wj·

lj=(9+30+12+18+3+17+2+6+24)*2=242从外存读11个记录写入外存11个记录从外存读91个记录写入外存121个记录写入外存91个记录从外存读121个记录62392417183011325912112总共读写外存446个记录读写磁盘次数=∑wj·

lj=(2+3+6)*3+(9+12+17+18+24)*2+30*1=223按照hafuman树的思想，记录少的段最先合并。不够时增加虚段【例7-6】8个初始归并段，记录数分别为2、3、6、9、12、17、18、24。如果进行3-路归并，请讨论在各种情况下的对外存的读写次数。从外存读5个记录写入外存5个记录从外存读67个记录写入外存91个记录写入外存67个记录从外存读91个记录共读写326个记录读写磁盘次数=∑wj·

lj=(2+3)*3+(6+9+12+17+18)*2+24*1=163

虚段的补法:

在K路平衡归并时，它的归并树的模型是一棵度为K的树。在这棵树上的结点要么是叶子，要么是具有K个孩子的内部结点。设具有K个孩子的内部结点共有nk

个。初始归并段的个数为m个。设n=nk+m，故：从结点出发的分枝，共计有K*nk

个。若从进入结点的角度进行考虑，则共有：nk+m-1注意：没有分枝进入根结点。所以，K*nk＝nk+m-1

于是：nk=(m-1)/(K-1)

这就意味着，若(m-1)MOD(K-1)＝0，无需增加虚段。否则，要增加虚段，其数目为：（K-1)-(m-1)MOD(K-1)限制：由于磁带寻找具有最少记录的初始归并段，必须反复倒带。所以，实用性不强；在磁盘的情况下，需要有段包含的记录数信息、段的位置信息等；文件如集中放置在几个相邻的柱面上的情况比较合适。并行操作的缓冲区处理----1324ou(1)ou(2)iu(1)iu(2)----iu(3)iu(4)12---3-457--34----57615归并到ou(1)输入到in(3)归并到ou(2)输入到in(4)输出ou(1)(a)(b)(c)56

89---7-15

78-92025---159-

--2025

-15归并到ou(1)输入到in(1)归并到ou(1)输入到in(3)输出ou(2)(d)(e)(f)归并到ou(2)输入到in(2)输出ou(1)输出ou(2)

对k个归并段进行k路归并至少需要k个输入和1个输出缓冲区，要使输入、输出和归并同时进行，k+1个缓冲区是不够的，需要2k个输入缓冲区实现并行操作。135789246152025(3)初始归并段的生成步12345678910111213…缓冲区内容151515(11)(11)(11)(11)(11)(11)1111(06)……1919191925(16)(16)(16)(16)161616……04122727272734(26)(26)262626……8383838383838383(07)109090……输出结果0412151925273483

07101116…R1R2(a)初始归并段的长度≥缓冲区的长度(b)任何内部分类算法都可作为生成初始归并段的算法(c)例如：缓冲区的长度为4，输入序列为：

151904831227112516342607109006…新输入记录.key小于当前记录.key，等待下一个归并段采用置换-选择法生成初始归并段的长度平均是缓冲区长度的两倍。磁盘文件的归并分类小结：1、磁盘文件的特点2、要解决的问题

（1）多路归并—减少归并遍数k路归并，选择树，最佳归并树（k-叉哈夫曼树）

（2）并行操作的缓冲区处理—使输入、输出和CPU处理尽可能重叠

2k个输入缓冲区，2个输出缓冲区

（3）初始归并段的生成

置换-选择法，生成初始归并段长度平均是缓冲区长度的两倍7.4磁带文件的归并分类（外部）存储设备——纸带、磁鼓、磁带、磁盘等磁带信息的表示：一种磁化方向、代表1另一种磁化方向，代表00100100110101111参考资料：关于磁带

磁带：一条薄薄涂上一层磁性材料的窄带（现在使用的磁带大多数有1/2英寸宽，最长可达3600英尺，绕在一个卷盘上）。它是一种顺序存取的存储设备。

磁带的工作原理：使用时，将磁带放在磁带机上，驱动器控制磁带盘转动，带动磁带向前移动。通过读/写头就可以读出磁带上的信息或者把信息写入磁带中。

7道带：在1/2英寸宽的带面上记录7位二进制信息的磁带。

9道带：在1/2英寸宽的带面上记录9位二进制信息的磁带。每一横排可表示一个字符（8位表示一个字符，剩下的一位作奇偶校验位）。

信息密度：每英寸的二进制字符数。通常为每英寸800位或1600位或6250位。移动速度：每秒200英寸。

间隙IRG（InterRecordGap）：磁带上相邻两组字符组（记录）之间的空白区。根据启停时间的需要，这个间隙通常为1/4~3/4英寸。

例如，若每个字符组的长度是80个字符，IRG为3/4英寸，则对密度为每英寸1600个字符的磁带，其利用率仅为1/16，有15/16的带用于IRG。如图11.1(a)所示。

块间间隙IBG（InterBlockGap）：将若干个字符组合并成块，每个字符组间没有IRG，而变成块间的间隙。

例如，图(b)表示将20个长度为80字符的字符组存放在磁带上的一个物理块中的情况。IRGIRGIRG记录(a)字符组长80字符的磁带IBGIBGIBG20个记录20个记录20个记录(b)成块存放的磁带磁带上信息存放示意图磁带上读写一块信息所需的时间为： TI/O=ta+n*tw其中：ta为延迟时间，读/写头到达传输信息所在物理块起始位置所需时间（显然，延迟时间和信息在磁带上的位置、当前读/写头所在位置有关）；tw为传输一个字符的时间。成块的优点：（1）可以减少IRG的数目，从而提高磁带的利用率，块的长度大于IBG的长度。（2）可以减少I/O操作。因为一次I/O操作可把整个物理块都读到内存缓冲区中，然后再从缓冲区中取出所需要的信息（一个字符组）。每当要读一个字符组时，首先要查缓冲区中是否已有，若有，则不必执行I/O操作，直接从缓冲区读取即可。

与磁盘不同，磁带是顺序存储设备，读取信息块的时间与信息块的位置有关。研究磁带分类，需要了解信息块的分布。K路平衡归并分类磁带机数量：2k输入：T1,T2,……,Tk

输出输出：Tk+1,Tk+2,……,T2k

输入磁带机T1T2…Tk归并段R1R2…RkRk+1Rk+2…R2k…………Rmk+1………T1:R1(1000),R3(1000),R5(1000)T2:R2(1000),R4(1000),R6(1000)T3:ØT4:ØT1:ØT2:ØT3:

R1(2000),R3(2000)T4:R2(2000)T1:R1(4000)T2:

R2(2000)T3:ØT4:ØT1:ØT2:ØT3:R1(6000)

T4:Øi遍后t1t2t3开始13(1L)21(L)空1空8(1L)13(2L)28(3L)空5(2L)33(3L)5(5L)空4空2(5L)3(8L)52(13L)空1(8L)61(13L)1(21L)空7空空1(34L)步t1t2t3总段数n0011n-11102n-22013n-30235n-43508n-580513n-6081321n-71321034以k=2为例，用三台磁带机T1，T2，T3，假设初始归并段长度为L。初始归并段的段数为34。过程如表1所示。将上例递归过程从最后一步逆推，如表2所示。每一步归并段总数排列成序列为：1，2，3，5，8，13，21，34,…刚好组成Fibonacci数列，Fk=Fk-1+Fk-2K路多阶段归并，可从2路归并扩充，对应k阶Fibonacci数列。0≤n≤K-2n=K-1n≥K……结论：K+1台磁带机k路多阶段归并，在n-j步归并段的分布规则=〉第j步归并断总数：其中第j步中逻辑磁带机上第i台磁带机。表示：空磁带机台号=K+1当j=0或k+1的整数倍j%(k+1)j不为上述值注意：在多路归并中，若要求归并的文件其初始归并段总数不是K阶Fibonacci数，则需附加一些虚的归并段数，以凑成k阶Fibonacci数，同时还应该将虚归并段适当地分布在k路归并的k台磁带上。每一步都有一台磁带机是空的。【例7-7】设有磁盘文件中记录的关键字分别为：

10,20,15,25,12,13,21,30,8,16,10

用置换-选择排序法产生初始归并段，问可产生几个初始归并段？每个初始归并段包含哪些记录（设工作区能容纳4个记录）。解：内存缓冲区可容纳4个记录，采用4路归并的置换-选择排序方法生成初始