数据结构-文件.ppt

* * 第十章 文件 基本概念 顺序文件 索引文件 ISAM文件和VSAM文件 散列文件（直接存取文件） 多关键字文件 基本概念 文件：是由大量性质相同的记录组成的集合。 （通常，存储在外存储器中。） 操作系统文件（系统文件）：仅是一维的连续的字符序列， 无结构、无解释。 数据库文件：是带有结构的记录的集合，这类记录是由一 个或多个数据项组成的集合。 （分为：单关键字文件、多关键字文件） 定长记录文件：文件中每个记录含有的信息长度相同。 不定长记录文件：文件中含有信息长度不等。 基本概念 记录的逻辑结构：是指记录在用户或应用程序员面 前呈现的方式，是用户对数据的表示和存取方式。 （它着眼于用户使用方便） 记录的物理结构：是数据在物理存储器上的存储方 式，是数据的物理表示和组织。（它着眼于存储空 间的提高和存取时间的减少） 基本概念 文件的操作：检索和修改 检索 （1）顺序存取：存取下一个逻辑记录 （2）直接存取：存取第i个记录 （3）按关键字存取：给定一个值，查询一个和一批关键字 与给定值相关的记录。 查询：（1）简单查询：查询关键字等于给定值的记录。 （2）区域查询：查询关键字属于某个区域的记录。 （3）函数查询：给定关键字的某个函数。 （4）布尔查询：将上述三种查询用布尔运算组合 起来的查询。 基本概念 修改 插入 删除 更新 文件的物理结构 文件在存储介质上的组织方式。 （1）顺序组织 （2）随机组织 （3）链组织 顺序文件 顺序文件是物理结构最简单的文件，也是数据处理历史上最早使用的文件结构。 顺序文件是记录按其在文件中的逻辑顺序依次进入而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序一致。 连续文件：若次序相继的两个物理记录在存储介质上的 存储位置是相邻的，则又称为连续文件。 串联文件：若物理记录之间的次序由指针相连表示，则 称为串联文件。 顺序文件 当需要对磁带顺序文件进行检索时，一般是采用顺序扫描的方式来检索满足查询条件的记录。例如，若要检索第i个记录，则必须先检索前面的i-1个记录。为了提高平均检索效率，可采用批量处理技术。如果将对文件的多个检索请求加以积累和排序，则形成一个称为待办文件（或事务文件）的文件。如果将被查询的文件称为主文件，则批量检索就是按照待办文件的要求成批地检索主文件。批量检索对于实时应用来说是不适宜的，因为实时查询要求响应时间快，而在很短的时间间隔内，积累的批处理文件规模太小，不能表现出它的优越性。 在磁带顺序文件中插入记录，只能加在文件的末尾，不能插在两个原有记录之间。 顺序文件 修改记录，即使在新旧记录等长的情况下，将新记录写在旧记录的位置上，一般不但不可能完全重合，甚至还会破坏邻近记录的信息。因此，修改一个磁带文件，需要用另一条磁带将原文件复制过来，在复制过程中进行插入、删除、修改记录的操作。为了提高效率，修改一个顺序文件，也采用成批处理技术。这种批量修改方式很适用于银行帐户结算管理系统。例如，可把一天的零星支取和存入分别作为记录收集在一起，构成为一个待办文件，在当天下班时再按照待办文件进行批量修改主文件（头天下班修改过的主文件）的工作，便得到一个新主文件。 顺序文件 顺序文件的基本优点是在连续存取时速度较快。例如，如果文件中的第i个记录刚被存取过，而下一个要存取的记录就是第i+1个记录，则此次存取将会很快完成。磁带是比较适用于这种应用的外存设备。存放于磁带上的文件也只能是顺序文件，这是由磁带的物理特性决定的。存放于磁盘上的文件，既可以是顺序文件，也可以是索引结构或其它结构类型的文件。 索引文件 顺序文件的查询速度很慢。采用索引文件可以提高检索效率。 索引用来表示关键字与相应记录的存储地址之间的对应关系。换言之，索引指出了记录在存储器中的存储地址。设记录Ri的关键字为Ki，Ri在外存中的存储地址为Ai，则（Ki，Ai）称为记录Ri的索引项。索引表（简称索引）是索引项的集合。如果文件中的每个记录都有一个索引项，则这样的索引称为稠密索引。如果多个记录只有一个索引项，则这样的索引称为非稠密索引。带有索引的文件称为索引文件。索引也称为目录。 索引文件 索引文件在外存（磁盘、磁鼓等）中可分为两个存储区：索引区和记录区（数据区）。索引表中的索引项顺序存放在索引区中，但为了便于检索，索引项一般按关键字的大小次序排列。文件中的记录按输入的先后次序存放到记录区；记录区按关键字大小次序排列的索引文件称为索引顺序文件。对于索引顺