中国科大数据结构

《数据结构》课程中国科学技术大学网络学院数据结构第十二章文件本章内容12.1有关文件的基本概念12.2顺序文件12.3索引文件12.4ISAM和VSAM文件12.5直接存取文件12.6多关键字文件中国科大《数据结构》12-312.1有关文件的基本概念文件：是大量记录的集合。习惯上称存储在主存储器（内存储器）中的记录集合为表，称存储在二级存储器（外存储器）中的记录集合为文件。数据项：是文件中可使用的、不可分的的最小数据单位。属性：记录中所有非关键字的数据项，称为记录的属性。文件类别按记录的类型不同可分成：操作系统的文件：操作系统中的文件仅是一维的连续的字符序列，无结构、无解释。数据库文件：数据库中的文件是带有结构的记录的集合。这类记录是由一个或多个数据项组成的集合，它也是文件中可存取的数据的基本单位。按记录中关键字的多少数据库文件可分成：单关键字文件：文件中记录只有一个唯一标识记录的主关键字。多关键字文件：文件中记录除了含有一个主关键字外，还含有若干个次关键字。中国科大《数据结构》12-412.1有关文件的基本概念按记录含有信息的长度不同可分成：定长记录文件：文件中每个记录含有的信息长度相同。不定长记录文件：文件中每个记录含有的信息长度不等。记录的逻辑结构和物理结构记录的逻辑结构：是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。着眼于用户使用方便。记录的物理结构：是数据在物理存储器上存储的方式，是数据的物理表示和组织。着眼于提高存储空间的利用率和减少存取记录的时间。物理记录和逻辑记录之间可能存在下列三种关系：1.一个物理记录存放一个逻辑记录；2.一个物理记录包含多个逻辑记录；3.多个物理记录表示一个逻辑记录。中国科大《数据结构》12-512.1有关文件的基本概念记录的逻辑结构与物理结构的差别示例中国科大《数据结构》12-612.1有关文件的基本概念文件的操作：主要有两类，即检索与修改文件的检索：主要有三种方式：顺序存取：存取下一个逻辑记录。直接存取：存取第i个逻辑记录。按关键字存取：给定一个值，查询一个或一批关键字与给定值相关的记录。对数据库文件可以有如下4种查询方式：1.简单询问：查询关键字等于给定值的记录。2.区域询问：查询关键字属某个区域内的记录。3.函数询问：给定关键字的某个函数。4.布尔询问：以上3种询问用布尔运算组合起来的询问。文件的修改：文件的修改包括：插入一条记录；删除一条记录更新一条记录。中国科大《数据结构》12-712.1有关文件的基本概念文件的操作有实时和批量两种处理方式实时操作要求有较短的应答响应时间，在接受指令后尽可能快地完成检索或修改任务。批量的文件处理则允许较长反馈时间。用户可以根据需求选择不同的文件处理方式。批量处理方式可减少更新操作的代价例如，银行的帐户系统需实时检索，但可进行批量修改，即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进行批量处理。事务文件有序的排序事务文件终端主文件新主文件批处理示意图中国科大《数据结构》12-812.1有关文件的基本概念文件的物理结构文件在存储介质（磁盘或磁带）上的组织方式。文件逻辑组织形式：1.顺序结构的定长记录；2.顺序结构的变长记录；3.按关键码存取的记录。文件物理组织方形式：1.顺序文件2.散列文件3.索引文件4.倒排文件中国科大《数据结构》12-912.2顺序文件定义：顺序文件（SequentialFile）：是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。连续文件：次序相继的两个物理记录在存储介质上的存储位置是相邻的顺序文件。串联文件：物理记录之间的次序由指针相链表示的顺序文件。特点：顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。它的特点是：存取第i个记录，必须先搜索在它之前的i－1个记录。插入新的记录时只能加在文件的末尾。若要更新文件中的某个记录，则必须将整个文件进行复制。中国科大《数据结构》12-1012.2顺序文件顺序文件的操作：一般由三种不同的方法：1.顺序存取是从文件的第一个记录开始依次顺序进行存取。这种方法存取效率很高。2.随机存取是希望对指定的记录直接进行存取。但是这种要求对于顺序文件来说，是极不方便的，存取效率很低。3.按关键字存取是按记录的关键字值进行存取。这种方法对于顺序文件来讲，也需要从文件的第一个记录开始进行查找，因此，在一般情况下，存取效率不高。中国科大《数据结构》12-1112.2顺序文件批处理算法实现批处理的示意算法如教材p310的算法12.1所示。算法中用到的各符号的含义说明如下：F：主文件；G：事务文件；H：新主文件。它们都按关键字递增排序。事务文件的每个记录中，增设一个代码以示修改要求，其中：I：表示插入；D：表示删除；U：表示更改。中国科大《数据结构》12-1212.2顺序文件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);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中国科大《数据结构》12-1312.2顺序文件分析批处理算法的时间假设主文件包含n个记录，事务文件包含m个记录。一般情况下，事务文件较小，可以进行内部排序，则时间复杂度为O(m*logm)。内部归并的时间复杂度为O(n＋m)，则总的内部处理时间为O(m*logm＋n)。假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区大小为s（个记录），则整个批处理过程中读/写外存的次数为：2m/s+(m+n)/s）中国科大《数据结构》12-1412.3索引文件基本术语索引表：除了文件本身（称做数据区）之外，另建立的一张指示逻辑记录和物理记录之间一一对应关系的表。索引项：索引表中的每一项。总是按关键字（或逻辑记录号）顺序排列。索引文件：包括文件数据区和索引表两大部分的文件。索引顺序文件：数据区中的记录也按关键字顺序排列的文件。索引非顺序文件：数据区中的记录不按关键字顺序排列的文件。稠密索引：由于数据文件中记录不按关键字顺序排列，则必须对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。非稠密索引：数据文件中的记录按关键字顺序有序，则可对一组记录建立一个索引项，这种索引表称为非稠密索引。中国科大《数据结构》12-1512.3索引文件例如，下图为两个索引表的例子。逻辑记录号存在标识物理记录号01111720null3110关键字ki物理记录号1011190119117812311601251142物理地址职工号姓名性别工资1142125张三男35001160123李四女40001178119王五男45001190101黄六男2800中国科大《数据结构》12-1612.3索引文件索引文件的存储索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存放主文件。索引文件的建立建立索引文件的过程：1.按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的2.待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件。中国科大《数据结构》12-1712.3索引文件检索操作检索分两步进行：1.将外存上含有索引区的页块送人内存，查找所需记录的物理地址2.将含有该记录的页块送人内存注意：索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。由于索引表有序，对索引表的查找可用顺序查找或二分查找中国科大《数据结构》12-1812.3索引文件索引文件的修改删除操作：删除一个记录时，仅需删去相应的索引项；插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再索引表中插入索引项；更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时修改索引表中相应的索引项。多级索引：查找表：对索引表建立的索引。通常最高可有四级索引：数据文件索引表查找表第二查找表第三查找表多级索引是静态索引，各级索引均为顺序表结构。其结构简单，但修改很不方便，每次修改都要重组索引。因此，当数据文件在使用过程中记录变动较多时，应采用动态索引。如二叉排序树（或二叉平衡树）、B-树以及键树。中国科大《数据结构》12-1912.4ISAM和VSAM文件12.4.1ISAM文件ISAM文件定义：索引顺序存取方法ISAM(IndexedSequentialAccessMethod)是一种专为磁盘存取设计的文件组织方式。磁盘是以盘组、柱面和磁道三级地址存取的设备，可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。磁道索引项：基本索引项：关键字：表示该磁道中最末一个记录的关键字（在此为最大关键字）。指针：指示该磁道中第一个记录的位置。溢出索引项：关键字：表示该磁道溢出的记录的最大关键字。指针：指示在溢出区中的第一个记录。中国科大《数据结构》12-2012.4ISAM和VSAM文件柱面索引项：关键字：表示该柱面中最末一个记录的关键字（最大关键字）。指针：指示该柱面上的磁道索引位置。ISAM文件的组成ISAM文件由多级主索引、柱面索引、磁道索引和主文件组成。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上。对同一柱面，则应按盘面的次序顺序存放。中国科大《数据结构》12-2212.4ISAM和VSAM文件在ISAM文件上检索记录时，先从主索引出发检索到相应的柱面索引，然后从柱面索引检索到记录所在柱面的磁道索引，最后从磁道索引检索到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至检索到为止；反之，若检索遍磁道而不存在此记录，则表明文件中无此记录。ISAM文件中删除记录比较简单，只需作删除标记而不用移动记录或改变指针。当然应该周期性地把记录读入内存重排整理ISAM文件，以尽量填满基本区而空出溢出区。中国科大《数据结构》12-2312.4ISAM和VSAM文件12.4.2VSAM文件V