数据结构__文件

第十二章文件￡12.1有关文件的基本概念￡12.2顺序文件￡12.3索引文件￡12.4ISAM和VSAM文件￡12.4.1ISAM文件￡12.4.2VSAM文件￡12.5直接存取文件（散列文件）￡12.6多关键字文件￡12.6.1多重表文件￡12.6.2倒排文件第十二章文件文件是大量记录的集合。习惯上称存储在主存储器（内存储器）中的记录集合为表，称存储在二级存储器（外存储器）中的记录集合为文件。￡12.1有关文件的基本概念（1）文件及其类别文件（file）：是由大量性质相同的记录组成的集合。数据项：最基本的不可分的数据单位，是文件中可使用的数据的最小单位。属性：记录中所有非关键字的数据项，称为记录的属性。按记录的类型不同可分成：①操作系统的文件：操作系统中的文件仅是一维的连续的字符序列，无结构、无解释。②数据库文件：数据库中的文件是带有结构的记录的集合。这类记录是由一个或多个数据项组成的集合，它也是文件中可存取的数据的基本单位。按记录中关键字的多少数据库文件可分成：1.单关键字文件：文件中的记录只有一个唯一标识记录的主关键字。2.多关键字文件：文件中的记录除了含有一个主关键字外，还含有若干个次关键字。按记录含有信息的长度不同可分成：①定长记录文件：文件中每个记录含有的信息长度相同。②不定长记录文件：文件中每个记录含有的信息长度不等。（2）记录的逻辑结构和物理结构记录的逻辑结构：是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。着眼于用户使用方便。记录的物理结构：是数据在物理存储器上存储的方式，是数据的物理表示和组织。着眼于提高存储空间的利用率和减少存取记录的时间。物理记录和逻辑记录之间可能存在下列3种关系：①一个物理记录存放一个逻辑记录；②一个物理记录包含多个逻辑记录；③多个物理记录表示一个逻辑记录。（3）文件的操作（运算）文件的检索：①顺序存取：存取下一个逻辑记录。②直接存取：存取第i个逻辑记录。①②两种存取方式都是根据记录序号(即记录存入文件时的顺序编号)或记录的相对位置进行存取的。③按关键字存取：给定一个值，查询一个或一批关键字与给定值相关的记录。对数据库文件可以有如下4种查询方式：1.简单询问：查询关键字等于给定值的记录。2.区域询问：查询关键字属某个区域内的记录。3.函数询问：给定关键字的某个函数。4.布尔询问：以上3种询问用布尔运算组合起来的询问。文件的修改：文件的修改包括插入一个记录、删除一个记录和更新一个记录3种操作。文件的操作可以有实时和批量两种不同方式。通常实时处理对应答时间要求严格，应在接受询问之后几秒钟内完成检索和修改，而批量的处理则不然。例如，银行的帐户系统需实时检索，但可进行批量修改，即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进行批量处理。（4）文件的物理结构文件的物理结构：文件在存储介质（磁盘或磁带）上的组织方式。文件的基本组织方式：①顺序组织；②随机组织；③链组织。￡12.2顺序文件串联文件：物理记录之间的次序由指针相链表示的顺序文件。（1）定义顺序文件（SequentialFile）：是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。连续文件：次序相继的两个物理记录在存储介质上的存储位置是相邻的顺序文件。（2）特点顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。它的特点是：①存取第i个记录，必须先搜索在它之前的i－1个记录。②插入新的记录时只能加在文件的末尾。③若要更新文件中的某个记录，则必须将整个文件进行复制。（3）磁带上顺序文件的批处理主文件：待修改的原始文件。事务文件：所有的修改请求集中构成的一个文件。磁带文件的批处理过程：首先对事务文件进行排序，然后将主文件和事务文件归并成一个新的主文件。图12.1为这个过程的示意图。终端事务文件排序有序的事务文件主文件新主文件图12.1磁带文件批处理示意图其中，主文件、事务文件和新的主文件分别存放中一台磁带上。主文件按关键字自小至大（或自大至小）顺序有序，事务文件必须和主文件有相同的有序关系。在归并的过程中，顺序读出主文件与事务文件中的记录，比较它们的关键字并分别进行处理。对于关键字不匹配的主文件中的记录，则直接将其写入新主文件中。“更改”和“删除”记录时，要求其关键字相匹配。“删去”不用写入，而“更改”则要将更改后的新记录写入新主文件。“插入”时不要求关键字相匹配，可直接将事务文件上要插入的记录写到新主文件的适当位置。算法实现：批处理的示意算法如算法12.1所示。算法中用到的各符号的含义说明如下：f——主文件；g——事务文件；h——新主文件。它们都按关键字递增排序。事务文件的每个记录中，增设一个代码以示修改要求，其中：“I”表示插入；“D”表示删去；“U”表示更改。voidMergeFile(FILE*f,FILE*g,FILE*h){//由按关键字递增有序的非空顺序文件f和g归并得到新文件h，//三个文件均已打开，其中，f和g为只读文件，文件中各附加//一个最大关键字记录，且g文件中对该记录的操作为插入。//h为只写文件。fread(*fr,sizeof(RcdType),1,f);fread(*gr,sizeof(RcdType),1,g);算法12.1如下：while(!feof(f)||!feof(g)){switch{casefr.keygr.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.keygr.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（个记录），则整个批处理过程中读/写外存的次数为：snmsm*2*2￡12.3索引文件非稠密索引：数据文件中的记录按关键字顺序有序，则可对一组记录建立一个索引项，这种索引表称为非稠密索引。（1）基本术语索引表：除了文件本身（称做数据区）之外，另建立的一张指示逻辑记录和物理记录之间一一对应关系的表。索引项：索引表中的每一项。总是按关键字（或逻辑记录号）顺序排列。索引文件：包括文件数据区和索引表两大部分的文件。索引顺序文件：数据区中的记录也按关键字顺序排列的文件。索引非顺序文件：数据区中的记录不按关键字顺序排列的文件。稠密索引：由于数据文件中记录不按关键字顺序排列，则必须对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。例如，图12.2为两个索引表的例子。014101151171190420(不存在)12331311012511关键字ki物理记录号逻辑记录号标识物理记录号图12.2索引表示例在记录输入建立数据区的同时建立一个索引表，表中的索引项按记录输入的先后次序排列，待全部记录输入完毕后再对索引表进行排序。（2）索引表的生成索引表是由系统程序自动生成的。例如，对应于图12.3(a)的时间文件，其索引表如图12.3(b)，而图12.3(c)为文件建立输入过程中建立的索引表。10129张珊程序员.10305李四维修员.10402王红程序员.10538刘琪穿孔员.10831..10943..11017..11248..物理记录号职工号姓名职务其他(a)文件数据区图12.3索引非顺序文件示例(b)索引表(c)输入过程中建立的索引表02104291010510305103171100210429101381053110831108381054310943109171104811248112关键字物理记录号关键字物理记录号123（3）索引文件的检索检索方式：直接存取或按关键字（进行简单询问）存取。检索过程：首先，查找索引表，若索引表上存在该记录，则根据索引项的指示读取外存上该记录;否则说明外存上不存在该记录，也就不需要访问外存。由于索引项的长度比记录小得多，则通常可将索引表一次读入内存，由此再索引文件中进行检索只访问外存两次，即一次读索引，一次读记录。并且由于索引表是有序的，则查找索引表时可用折半查找法。（4）索引文件的修改①删除操作：删除一个记录时，仅需删去相应的索引项；②插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再索引表中插入索引项；③更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时修改索引表中相应的索引项。（5）多级索引查找表：对索引表建立的索引。例如，假设图12.3(b)的索引表需占3个物理块的外存，每一个物理块容纳3个索引，则建立的查找表如图12.4所示。检索记录时，先查找查找表，再查索引表，然后读取记录。图12.4图12.3(b)中索引表的索引最大关键字物理块号171382463通常最高可有四级索引：第三查找表第二查找表查找表索引表数据文件上述的多级索引是一种静态索引，各级索引均为顺序表结构。其结构简单，但修改很不方便，每次修改都要重组索引。因此，当数据文件在使用过程中记录变动较多时，应采用动态索引。如,二叉排序树（或二叉平衡树）、B-树以及键树。￡12.4ISAM和VSAM文件￡12.4.1ISAM文件（1）定义索引顺序存取方法ISAM(IndexedSequentialAccessMethed)：是一种专为磁盘存取设计的文件组织方式。由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。例如，图12.5为存放一个磁盘组上的ISAM文件。每个柱面建立一个磁道索引，每个磁道索引项由：基本索引项和溢出索引项两部分组成，如图12.6所示。①磁道索引项：基本索引项：关键字：表示该磁道中最末一个记录的关键字（在此为最大关键字）。指针：指示该磁道中第一个记录的位置。溢出索引项：关键字：表示该磁道溢出的记录的最大关键字。指针：指示在溢出区中的第一个记录。②柱面索引项：关键字：表示该柱面中最末一个记录的关键字（最大关键字）。指针：指示该柱面上的磁道索引位置。图12.5ISAM文件结构示例R164磁道索引50磁道索引柱面C1柱面索引主索引R14R21R45R47R50164164164330溢出区溢出区溢出区柱面C2柱面C3R189R215R33011