数据结构学习12.ppt

第十二章 学习目标 熟悉各类文件的特点，构造方法以及如何实现检索，插入和删除等操作。 重点和难点 重点：了解各种文件的结构特点及其适用场合。　 知识点 顺序文件、索引文件、索引顺序文件、VSAM文件、散列文件、多关键字文件 12.1 有关文件的基本概念 文件(File) 是由大量性质相同的记录组成的集合，一般放在外存上。 记录 是数据项的集合，是可存取的数据的基本单位。 数据项 由一个或多个位或字节组成，是不可分割的数据最小单位。 定长记录文件 文件中每个记录含有的信息长度相等。 不定长文件 文件中含有信息长度不等的不定长记录。 单关键字文件 文件中的记录只有一个唯一标识记录的主关键字。 多关键字文件 文件中的记录除了含有一个主关键字外，还含有若干个次关键字。 记录的属性 记录中所有非关键字的数据项。 记录的逻辑结构 记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。 记录的物理结构 数据在物理存储器上存储的方式，是数据的物理表示和组织。 物理记录 计算机用一条I/0命令进行读写的基本数据单位（物理块）。 物理记录和逻辑记录之间可能存在下列三种关系： 一个物理记录存放一个逻辑记录； 一个物理记录包含多个逻辑记录； 多个物理记录表示一个逻辑记录。 文件的检索方式 顺序存取：存取下一个逻辑记录。 直接存取；存取第i个逻辑记录。 按关键字存取： 简单查询、区域查询、函数查询、布尔查询 文件的修改 记录的插入、删除、修改。 文件的物理结构 文件在外存上的组织方式。 顺序组织 随机组织 链组织 12.2 顺序文件 顺序文件 定义 记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即物理记录和逻辑记录的顺序是一致的。 分类 连续（顺序）文件 次序相继的两个物理记录在存储介质上的存储位置是相邻的。 串联（顺序）文件 物理记录之间的次序由指针相链表示。 特点 存取第i个记录，必须先有哪些信誉好的足球投注网站在它之前的i-1个记录。 新的记录只能加在文件末尾。 更新记录，必须将整个文件复制。 优点 连续存取的速度快，主要用于只进行顺序存取、批量修改的情况。 存取设备 磁带 适合于文件的数据量大、平时记录变化少、只作批量修改的情况。 磁盘 12.3 索引文件 引入原因 对于按关键字存取得记录结构，顺序查找和折半查找的速度很慢。为了避免大量与外存打交道，可以保存一个索引表来指示关键字与记录地址之间的对应关系。 索引文件 包括数据区和索引表两部分。 为按建立时，系统自动开辟索引区。按记录进入的顺序登记索引项。索引项指出该记录的物理地址。最后，索引表按关键字排序。 只能存储在磁盘存储设备上。 索引文件的检索 将索引表读入内存（若一个物理块可容纳一个索引表，则仅一次读入，否则需要多次读入）；查找索引表，确定记录的物理地址（索引表有序，可折半查找）； 根据物理地址，一次读取记录。 索引文件的修改 删除 仅删去相应的索引项。 插入 记录进入数据区末尾，索引项插入索引表中（或重新排序）。 更新 删除与插入的结合。 多级索引 记录数目很大，导致一个物理块容纳不了索引表。此时，查找索引表需要多次访问内存。 对索引表再建立一个索引。 最高可以有四级索引，此时检索需要访问外存5次。 12.4 ISAM文件和VSAM文件 ISAM文件（索引顺序存取法） 是一种专为磁盘存取而设计的文件组织方式。 由于磁盘是以盘组、柱面和磁道三级地址存取的设备，则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引。 文件的记录在同一盘组上存放时，应先集中放在一个柱面上，然后再顺序存放在相邻的柱面上，对同一柱面，则应按盘面的次序顺序存放。用这种方法建立起来的索引文件称为ISAM文件。 包括：索引区、数据基本区、数据溢出区。 ISAM文件的检索 查主索引（驻内存），将相应柱面索引（在其柱面上）调用内存。 查柱面索引，将磁道索引（一般放在第0道上）调入内存； 查磁道索引，将本磁道上的所有记录送入内存； 顺序对这一组记录查找。 ISAM文件的插入 定位应插入的磁道； 按关键字顺序插入新纪录，将同一磁道上最后一个记录移至溢出区； 同时修改磁道索引项。 ISAM文件的删除 找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。 ISAM文件的整理 经过多次的增删后，文件的结构可能变得很不合理。此时，大量得记录进入溢出区，而基本区中又浪费很多空间。因此，通常需要周期地整理ISAM文件。 把记录读入内存，重新排列，复制成一个新的ISAM文件，填满基本区而空出溢出区。 12.4.2 VSAM文件 VSAM（虚拟存储存取方法） 利用了操作系统的虚拟存储器的功能，给用户提供方便。 对用户来说，存储记录时不需要考虑记录的具体存储位置，