中国科大数据结构精编版

《中国科大数据结构精编版》由会员分享，可在线阅读，更多相关《中国科大数据结构精编版（36页珍藏版）》请在金锄头文库上搜索。

1、数据结构第十二章文件,本章内容 12.1 有关文件的基本概念 12.2 顺序文件 12.3 索引文件 12.4 ISAM和VSAM文件 12.5 直接存取文件 12.6 多关键字文件,12-2,12.1 有关文件的基本概念,文件：是大量记录的集合。习惯上称存储在主存储器（内存储器）中的记录集合为表，称存储在二级存储器（外存储器）中的记录集合为文件。 数据项：是文件中可使用的、不可分的的最小数据单位。 属性：记录中所有非关键字的数据项，称为记录的属性。 文件类别 按记录的类型不同可分成： 操作系统的文件：操作系统中的文件仅是一维的连续的字符序列，无结构、无解释。 数据库文件：数据库中的文件是带有

2、结构的记录的集合。这类记录是由一个或多个数据项组成的集合，它也是文件中可存取的数据的基本单位。 按记录中关键字的多少数据库文件可分成： 单关键字文件：文件中记录只有一个唯一标识记录的主关键字。 多关键字文件：文件中记录除了含有一个主关键字外，还含有若干个次关键字。,12-3,12.1 有关文件的基本概念,按记录含有信息的长度不同可分成： 定长记录文件：文件中每个记录含有的信息长度相同。 不定长记录文件：文件中每个记录含有的信息长度不等。 记录的逻辑结构和物理结构 记录的逻辑结构：是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。着眼于用户使用方便。 记录的物理结构：是数据

3、在物理存储器上存储的方式，是数据的物理表示和组织。着眼于提高存储空间的利用率和减少存取记录的时间。 物理记录和逻辑记录之间可能存在下列三种关系： 一个物理记录存放一个逻辑记录； 一个物理记录包含多个逻辑记录； 多个物理记录表示一个逻辑记录。,12-4,12.1 有关文件的基本概念,记录的逻辑结构与物理结构的差别示例,12-5,12.1 有关文件的基本概念,文件的操作：主要有两类，即检索与修改 文件的检索：主要有三种方式： 顺序存取：存取下一个逻辑记录。 直接存取：存取第i个逻辑记录。 按关键字存取：给定一个值，查询一个或一批关键字与给定值相关的记录。对数据库文件可以有如下4种查询方式： 简单询

4、问：查询关键字等于给定值的记录。 区域询问：查询关键字属某个区域内的记录。 函数询问：给定关键字的某个函数。 布尔询问：以上3种询问用布尔运算组合起来的询问。 文件的修改：文件的修改包括： 插入一条记录； 删除一条记录 更新一条记录。,12-6,12.1 有关文件的基本概念,文件的操作有实时和批量两种处理方式 实时操作要求有较短的应答响应时间，在接受指令后尽可能快地完成检索或修改任务。 批量的文件处理则允许较长反馈时间。用户可以根据需求选择不同的文件处理方式。批量处理方式可减少更新操作的代价 例如，银行的帐户系统需实时检索，但可进行批量修改，即可以将一天的存款和提款记录在一个事务文件上，在一天

5、的营业之后再进行批量处理。,12-7,12.1 有关文件的基本概念,文件的物理结构 文件在存储介质（磁盘或磁带）上的组织方式。 文件逻辑组织形式： 顺序结构的定长记录； 顺序结构的变长记录； 按关键码存取的记录。 文件物理组织方形式： 顺序文件 散列文件 索引文件 倒排文件,12-8,12.2 顺序文件,定义：顺序文件（Sequential File）：是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。 连续文件：次序相继的两个物理记录在存储介质上的存储位置是相邻的顺序文件。 串联文件：物理记录之间的次序由指针相链表示的顺序文件。 特点：

