《《数据结构（C++版）（第二版）》-李根强-电子教案 第11章》由会员分享，可在线阅读，更多相关《《数据结构（C++版）（第二版）》-李根强-电子教案 第11章（21页珍藏版）》请在金锄头文库上搜索。
1、2019年5月24日,1,第11章 文件,本章学习内容,11.1 文件的基本概念,11.2 顺序文件,11.3 索引文件,11.4 ISAM文件和VSAM文件,11.5 散列文件,11.6 多关键字文件,2019年5月24日,2,11.1 文件的基本概念,文件是由大量性质相同的记录所构成的集合。,文件有不同的分类方式：,按记录类型分：操作系统文件和数据库文件。 按记录是否定长分：定长记录文件和不定长记录文件。 按查找关键字多少分：单关键文件和多关键文件。,记录有逻辑结构和存储结构之分。记录的逻辑结构，是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。记录的存储结构是指数据
2、在物理存储器中的存储形式，是数据的物理表示和组织。,2019年5月24日,3,文件和数据元素一样，也有逻辑结构和存储结构。文件的逻辑结构可以表现为记录的逻辑结构。文件的存储结构是指文件在物理存储器（磁盘或磁带）中的组织方式。文件可以有各种各样的组织方式，其基本方式有三种：顺序组织、随机组织和链组织。,对文件所施加的运算（操作）有两类：查找（检索）和更新（修改）。 文件的查找（检索）有三种方式：顺序查找、按记录号直接随机查找、按关键字直接随机查找。,文件的更新有三种方式：插入、删除、更新一条记录。,2019年5月24日,4,11.2 顺序文件,顺序文件是指记录按其在文件中的逻辑顺序依次存放到外部
3、介质上的文件。也就是说，顺序文件的物理记录顺序和逻辑记录顺序一致。若次序相继的两个物理记录在存储器中位置是相邻的，则称为连续文件；若物理记录之间的次序由指针相链表示，则称为串链文件。,顺序文件是根据记录的序号或记录的相对位置进行存取的文件组织方式。它的特点是： (1) 存取第K个记录必须先搜索在它之前的K-1个记录。 (2) 插入新的记录时只能在文件末尾插入。 (3) 若要更新文件中的某个记录，则必须将该文件复制。,由于顺序文件的优点是连续存取速度快，因此主要用于顺序存取、批量修改的情况。 磁带是一种典型的顺序存取设备，存储在磁带上的文件就是顺序文件。但磁带目前很 少使用，使用的顺序文件多为磁
4、盘顺序文件。对顺序文件可以向顺序表一样，进行顺序查找、分块查找或折半查找（文件有序）。,2019年5月24日,5,11.3 索引文件,除了文件（主文件）本身外，另外建立一张指示逻辑记录与物理记录之间一一对应关系的表（索引表）。这种包含主文件数据和索引表两大部分的文件称为索引文件。,索引表中的每一项称为索引项，索引项由记录的关键字与记录的存放地址构成。索引文件是按关键字有序排列的，若主文件也按关键字有序排列，这样的索引文件称为索引顺序文件；若主文件是无序的，这样的索引文件为索引非顺序文件。,索引表是由系统程序自动生成的。在输入记录的同时建立一个索引表，表中的索引项按记录输入的先后次序排列，待全部
5、记录输入完毕再对索引表进行排序。,索引文件的查找方式为直接查找或按关键字查找，和前面介绍的分块查找类似，但必须分两步走：首先在索引表中查找，若找到则再到主文件中查找；否则主文件中不存在该记录，也就不要访问外存了。,2019年5月24日,6,索引表是有序表，可以用快速的折半查找来实现，而主文件为索引顺序文件时，也可以用折半查找实现，主文件为索引非顺序文件时，只能用顺序查找来实现。,当一个文件很大时，索引表也很大，这时可以对索引表再建立一个索引，称为二级索引。更大的索引表可以建立多级索引。,在图11-1中，（a）为主表，(b)为一级索引表，(c)为二级索引表。,但图11-1中的多级索引是一种静态索
6、引，为顺序表结构。虽然结构简单，但修改很不方便，所以当主文件在使用过程中变化比较大时，应采用树表结构的动态索引，如二叉排序树、B树、键树等，以便于插入、删除。,2019年5月24日,7,(a)主表 (b)索引表 (c)二级索引表,图11-1 索引表文件示例,2019年5月24日,8,11.4 ISAM文件和VSAM文件,11.4.1 ISAM文件,ISAM（Indexed Sequential Access Method）索引顺序存取方法的缩写，它是一种专为磁盘存取设计的文件组织方式。由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面、磁道三级索引。,文件的记
7、录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，对同一柱面，则应按盘面的次序顺序存放。例如图11-2为存放在一个磁盘组上的ISAM文件，每个柱面建立一个磁道索引，每个磁道索引项由两部分组成：基本索引项和溢出索引项。每一部分都包含关键字和指针两项，前者表示该磁道中最末一个记录的关键字（最大关键字），后者指示该磁道中第一个记录的位置，柱面索引的每一个索引项也由关键字和指针两项组成，前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上的磁道索引位置。,2019年5月24日,9,在ISAM文件上检索记录时，先从主索引出发找到相应的柱面索引，再从柱面索引找到记
8、录所在柱面的磁道索引，最后从磁道索引找到记录所在磁道的第一个记录的位置，由此出发在该磁道上进行顺序查找直到找到为止；反之，若找遍该磁道而不存在此记录，则表明该文件中无此记录。,例如，在图11-2中，查找关键字21时，先找到主索引中620，再找到柱面索引164，最后找到磁道索引50，最后顺序查找到R21，查找成功。若查找关键字48，先找到主索引中620，再找到柱面索引164，最后找到磁道索引50，最后顺序查找到R50，无R48，查找不成功。,2019年5月24日,10,图11-2 ISAM文件结构,2019年5月24日,11,从图11-2可以看到，每个柱面上还开辟有一个溢出区，这是为插入记录所设
9、置的。由于ISAM文件中记录是按关键字顺序存放的，则在插入记录时需移动记录并将同一磁道上最末一个记录移到溢出区，同时修改磁道索引项。通常在文件中可集中设置一个溢出区，或在每个柱面分别设置一个溢出区，或在柱面溢出区满后再使用公共溢出区。,ISAM文件中删除记录比插入记录简单，只要找到待删除的记录，在存储位置上作删除标记而无需移动记录或改变指针。则在经过多次的增删后，文件的结构可能变得很不合理，这时应将记录读入内存重排，进行ISAM文件的整理。,2019年5月24日,12,11.4.2 VSAM文件,VSAM（Virtual Storage Access Method）虚拟存储存取方法的缩写。这种
10、存取方法利用了操作系统的虚拟存储器的功能，用户无需了解文件的具体单位，给用户使用文件提供方便。,VSAM文件由三部分组成：索引集、顺序集和数据集。数据集存放文件的所有记录，顺序集和索引集一起构成一棵B+树，为文件的索引部分。数据集中的一个结点称为控制区间，它由一组连续的存储单元组成，是一个I/O操作的基本单位。一个文件上的每个控制区的大小相同，含有一个或多个按关键字递增有序排列的记录并带有一定的控制信息（如记录长度、区间中的记录数等）。顺序集中的一个结点用于存放若干相邻控制区间的索引项（含有控制区间中的最大关键字和指向控制区间的指针组成），该结点连同其对应的下层所控制区间形成一个整体，称为控制
11、区域。顺序集中的结点相互之间用指针相链，在他们上一层的结点又以他们为基础形成索引，并逐级向上建立索引，形成B+树的非终端结点。,2019年5月24日,13,对VSAM文件中记录的检索，既可以从最高层的索引逐层往下按关键字进行查找，又可以在顺序集中沿着指针链顺序查找。,VSAM文件没有专门的溢出区，但可以利用控制区间中的空隙或控制区域中的空控制区域来插入记录（B+树上插入）。在控制区间中插入记录时，为保证区间内记录关键字的有序，需移动记录。而当区间中记录已满、再要插入记录时，区间将分裂。而在VSAM文件中删除记录时，也需要移动记录。,VSAM文件占有较多的存储空间，存储空间的利用率也只能保持75
12、%左右。但它的优点是：动态分配和释放存储空间，无需象ISAM文件那样定期重组文件，并能较快地对插入的记录进行查找和插入。,2019年5月24日,14,11.5 散列文件,散列文件是指利用哈希(Hash)函数进行组织的文件。它实际上是一个根据某个哈希函数和一定的处理冲突方法而得到的、存放在外存上的散列表。,与哈希表不同的是，对于文件而言，磁盘上的文件记录通常是成组存放的。若干个记录组成一个存储单位，在散列文件中这个存储单位叫作桶。一个桶能存放的逻辑记录的总数称为桶的容量。假设一个桶能存放m个记录，即m个同义词的记录可以保存到同一地址的桶中，第m+1个同义词出现时则发生“溢出”。处理溢出也采用哈希
13、表中处理冲突的各种方法；但对散列文件，主要采用链地址法。,当发生“溢出”时，需要将第m+1个同义词存放到另一个桶中，通常称此桶为“溢出桶”；相对地，称前m个同义词存放的桶为“基桶”。溢出桶可以有多个，它们和基桶大小相同，相互之间用指针链接。,2019年5月24日,15,若要在散列文件中进行查找，先根据散列函数的地址找到对应的基桶，在基桶中查找；若找到，则查找成功；若找不到，则进入溢出桶中进行查找，若找到，查找成功，否则查找失败。,若要在散列文件中插入记录，先根据散列函数的地址找到对应的基桶，有空间则直接插入，否则在它所对应的溢出桶中插入。,例如，给定记录关键字为19，13，23，1，68，20
14、，84，28，55，14，10，89，93，69，16，11，33，35。用除留余数法给定哈希函数H(key)=key%7。桶的容量m=3，基本桶数=7，由此得到的散列文件见图11-3。,2019年5月24日,16,图11-3 散列文件示例,散列文件的优点：插入、删除记录方便，存取速度比索引文件快，不需要索引区，节省存储空间。,散列文件的缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式只有简单询问；并且在经过多次插入、删除之后，也可能造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时亦需重组文件。,2019年5月24日,17,11.6 多关键字文件,多关键字文件的特点是，在
15、对文件进行检索操作时，不仅要对主关键字进行简单询问，还要对次关键字进行其它类型的询问检索。因此，对多关键字文件，还要建立一系列的次关键索引。次关键字索引和主关键索引所不同的是，每个索引项应包含次关键字、具有同一次关键字的多个记录的主关键字或物理记录号。下面将讨论多关键字文件的两种组织方法。,11.6.1 多重表文件,多重表文件的特点是：记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引（主索引）；对每一个次关键字建立次关键字索引（次索引），所有具有同一次关键字的记录构成一个链表。主索引为非稠密索引（一组记录建立一个索引项），次索引为稠密索引（一个记录建立一个索引项）。每个索引项包含次关
16、键字、头指针和链表长度。,例如，图11-4所示就是一个多重表文件。其中，编号为主关键字，记录按编号顺序链接。对编号分稠密索引，分成3个链表，其索引如图11-4(b)所示，索引项中的主关键字为各组中的最大值。部门、职称为两个次关键字，它们的索引如图11-4(c)、11-4(d)所示。具有相同次关键字的记录链接在同一链表中。,2019年5月24日,18,(a)数据文件,(b)主关键字索引 (c)部门索引 (d)职称索引,图11-4 多重表文件示例,2019年5月24日,19,在多重表中进行查找很方便，根据关键字值找到链表的头指针，然后从头指针出发可以找出链表中所有记录。例如，要查找计算机系的教授，可以从部门索引表找到计算机系的头指针和链表长度，分别为1和4，从第1个记录开始，按链表找到第3个记录，再找到第6个即可。若找遍整个链表都没有符合要求的记录，则查找失败。,在多重表文件中插入一条记录很容易，只要修改指针，将记录插在链表的头指针之后。但是，要删除一条记录却很繁琐，需在每个次关键字的链表中删去该记录。,201
