《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第10章 文件》由会员分享，可在线阅读，更多相关《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第10章 文件（23页珍藏版）》请在金锄头文库上搜索。
1、10.1 文件的基本概念 10.2 顺序文件 10.3 索引文件 10.4 散列文件 10.5 多关键字文件,第10章 文件,文件（Files）是大量记录的有序集合，它对应一个二维表，表的每一行为一个记录，每一列为一个数据项。一般称存储在内存中的记录集合称为表，而称存储在外存储器中的记录集合为文件。文件中的记录是按某一种确定的次序线性排列，所以文件的逻辑结构是线性结构。本章主要介绍文件的概念和几种基本的数据文件的构造方法及其使用讨论文件在外存储器中的表示及其操作的实现。,第10章 文件,1、文件的概念 文件是由大量性质相同的记录组成的集合；二者的区别在于线性表是把记录全部组织在内存储器中，而文
2、件则是把大量记录都组织在外存储器中。 2、文件分类 按照记录的类型，可以把文件分为操作系统文件和数据库文件两大类。 按照记录的长度特性，可以把文件分为定长记录文件和不定长记录文件。定长记录文件中每个记录含有的信息长度相同，而不定长记录文件中每个记录含有的信息长度不等。 按照记录中关键字的多少，可以把文件分为单关键字文件和多关键字文件。单关键字文件中的记录只有一个惟一标识记录的主关键字；而多关键字文件中的记录除了主关键字外，还含有一个或多个次关键字，记录中所有非关键字的数据项称作记录的属性。,10.1 文件的基本概念,3、逻辑结构和物理结构 逻辑结构是指记录在用户或应用程序员面前呈现的方式，是用
3、户对数据的表示和存取方式；用户所读写的记录是指逻辑记录。记录的物理结构是数据在物理存储器上存储的方式，是数据的物理表示和组织方式。一个物理记录可以存放一个或多个逻辑记录，多个物理记录可以表示一个逻辑记录。用户读写的是逻辑记录，检索其对应的物理记录是操作系统的职责。 文件组织方式（即物理结构）有顺序组织、随机组织和链式组织等基本方式。,4、文件的操作 一般的，文件的操作有检索、修改和排序三类 。检索的方式有三种：顺序检索；按记录号检索；按关键字检索。修改操作包括插入、删除和更新一个记录这三种操作。排序操作则是为了检索方便高效对文件中记录的重新有序整理。 另外，文件的操作也可以有实时和批处理两种不
4、同的方式。实时处理通常对应答时间要求严格，应在接收询问后立即完成相应的操作；而批处理则不同，可以根据需要对积累一段时间的记录进行成批处理。,顺序文件是把记录按建立文件时的逻辑顺序依次存放在外存储器中，文件中的物理记录顺序和逻辑记录顺序一致。若次序相继的两个物理记录在存储器上的存储位置是相邻的，则又称为连续文件；若物理记录之间的次序由指针链接，则称为串联文件。 顺序文件的优点是连续存取速度快，主要用于顺序存取和批量修改的情况。若对应答时间要求不严格时亦可进行直接存取。 在对顺序文件作修改时，可对原文件中的记录复制一遍，并在复制的过程中插入新的记录、跳过待删除的记录、或用修改过的新记录代替原记录。
5、为了修改方便起见，要求待修改文件按关键字有序（对非数据库文件可将逻辑记录号作为关键字）。 磁带是一种典型的顺序存取设备，存储在磁带上的文件就是顺序文件。对磁盘上的顺序文件进行修改时，若不增加记录的长度，也可在原文件上直接修改而不必复制文件。 对顺序文件进行顺序检索的方法类似于静态表的顺序检索，也可以对磁盘文件进行分块检索或二分法检索。,10.2 顺序文件,索引文件是指具有索引存储结构的文件。简单的文件包含一个主文件和一个索引表，主文件是原有数据文件的顺序存储或链接存储的文件，而索引表是在主文件的基础上建立的顺序表，索引表中的每个索引项同文件中的每个记录一一对应，每个索引项由对应记录的关键字和存
6、储该记录的首地址组成，而且无论主文件是否按关键字有序，索引表将组织成按关键字有序，即除了主文件（即数据文件）之外，再建立一张索引表来指示逻辑记录和物理记录之间的一一对应关系；索引表中的每一项称作索引项，由记录的关键字和记录的存放地址构成；把索引表和主文件总称为索引文件（Indexed File）。 在索引文件中，若主文件也按关键字升序排列，则构成的索引文件称作索引顺序文件；若主文件是无序的，则称所构造的索引文件为索引非顺序文件。索引文件只适用于直接存取的外存储器（如磁盘）。索引文件的存储分索引区和数据区来进行，索引区存放索引表，数据区存放主文件。在输入记录建立数据区的同时建立索引表，表中的索引
7、项按记录输入的先后次序排列；待全部记录输入完毕后再对索引表按关键字排序，排序后的索引表和主文件一起构成了索引文件，如图10.1所示。,10.3 索引文件,索引文件的检索，应先在索引表中检索。若在索引表中检索到关键字值等于给定值的索引项，则按索引项指示从外部存储器读取该记录；否则，说明待检索记录不存在无需访问外存储器。当主文件中记录数目很大时，可对索引表再次建立二级索引；检索时先在二级索引中找，再检索索引表，然后读取记录。索引表和二级索引表都是有序表，在内存储器中可用检索效率较高的方法如二分法检索方法进行检索。 多级索引是一种静态索引，为顺序表结构，虽然结构简单，但修改很不方便，每次修改都要重组
8、索引，所以，当主文件在使用过程中记录变动比较多时，应采用树表结构的动态索引，如二叉排序树、B-树、键树等，以便于插入、删除等。,ISAM（Indexed Sequential Access Method）即索引顺序存取方法，是一种专为磁盘存取设计的文件组织方式。如图10.2所示为存放在一个磁盘组上的ISAM文件。 在ISAM文件上检索记录时，先从主索引出发检索到相应的柱面索引，然后从柱面索引检索到记录所在柱面的磁道索引，最后从磁道索引检索到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直至检索到为止；反之，若检索遍磁道而不存在此记录，则表明文件中无此记录。 由于ISAM文件中记
9、录是按关键字顺序存放的，在插入一个记录时需要向后移动记录，并将同一磁道上的最后一个记录移至溢出区，同时修改磁道索引项。ISAM文件的插入和溢出处理如图10.3所示。 ISAM文件中删除记录比较简单，只需作删除标记而不用移动记录或改变指针。当然应该周期性地把记录读入内存重排整理ISAM文件，以尽量填满基本区而空出溢出区。,10.3.1 ISAM文件,VSAM（Virtual Storage Access Method）即虚拟存储存取方法。它使用户只需考虑控制区间等逻辑存储单位，而无需考虑其物理位置以及何时对外存储器进行读写操作，给用户使用文件提供了方便。 VSAM文件的结构由索引集、顺序集和数据
10、集三部分组成，如图10.4所示。数据集存放文件的所有记录，顺序集和索引集构成一棵B+树是文件的索引部分。数据集中的一个结点称为控制区间（Control Interval）。顺序集中的一个结点，存放着若干相邻控制区间的索引项，每个索引项由控制区间中的最大关键字和指向该控制区间的指针组成。顺序集中的一个结点连同其下层所有控制区间形成的整体称作控制区域（Control Range）。顺序集中的结点之间用指针相链接，在它们上层的结点又以它们为基础形成索引，并逐级向上建立索引，形成B+树的非终端结点。,10.3.2 VSAM文件,对VSAM文件中记录的检索，既可从最高层的索引逐层往下按关键字进行检索，又
11、可在顺序集中沿着指针链顺序检索。 VSAM文件没有专门的溢出区，但可以利用控制区间中的空隙或控制区域中的空控制区间来插入记录（即在B+树上插入记录）。而在VSAM文件中删除记录时，也需移动记录。 VSAM文件占有较多的存储空间，然而它具有许多优点，如动态地分配和释放存储空间，无需像ISAM文件那样定期重排文件，并能较快地执行插入操作和保持较高的检索效率。 VSAM文件通常作为组织大型索引顺序文件的标准形式。,散列文件（Hash File）也称作直接存取文件，它是利用哈希方法组织的数据文件；即根据某个哈希函数和一定的冲突消解策略而得到的存放在外存储器上的散列表。 磁盘上的文件的若干个记录组成一个
12、存储单位，在散列文件中这个存储单位称作桶。一个桶能存放的逻辑记录的总数称作桶的容量。假如桶的容量为m，即m个同义词的记录可以存放在同一地址的桶中，当第m+1个同义词记录出现时则发生溢出。处理溢出也可采用哈希表中的各种处理冲突的方法，但对散列文件主要是采用链地址法消解冲突。 当发生溢出时，需要将第m+1个同义词存放到另一个桶中，通常称作“溢出桶”；相应地把存放前m个同义词的桶称作“基桶”。溢出桶可以有多个，它们和基桶大小相同，相互之间用指针相链接。当在基桶中没有检索到待查记录时，就顺指针所指到溢出桶中去检索。 例如，某一个文件有个记录，其关键字分别为28，19，13，93，89，14，55，69
13、，8，9，16，21，33，81，62，l1，15，34，35，用除留余数法作哈希函数H（key）=key %7，桶的容量m=3，基本桶数=7，由此得到的散列文件如图10.5所示。,10.4 散列文件,在散列文件中检索时，先根据给定的关键字值k求得哈希地址即基桶号，然后将基桶的记录读入内存进行顺序检索，若找到关键字值为k的记录则检索成功；若基桶中虽无关键字值为k的记录但指针域非空，需要把溢出桶中的记录读入内存继续检索，直到检索成功或检索失败。若基桶内没有填满记录即虽有溢出桶但仍未找到关键字为k的记录或其指针域为空（即无溢出桶），则文件内不含有待检索记录，即检索失败。 在散列文件中，删除记录时仅
14、需对被删除记录作一个删除标记即可。 散列文件具有插入、删除方便，存取速度比索引文件要快；不需要索引区，节省存储空间等优点；但它也具有以下缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式只有简单询问；并且在经过多次的插入、删除之后，也可能造成溢出桶满而基桶内多数为被删除记录的不合理文件结构，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录，此时亦需对文件进行重新整理。,多关键字文件（Multiple Key File）的特点是，在对文件进行检索操作时不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。因此，对多关键字文件还需要建立一系列的次关键字索引。次
15、关键字索引和主关键字索引所不同的是，每个索引项应包含次关键字和具有同一次关键字的多个记录的主关键字或物理记录号。多重表文件和倒排文件是常见的两种多关键字文件的组织方法。 多重表文件（Multilist File）的特点是，记录按主关键字的顺序构成一个串联文件，并建立主关键字索引（称为主索引）；对每一个次关键字项建立次关键字索引（称为次索引），所有具有同一次关键字的记录构成一个链表。主索引为非稠密索引，一组记录建立一个索引项；次索引为稠密索引，每个记录建立一个索引项，每个索引项包括次关键字、头指针和链表长度。,10.5 多关键字文件,例如，图10.6所示为一个多重表文件。对工号非稠密索引分成三个
16、子链表，其索引如图10.6(b)所示，索引项中的主关键字为各组中关键字的最大值。职称和专业是两个次关键字项，其索引分别如图10.6(c)和(d)所示，具有相同次关键字值的记录链接在同一链表中。有了这些次关键字索引，根据关键字值找到链表头指针，然后从头指针出发可列出链表中所有记录。 在多重表文件中可以很容易地插入一个新记录是，只要修改指针，将记录插在链表的头指针之后即可。但是，要删去一个记录却很繁琐，需要在每个次关键字的链表中删去该记录。 倒排文件（inverted file）和多重表文件的区别在于次关键字索引的结构不同。倒排文件的次关键字索引称为倒排表，在倒排表的索引项中没有头指针和链长度，而是直接用一个项存放具有同一关键字的所有记录的物理记录号或主关键字值。如图10.7所示为上例中的倒排表。,在倒排文件中可以较快地检索记录，特别是在检索多个次关键字的情况时。在处理各种次关键字的查询时，只要在次关键字索引中检索出有关的指针集合，再对这些指针集合进行交、并、差等逻辑运算，就可求出符合查询条件的记录指针，然后按指针到外存去存取记录。 在插入和删除记录时，倒排表也