6、顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。它的特点是： 存取第i个记录，必须先搜索在它之前的i1个记录。 插入新的记录时只能加在文件的末尾。 若要更新文件中的某个记录，则必须将整个文件进行复制。,12-9,12.2 顺序文件,顺序文件的操作：一般由三种不同的方法： 顺序存取是从文件的第一个记录开始依次顺序进行存取。这种方法存取效率很高。 随机存取是希望对指定的记录直接进行存取。但是这种要求对于顺序文件来说，是极不方便的，存取效率很低。 按关键字存取是按记录的关键字值进行存取。这种方法对于顺序文件来讲，也需要从文件的第一个记录开始进行查找，因此，在一般情况下，存取效率不高

7、。,12-10,12.2 顺序文件,批处理算法实现 批处理的示意算法如教材p310的算法12.1所示。算法中用到的各符号的含义说明如下： F：主文件； G：事务文件； H：新主文件。 它们都按关键字递增排序。事务文件的每个记录中，增设一个代码以示修改要求，其中： I：表示插入； D：表示删除； U：表示更改。,12-11,12.2 顺序文件,void MergeFile (FILE *f, FILE *g, FILE *h) /由按关键字递增有序的非空顺序文件f和g归并得到新文件h， /三个文件均已打开，其中，f和g为只读文件，文件中各附加 /一个最大关键字记录，且g文件中对该记录的操作为插入

