(课件)数据结构第十二章 文件.pptVIP

３．文件重组 在经过多次的插入和删除操作之 后，大量的记录进入文件的“溢出区”， 而“基本存储区”中出现很多已被删去 的记录空间，此时的文件结构很不合 理。因此，对ISAM文件， 需要周期 地进行重组。 ４．柱面索引的位置 ISAM文件占有多个柱面，其柱 面索引本身占有一个柱面，为使“磁头”的平均移动距离最小，柱面索引应设在数据文件所占全部柱面的中间位置上。 二、VSAM文件 VSAM(Vistual Storage Access Method) （虚拟存储存取方法） 文件是利用操作系统中提供的虚拟存储器的功能组织的文件，免除了用户为读/写记录时直接对外存进行的操作，对用户而言，文件只有控制区间和控制区域等逻辑存储单位。 … ... ... ... ... 索引集 B+树 顺序集 控制区域 控制区间 数据集 1．文件的结构 * 第十二章 文 件 12.1 有关文件的基本概念 12.2 顺 序 文 件 12.3 索 引 文 件 12.4 索 引 顺 序 文 件 12.5 直 接 存 取 文 件 12.6 多 关 键 字 文 件 一、文件即为记录的集合，和“查找 表”的差别在于，“文件”指的是存 储在外存储器中的记录的集合。 记录是文件中可以存取的数据的 基本单位。 12.1 有关文件的基本概念 二、文件可按其记录的类型不同而 分成两类： 其一为操作系统的文件，文件中的记录仅是一个字符组。由于操作系统中的文件仅是一维的连续字符序列，为了用户存取和加工的方便，将文件中的信息划分为若干组，其中每一组信息称作一个记录； 其二为数据库文件，文件中的记录带有结构，是数据项的集合。记录是文件中可以存取的数据基本单位，数据项是文件中可以使用的数据最小单位。 三、记录中能标识不同记录的数据项 被称为关键字，若该数据项能唯 一标识一个记录，则称为主关键 字，若能识别多个记录则称为次 关键字。 四、文件的逻辑结构指的是呈现在用 户面前的文件中记录之间的逻辑 关系；文件的物理结构指的是文 件中的逻辑记录在存储器中的组 织方式。 五、文件的操作： 检 索 修 改 1．检索 顺序存取：存取“当前记录的”下一个记录； 直接存取：存取第i个记录； 按关键字存取：存取其关键字等于给定值的记录。 2．修改 往文件中插入一个或一批记录； 更新文件中某个记录的属性。 从文件中删除一个或一批记录； 本章讨论文件的几种常见的 物理结构： 顺序文件 索引文件 索引顺序文件 直接存取文件 多关键字文件 结 构 特 点： 记录在文件中的排列顺序是由记 录进入存储介质的次序决定的， 即文 件物理结构中记录的排列顺序和文件 的逻辑结构中记录的排列顺序一致。 12.2 顺 序 文 件 顺序文件的具体组织形式有两种： 串联文件：物理记录之间的顺序由指 针相链。 连续文件：次序相继的两个物理记录 其存储位置相邻; 操作特点： 1．便于进行顺序存取； 2．不便于进行直接存取，为取第i个记录，必须先读出前i-1个记录，对于磁盘上的等长记录的连续文件可以进行折半查找； 3．插入新的记录只能加在文件的末尾； 4．删除记录时，只作标记； 5．更新记录必须生成新的文件。 顺序文件的插入、删除和更新操作在多数情况下都采用批处理方式。此时，为处理方便，通常将顺序文件作成有序文件，称作“主文件”，同时将所有的操作作成一个“事务文件”（经过排序也成为有序文件），所谓“批处理”，就是将这两个文件“合”为一个新的主文件。具体操作相当于“归并两个有序表”。 一、结构特点： 1．索引文件由“主文件”和多级“索引”组成； 2．索引中的每个记录由“关键字”和“指针”组成； 3．通常，索引文件中的主文件是无序文件，索引是 (按关键字有序)的有序文件； 4．“索引”是在输入数据建立文件时自动生成。初建时的“静态索引”为无序文件，经过排序后成为有序文件。 12.3 索 引 文 件 二、操作的特点： １．检索方式为：直接存取和按关键字存取。“按关键字检索”将分两步进行：先查索引，然后根据索引中指针所指索取记录； ２．插入记录时，“记录”插入在主文件的末尾，而相应