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