8、。 / h为只写文件。 fread (*fr, sizeof(RcdType), 1, f); fread (*gr, sizeof(RcdType), 1, g); while (!feof (f) | | !feof (g) switch case fr.key gr.key: /插入,函数P把gr加工为h的结构 fwrite (P(gr), sizeof(RcdType), 1, h); if (!feof (g) fread (*gr, sizeof(RcdType), 1, g); break;,case gr.code = = U /其他均为出错情况 / switch / whil

9、e / MergeFile,12-12,12.2 顺序文件,分析批处理算法的时间 假设主文件包含n个记录，事务文件包含m个记录。一般情况下，事务文件较小，可以进行内部排序，则时间复杂度为O(m*logm)。内部归并的时间复杂度为O(nm)，则总的内部处理时间为O(m*logmn)。 假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区大小为s（个记录），则整个批处理过程中读/写外存的次数为 ： 2m/s+(m+n)/s）,12-13,12.3 索引文件,基本术语 索引表：除了文件本身（称做数据区）之外，另建立的一张指示逻辑记录和物理记录之间一一对应关系的表。 索引项：索引表中的每一项。总是按

10、关键字（或逻辑记录号）顺序排列。 索引文件：包括文件数据区和索引表两大部分的文件。 索引顺序文件：数据区中的记录也按关键字顺序排列的文件。 索引非顺序文件：数据区中的记录不按关键字顺序排列的文件。 稠密索引：由于数据文件中记录不按关键字顺序排列，则必须对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。 非稠密索引：数据文件中的记录按关键字顺序有序，则可对一组记录建立一个索引项，这种索引表称为非稠密索引。,12-14,12.3 索引文件,例如，下图为两个索引表的例子。,12-15,12.3 索引文件,索引文件的存储 索引文件在存储器上分为两个区：索引区和数据区。索引区存放索引表，数据区存

11、放主文件。 索引文件的建立建立索引文件的过程： 按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的 待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件。,12-16,12.3 索引文件,检索操作检索分两步进行： 将外存上含有索引区的页块送人内存，查找所需记录的物理地址 将含有该记录的页块送人内存 注意： 索引表不大时，索引表可一次读入内存，在索引文件中检索只需两次访问外存：一次读索引，一次读记录。 由于索引表有序，对索引表的查找可用顺序查找或二分查找,12-17,12.3 索引文件,索引文件的修改 删除操作：删除一个记录时，仅需删去相应的索引项；

12、插入操作：插入一个记录时，应将记录置于数据区的末尾，同时再索引表中插入索引项； 更新操作：更新记录时，应将更新后的记录置于数据区末尾，同时修改索引表中相应的索引项。 多级索引： 查找表：对索引表建立的索引。通常最高可有四级索引：,数据文件,索引表,查找表,第二查找表,第三查找表,多级索引是静态索引，各级索引均为顺序表结构。其结构简单，但修改很不方便，每次修改都要重组索引。因此，当数据文件在使用过程中记录变动较多时，应采用动态索引。如二叉排序树（或二叉平衡树）、B-树以及键树。,12-18,12.4 ISAM和VSAM文件,12.4.1 ISAM文件 ISAM文件定义：索引顺序存取方法ISAM(

13、Indexed Sequential Access Method)是一种专为磁盘存取设计的文件组织方式。磁盘是以盘组、柱面和磁道三级地址存取的设备，可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。 磁道索引项： 基本索引项： 关键字：表示该磁道中最末一个记录的关键字（在此为最大关键字）。 指针：指示该磁道中第一个记录的位置。 溢出索引项： 关键字：表示该磁道溢出的记录的最大关键字。 指针：指示在溢出区中的第一个记录。,12-19,12.4 ISAM和VSAM文件,柱面索引项： 关键字：表示该柱面中最末一个记录的关键字（最大关键字）。 指针：指示该柱面上的磁道索引位置。 ISAM文件的组成 I

14、SAM文件由多级主索引、柱面索引、磁道索引和主文件组成。文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上。对同一柱面，则应按盘面的次序顺序存放。,12-20,12-21,12.4 ISAM和VSAM文件,在ISAM文件上检索记录时，先从主索引出发检索到相应的柱面索引，然后从柱面索引检索到记录所在柱面的磁道索引，最后从磁道索引检索到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至检索到为止；反之，若检索遍磁道而不存在此记录，则表明文件中无此记录。 ISAM文件中删除记录比较简单，只需作删除标记而不用移动记录或改变指针。当然应该周期性地把记录读入

15、内存重排整理ISAM文件，以尽量填满基本区而空出溢出区。,12-22,12.4 ISAM和VSAM文件,12.4.2 VSAM文件 VSAM（Virtual Storage Access Method）即虚拟存储存取方法。它使用户只需考虑控制区间等逻辑存储单位，而无需考虑其物理位置以及何时对外存储器进行读写操作，给用户使用文件提供了方便。 VSAM文件的结构由索引集、顺序集和数据集三部分组成。数据集存放文件的所有记录，顺序集和索引集构成一棵B+树是文件的索引部分。数据集中的一个结点称为控制区间（Control Interval）。,12-23,12.4 ISAM和VSAM文件,顺序集中的一个结

16、点，存放着若干相邻控制区间的索引项，每个索引项由控制区间中的最大关键字和指向该控制区间的指针组成。顺序集中的一个结点连同其下层所有控制区间形成的整体称作控制区域（Control Range）。顺序集中的结点之间用指针相链接，在它们上层的结点又以它们为基础形成索引，并逐级向上建立索引，形成B+树的非终端结点。,12-24,12.4 ISAM和VSAM文件,VSAM文件的结构示意图,12-25,12.4 ISAM和VSAM文件,对VSAM文件中记录的检索，既可从最高层的索引逐层往下按关键字进行检索，又可在顺序集中沿着指针链顺序检索。 VSAM文件没有专门的溢出区，但可以利用控制区间中的空隙或控制区域中的空控制区间来插入记录（即在B+树上插入记录）。而在VSAM文件中删除记录时，也需移动记录。 VSAM文件占有较多的存储空间，然而它具有许多优点，如动态地分配和释放存储空间，无需像ISAM文件那样定期重排文件，并能较快地执行插入操作和保持较高的检索效率。 VSAM文件通常作为组织大型索引顺序文件的标准形式。,12-26,12.4 I