数据结构第13章文件

《数据结构第13章文件》由会员分享，可在线阅读，更多相关《数据结构第13章文件（38页珍藏版）》请在金锄头文库上搜索。

1、第13章 文 件 本章小结13.1 文件的基本概念13.2 顺序文件13.4 哈希文件13.3 索引文件13.5 多关键字文件13.1 文件的基本概念13.1.1 什么是文件文件是性质相同的记录的集合。文件的数据量通常很大,它被放置在外存上。数据结构中所讨论的文件主要是数据库意义上的文件，而不是操作系统意义上的文件。操作系统中研究的文件是一维的无结构连续字符序列，数据库中所研究的文件是带有结构的记录集合，每个记录可由若干个数据项构成。 记录是文件中存取的基本单位，数据项是文件可使用的最小单位。数据项有时也称为字段。其值能惟一标识一个记录的数据项或数据项的组合称为主关键字项，其他不能惟一 标识一

2、个记录的数据项则称为次关键字项，主关键字项(或次关键字项)的值称为主关键字(或次关键字)。为讨论方便起见，我们仍不严格区分关键字项和关键字,即在不易混淆时，将主(或次)关键字项简称为主(或次)关键字，并且假定主关键字项只含一个数据项。 文件可以按照记录中关键字的多少，分成单关键字文件和多关键字文件。若文件中的记录只有一个惟一标识记录的主关键字，则称其为单关键字文件；若文件中的记录除了含有一个主关键字外，还含有若干个次关键字，则称为多关键字文件。文件又可分成定长文件和不定长文件。若文件中记录含有的信息长度相同，则称这类记录为定长记录，由这种定长记录组成的文件称做定长文件；若文件中记录含有的信息长

3、度不等，则称做不定长文件。 13.1.2 文件的逻辑结构及操作文件中各记录之间存在着逻辑关系，当一个文件的各个记录按照某种次序排列起来时(这种排列的次序可以是记录中关键字的大小，也可以是各个记录存入该文件的时间先后等等),各记录之间就自然地形成了一种线性关系。在这种次序下,文件中每个记录最多只有一个后继记录和一个前驱记录，而文件的第一个记录只有后继没有前驱，文件的最后一个记录只有前驱而没有后继。因此，文件可看成是一种线性结构。文件上的操作主要有两类：检索和维护。13.1.3 文件的存储结构文件的存储结构是指文件在外存上的组织方式。采用不同的组织方式就得到不同的存储结构。基本的组织方式有四种：顺

4、序组织、索引组织、哈希组织和链组织。文件组织的各种方式往往是这四种基本方式的结合。几种常用的文件组织方式：顺序文件、索引文件、哈希文件和多关键字文件。选择哪一种文件组织方式,取决于对文件中记录的使用方式和频繁程度、存取要求、外存的性质和容量。 13.2 顺序文件顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序跟物理顺序一致的文件。若顺序文件中的记录按其 主关键字有序,则称此顺序文件为顺序有序文件；否则称 为顺序无序文件。为了提高检索效率,常常将顺序文件组织成有序文件。顺序文件的结构特点：记录在文件中的排列顺序是由记录进入存储介质的次 序决定的，即文件物理结构中记录的排列顺序和文件的逻 辑结

5、构中记录的排列顺序一致。顺序文件的操作特点：(1)便于进行顺序存取；(2)不便于进行直接存取，为取第i个记录，必须先读出前i-1个记录，对于磁盘上的等长记录的连续文件可以进行折半查找； (3)插入新的记录只能加在文件的末尾； (4)删除记录时，只作标记； (5)更新记录必须生成新的文件。13.3 索引文件用索引的方法组织文件时，通常是在文件本身(称为主文件)之外，另外建立一张表，它指明逻辑记录和物理记录之间的一一对应关系，这张表就叫做索引表，它和主文件一起构成的文件称作索引文件。索引表中的每一项称作索引项，一般索引项都是由主关键字和该关键字所在记录的物理地址组成的。显然,索引表必须按主关键字有

