数结 华中科技大学 计犷机学院(16) 200=g=
2001 -- 12 --31 华中科技大学 数据结构计算机学院(16)
第12章文件 内存不能永久性保存数据,以及容量有限,所以需要数据 以文件形式存放到外部存储器中 121文件的基本概念 文件:由大量性质相同的记录组成的集合 记录:文件中可存取的基本数据单位,它有若干个数据项组成。 数据项:最基本的不可再分的数据单位。数据项的名称称为记 录的域 关键字:能够区分文件中各记录的域。 主关键字—可以唯一地标识一个记录的关键字; 次关键字不能唯一地标识一个记录的关键字
第12章 文 件 内存不能永久性保存数据，以及容量有限，所以需要数据 以文件形式存放到外部存储器中。 12.1 文件的基本概念 文件：由大量性质相同的记录组成的集合。 记录：文件中可存取的基本数据单位，它有若干个数据项组成。 数据项：最基本的不可再分的数据单位。数据项的名称称为记 录的域。 关键字：能够区分文件中各记录的域。 主关键字-----可以唯一地标识一个记录的关键字； 次关键字-----不能唯一地标识一个记录的关键字
文件分类: 按记录类型划分: (1)流式文件:由一维的连续的字符(字节)序列组 成,无结构,无解释。如C源程序。此时的记录为单个字 符(字节)。 (2)记录文件:记录是由一个或多个数据项组成的集 合。如 db dbf文件。 按记录长度划分: (1)定长记录文件:文件中每个记录含有的信息长度 相同 (2)不定长记录文件:文件有含有长度不等的记录组成
文件分类： 按记录类型划分： （1） 流式文件：由一维的连续的字符（字节）序列组 成，无结构，无解释。如C源程序。此时的记录为单个字 符（字节）。 （2） 记录文件：记录是由一个或多个数据项组成的集 合。如 .db .dbf文件。 按记录长度划分： （1） 定长记录文件：文件中每个记录含有的信息长度 相同。 （2）不定长记录文件：文件有含有长度不等的记录组成
记录的逻辑结构和物理结构: 逻辑结构:呈现在用户和应用程序员面前的数据组织形式 是用户对数据的表示和存取方式。着眼于用户使用方便。 物理结构:数据在物理存储器上存储的方式,是数据的物理 表示和组织。应考虑提高存储空间的利用率和减少存取记录 的时间。 物理记录:是计算机用一条IO命令进行读写的基本数据单位 对固定的设备和操作系统,它的大小基本上是固定不变的 逻辑记录和物理记录的三种关系: (1)一个物理记录存放一个逻辑记录; 2)一个物理记录存放多个逻辑记录; (3)多个物理记录存放一个逻辑记录; 用户读写记录是对逻辑记录,而操作系统对物理记录
记录的逻辑结构和物理结构： 逻辑结构：呈现在用户和应用程序员面前的数据组织形式， 是用户对数据的表示和存取方式。着眼于用户使用方便。 物理结构：数据在物理存储器上存储的方式，是数据的物理 表示和组织。应考虑提高存储空间的利用率和减少存取记录 的时间。 物理记录：是计算机用一条I/O命令进行读写的基本数据单位。 对固定的设备和操作系统，它的大小基本上是固定不变的。 逻辑记录和物理记录的三种关系： （1）一个物理记录存放一个逻辑记录； （2）一个物理记录存放多个逻辑记录； （3）多个物理记录存放一个逻辑记录； 用户读写记录是对逻辑记录，而操作系统对物理记录
文件的操作:(1)检索;(2)修改 文件的检索一般有三种: (1)顺序存取:从当前位置开始,存取下一个逻辑记录; (2)直接存取:存取第i个逻辑记录; 以上两种存取方式都是根据记录的序号(即记录存入文 件时的序号)或记录的相对位置进行存取 (3)按关键字存取:给定一个值,查询一个或一批关键字与 给定值相关的记录。 对数据库文件的查询有四种: a)简单査询:査询关键字等于给定值的记录; (b)区域査询:查询关键字属于某个区域的记录;
文件的操作： （1）检索； （2）修改。 文件的检索一般有三种： （1）顺序存取：从当前位置开始，存取下一个逻辑记录； （2）直接存取：存取第i个逻辑记录； 以上两种存取方式都是根据记录的序号（即记录存入文 件时的序号）或记录的相对位置进行存取。 （3）按关键字存取：给定一个值，查询一个或一批关键字与 给定值相关的记录。 对数据库文件的查询有四种： （a） 简单查询：查询关键字等于给定值的记录； （b）区域查询：查询关键字属于某个区域的记录；
(c)函数查询:给定关键字的某个函数;例如查询平均分以 上的记录。 (d)布尔査询:以上三种査询用布尔运算组合起来的查询 例如查询总分600以上并且数学在100分以上,或总分在 平均分以下并且外语在98分以上的所有记录。 文件的修改包括: (1)插入一个记录;(2)删除一个记录;(3)更新一个记录 文件的操作有两种方式 1)实时:应答时间要求严格,要求在给定时间内完成 (2)批量 文件组织的三种基本形式: 1)顺序组织;(2)随机组织;(3)链组织
（c）函数查询：给定关键字的某个函数；例如查询平均分以 上的记录。 （d）布尔查询：以上三种查询用布尔运算组合起来的查询。 例如查询总分600以上并且数学在100分以上，或总分在 平均分以下并且外语在98分以上的所有记录。 文件的修改包括： (1) 插入一个记录；(2) 删除一个记录；(3) 更新一个记录。 文件的操作有两种方式： （1）实时：应答时间要求严格，要求在给定时间内完成。 （2）批量。 文件组织的三种基本形式： （1）顺序组织；（2）随机组织；（3）链组织
122顺序文件 顺序文件( Sequential File)是记录按其在文件中的逻辑顺序 依次进入存储介质而建立的,即顺序文件中物理记录和逻辑记 录的顺序是一致的。 如果次序相继的两个物理记录在存储介质上的存储位置是 相邻的,则又成连续文件 如果两个物理记录之间的次序有指针链表示,则称串联文 件 顺序文件是根据记录序号或记录的相对位置来进行存取的文件 组织方式,特点: (1)存取第个记录,必须搜索在它之前的-个记录; (2)插入新的记录只能在文件尾; (3)若要更新文件中的某个记录,必须将整个文件复制
12.2 顺序文件 顺序文件（Sequential File)是记录按其在文件中的逻辑顺序 依次进入存储介质而建立的，即顺序文件中物理记录和逻辑记 录的顺序是一致的。 如果次序相继的两个物理记录在存储介质上的存储位置是 相邻的，则又成连续文件。 如果两个物理记录之间的次序有指针链表示，则称串联文 件。 顺序文件是根据记录序号或记录的相对位置来进行存取的文件 组织方式，特点： （1）存取第i个记录，必须搜索在它之前的i-1个记录； （2）插入新的记录只能在文件尾； （3）若要更新文件中的某个记录，必须将整个文件复制
顺序文件的优点是连续存取速度快,在查找和修改都是成批处 理的情况下,以顺序文件为佳。 顺序文件的分类: (1)按关键字排列; (2)未按关键字排列,仅按先后次序。 顺序文件的操作: (1)顺序存取:从文件的第1个记录依次顺序存取,存取效率 很高。 2)随机存取:对指定的记录进行存取,但这种要求对顺序 文件来说,极不方便,存取效率很低 (3)按关键字存取:需从文件的第1个记录开始查找,一般情 况下,存取效率不高
顺序文件的优点是连续存取速度快，在查找和修改都是成批处 理的情况下，以顺序文件为佳。 顺序文件的分类： （1） 按关键字排列； （2） 未按关键字排列，仅按先后次序。 顺序文件的操作： （1）顺序存取：从文件的第1个记录依次顺序存取，存取效率 很高。 （2）随机存取：对指定的记录进行存取，但这种要求对顺序 文件来说，极不方便，存取效率很低。 （3）按关键字存取：需从文件的第1个记录开始查找，一般情 况下，存取效率不高
123索引文件 除文件自身(称作数据区)之外,另建立一张指示逻辑记 录和物理记录之间一一对应关系的表:索引表。这类包括文件 数据区和索引表两大部分的文件称为索引文件。 索引表的每一项称为索引项 不论主文件是否按关键字有序,索引表中的索引项总是按 关键字顺序排列。若数据区中的记录也按关键字顺序排列,则 称索引顺序文件,反之,称索引非顺序文件
12.3 索引文件 除文件自身（称作数据区）之外，另建立一张指示逻辑记 录和物理记录之间一一对应关系的表：索引表。这类包括文件 数据区和索引表两大部分的文件称为索引文件。 索引表的每一项称为索引项。 不论主文件是否按关键字有序，索引表中的索引项总是按 关键字顺序排列。若数据区中的记录也按关键字顺序排列，则 称索引顺序文件，反之，称索引非顺序文件
关键字物理记录号 物理记录号职工号姓名职务其它 02 103 10129张三教授 05 102 10205李四讲师 17 107 10302王红助教 29 101 10438 31 105 10531 38 104 10643 43 106 10717 47 110 10850 49 109 10949 50 108 11047 111156 (b)索引表 (a)文件数据区
物理记录号 职工号 姓名 职务 其它 101 29 张三 教授 。 102 05 李四 讲师 。 103 02 王红 助教 。 104 38 。 。 。 105 31 。 。 。 106 43 。 。 。 107 17 。 。 。 108 50 。 。 。 109 49 。 。 。 110 47 。 。 。 111 56 。 。 。 (a) 文件数据区 关键字 物理记录号 02 103 05 102 17 107 29 101 31 105 38 104 43 106 47 110 49 109 50 108 56 111 (b) 索引表