6、序，而主文件本身则可以按主关键字有序或无序，前者称为索引顺序文件，后者称为索引非顺序文件。 对于索引非顺序文件，由于主文件中记录是无序的,则必须为每个记录建立一个索引项，这样建立的索引表称为稠密索引。对于索引顺序文件，由于主文件中记录按关键字有序，则可对一组记录建立一个索引项，例如,让文件中每个页块对应一个索引项，这种索引表称之为稀疏索引。通常可将索引非顺序文件简称为索引文件，本节只讨论这种文件。 索引文件在存储器上分为两个区：索引区和数据区，前者存 放索引表，后者存放主文件。在建立文件过程中，按输入记录 的先后次序建立数据区和索引表，这样的索引表其关键字是无 字的，待全部记录输入完毕后再对索

7、引表进行排序，排序后的 索引表和主文件一起就形成了索引文件。 14物 理 地 址 1 2 3 4 5学 号姓 名其 他物 理 地 址关 键 字物 理 地 址物 理 地 址关 键 字物 理 地 址 1李 明101110115王 平115211333张 萍123312458陈 强138413524马 伟144584索引文件的结构特点：(1) 索引文件由“主文件”和多级“索引”组成；(2) 索引中的每个记录由“关键字”和“指针”组成；(3) 通常，索引文件中的主文件是无序文件，索引是 (按关键字有序)的有序文件；(4) “索引”是在输入数据建立文件时自动生成。初建时的“静态索引”为无序文件，经过排序

8、后成为有序文件。索引文件的操作特点：(1) 检索方式为：直接存取和按关键字存取。“按关键字检索”将分两步进行：先查索引，然后根据索引中指针所指索取记录；(2) 插入记录时，“记录”插入在主文件的末尾，而相应的“索引项”必须插入在索引的合适位置上。因此,最好在建索引表时留有一定“空位”；(3) 删除记录时，仅需删除索引表中相应的索引项即可；(4) 更新记录时，应将更新后的记录插入在主文件的末尾，同时修改相应的索引项。有两种典型的索引顺序文件。13.2.1 ISAM文件ISAM(Index Sequential Access Method)(索引顺序存取方法)是一种专为磁盘存取设计的文件组织方法。

9、1. 文件的组织方式 主文件按柱面集中存放,同时建立三级索引：(1) 磁道索引(2) 柱面索引(3) 主索引磁道索引结构如下：基本索引项溢出索引项关键字 指针 关键字 指针2101024主 索 引r(14) r(21) r(38)r(41) r(57) r(63)r(72) r(85) r(99)溢 出 区磁 道 索 引r(514) 溢 出 区磁道索引 r(1024)一 个 柱 面.柱 面 索 引992101024T0T1T2T3T4T5R64柱面溢出区70811407081R140R130R138R68T1T2R63R72R75T0基 本 区R131R74R73R136R65磁道索引柱面C2

10、R70R81R79C2T0磁道索引R70R66R76在文件中插入记录插入64，74，7668767981操作的特点(1) 检索可有两种方式：顺序存取 依关键字最小至大顺序存取。按关键字存取 从主索引开始，到 柱面索引，到磁道索引，最后取 得记录，先后访问四次外存。 (2) 插入将记录插入在某个磁道的合适位置上；将该磁道上关键字 最大的记录移出到本柱面的溢出区中；修改本磁道的索引项( 包括基本索引项和溢出索引项)。 (3) 删除在被删记录当前存储位置上 作“删除标记”。文件重组在经过多次的插入和删除操作之后，大量的记录进入文件的“溢出区”，而“基本存储区”中出现很多已被删去的记录空间，此时的文件

11、结构很不合理。因此，对ISAM文件，需要周期地进行重整。13.3.2 VSAM文件VSAM是虚拟存储存取方法(Virtual Storage Access Method)的英文缩写。VSAM文件是一种采用虚拟存储存取方法的文件。VSAM文件的存储单位是控制区间和控制区域,这是一些逻辑存储单位，与柱面、磁道等实际存储单位并没有必然的联系。用户在存取VSAM文件的记录时，不需要考虑该记录的当前位置是在内存还是在外存，也不需要考虎何时执行对外存进行读写的命令。可见，这种文件较ISAM文件更方便用户使用。 1文件的结构 .索引集 B+树顺序集控制区域控制区间数据集2. 控制区间和控制区域控制区间：是用

12、户进行一次存取的逻辑单位，可看成是一个逻辑磁道。但它的实际大小和物理磁道无关。控制区域：由若干控制区间和它们的索引项组成，可看成是一个逻辑柱面。VSAM文件初建时，每个控制区间内的记录数不足额定数，并且有的控制区间内的记录数为零。顺序集本身是一个单链表，它包含文件的全部索引项，同时，顺序集中的每个结点即为B+树的叶子结点，索引集中的结点即为B+树的非叶结点。文件的操作检索：可进行顺序存取和按关键字存取；插入：按关键字大小插入在某个适当的控制区间中，当控制区间中的记录数超过文件规定的大小时，要“分裂”控制区间，必要时，还需要“分裂”控制区域；删除：必须“真实地”删除记录，因此要在控制区间内“移动

13、”记录。VSAM文件通常被作为大型索引顺序文件的标准组织方式。优点：动态地分配和释放空间, 不需要重组文件；能较快地实现对“后插入”的记录的检索；缺点：占有较多的存储空间,一般只能保持约75%的存储空间利用率。(因此,一般情况下,极少产生需要分裂控制区域的情况)13.4 哈希文件哈希文件也称为散列文件，是利用哈希存储方式组织的文件,亦称为直接存取文件。它类似于哈希表，即根据文件中关键字的特点，设计一个哈希函数和处理冲突的方法，将记录哈希到存储设备上。与哈希表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在哈希文件中， 这个存储单位叫做桶。假如一个桶能存放

14、m个记录，则当桶中已有m个同义词的记录时，存放第m+1个同义词会发生“溢出”。处理溢出虽可采用哈希表中处理冲突的各种方法，但对哈希文件而言，主要采用链地址法。当发生“溢出”时,需要将第m+1个同义词存放到另一个桶中，通常称此桶为“溢出桶”。相对地，称前m个同义词存放的桶为“基桶”。溢出桶和基桶大小相同，相互之间用指针链接。当在基桶中没有找到待查记录时，就沿着指针到所指溢出桶中进行查找，因此，希望同一哈希地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。 例如,某一文件有16个记录,其关键字集合为 23,5,26,1,10,18,27,12,7,9,4,19,6,16,33,2

15、4。桶的容量 m=3,桶数b=7。用除留余数法作哈希函数H(key)=key%7。给出 对应的哈希文件。 在哈希文件中进行查找时，首先根据给定值求出哈希桶地 址，将基桶的记录读入内存，进行顺序查找，若找到关键字等 于给定值的记录，则检索成功；否则，读入溢出桶的记录继续 进行查找。在哈希文件中删去一个记录，仅需对被删记录作删除标记 即可。优点：文件随机存放,记录不需进行排序；插 入、删除方便；存 取速度快；不需要索引区，节省存储空间。缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式 限于简单询问，并且在经过多次插入、删除后，也可能造成文 件结构不合理，需要重新组织文件。 13.5 多关键

16、字文件前面介绍的文件都是只含一个主关键字的文件。为了提高查找效率，还需要对被查询的次关键字建立相应的索引，这种包含有多个次关键字索引的文件称为多关键字文件。次关键字索引本身可以是顺序表，也可以是树表。下面讨论两种多关键字文件的组织方法。13.5.1 多重表文件多重表文件是将索引方法和链接方法相结合的一种组织方式，它对每个需要查询的次关键字建立一个索引，同时将具有相同次关键字的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字，作为索引表的一个索引项。通常多重表文件的主文件是一个顺序文件。 例如，教材中图13.8(a)是一个多重表文件的示例。主关键字是学号，次关键字是性别、民族和班号。设计对应的多重表文件。设计三个链接字段，分别将具有相同性别、民族和班号的记录链在一起,由此形成的性别、民族和班号索引见图13.8(b)、图13.8(c)和