数据结构——文件.ppt

文件的应用背景，数据结构范畴的文件概念。文件的应用背景，数据结构范畴的文件概念。基于检索的文件的基本形式与特点。基于检索的文件的基本形式与特点。常用的文件方式和关键技术实现要点。常用的文件方式和关键技术实现要点。10.1.1 10.1.1 文件文件 文件（文件（filefile） 文件是性质相同、逻辑上相关的数据记录集合。文件是性质相同、逻辑上相关的数据记录集合。按按数据记录的长度是否确定而分为定长文件和不定长文件数据记录的长度是否确定而分为定长文件和不定长文件：定长文件定长文件：文件中所有记录含有的数据项个数相同。文件中所有记录含有的数据项个数相同。不定长文件：不定长文件：文件中记录含有的数据项个数不等。文件中记录含有的数据项个数不等。按文件实际用途可以分为操作系统文件和数据库文件按文件实际用途可以分为操作系统文件和数据库文件： 操作系统文件操作系统文件 无严格意义下的数据结构，只是作为记录的集合无严格意义下的数据结构，只是作为记录的集合，主要表现为一维无结构连续字符序列，记录之间既没有结构的，主要表现为一维无结构连续字符序列，记录之间既没有结构的解释也没有特性的解释；相应文件操作只有解释也没有特性的解释；相应文件操作只有“整体整体”操作即打开操作即打开或关闭文件、删除文件或复制文件等；以及或关闭文件、删除文件或复制文件等；以及“字节字节”操作即从文操作即从文件读取一个字节或将一个字节写到文件当中。件读取一个字节或将一个字节写到文件当中。 数据库文件数据库文件 各项记录之间具有严格的逻辑结构（例如基本的线各项记录之间具有严格的逻辑结构（例如基本的线性表结构、关系文件和面向对象文件结构等），同时每个记录也性表结构、关系文件和面向对象文件结构等），同时每个记录也有相应结构，即数据库记录由若干数据项构成。有相应结构，即数据库记录由若干数据项构成。数据库文件数据库文件：例：下例：下图是一个学生学籍文件，每个学生情况形成一个记录。每个图是一个学生学籍文件，每个学生情况形成一个记录。每个记录由学号、姓名、性别、籍贯、出生年月和住址记录由学号、姓名、性别、籍贯、出生年月和住址6 6个数据项组成。个数据项组成。定义定义“学号学号”是主关键字，是主关键字，“姓名姓名”、“性别性别”等是次关键字。等是次关键字。学号学号 姓名姓名 性别性别 籍贯籍贯 出生年月出生年月 住址住址 101 张宏张宏 男男 湖南湖南 1990.12 长沙长沙 102 李李焯焯 男男 广东广东 1991.5 广州广州 按按只有主关键字还是同时具有主关键字和次关键字而分为单关键只有主关键字还是同时具有主关键字和次关键字而分为单关键字文件或多关键字文件：字文件或多关键字文件：单关键字文件单关键字文件：记录中只有一个惟一标识记录的主关键字。记录中只有一个惟一标识记录的主关键字。多关键字文件多关键字文件：记录中除了含有一个主关键字外还含有若干个次记录中除了含有一个主关键字外还含有若干个次关键字。关键字。1 1、文件逻辑结构、文件逻辑结构作为存储在外存中的数据，文件是具有相同性质的记录集合，作为存储在外存中的数据，文件是具有相同性质的记录集合，其逻辑结构应当为集合。但在实际操作过程中，文件中各个记其逻辑结构应当为集合。但在实际操作过程中，文件中各个记录至少都是录至少都是“顺次顺次”进入计算机的，即其至少具有进入计算机的，即其至少具有“工作工作”顺顺序，在这种意义下，通常将文件看作一种线性表，或者说，文序，在这种意义下，通常将文件看作一种线性表，或者说，文件就是外存中的线性表。件就是外存中的线性表。注意区分注意区分文件中记录的文件中记录的“顺序顺序”（sequentialsequential）概念）概念和文件记和文件记录的录的“有序有序”（orderorder）概念）概念。2 2、文件存储结构、文件存储结构 存储结构是文件在物理存储介质（磁盘或磁带）上的组织方式，它决定了存储结构是文件在物理存储介质（磁盘或磁带）上的组织方式，它决定了文件信息在存储设备上的存储位置。文件信息在存储设备上的存储位置。 顺序文件顺序文件 顺序文件在逻辑上是将数据记录间的顺序作为相应线性表中元素顺序文件在逻辑上是将数据记录间的顺序作为相应线性表中元素的的“次序次序”关系，在存储上，这种顺序关系与物理存储顺序一致。关系，在存储上，这种顺序关系与物理存储顺序一致。 索引文件索引文件 在存储的文件之外，建立一个相对于主文件用于描述文件逻辑在存储的文件之外，建立一个相对于主文件用于描述文件逻辑记录与物理存储记录之间的一一关系（即文件的第记录与物理存储记录之间的一一关系（即文件的第i i号记录对应存储的物理号记录对应存储的物理地址）的索引表，此时，主文件和其索引表构成的二元组就称为索引文件。地址）的索引表，此时，主文件和其索引表构成的二元组就称为索引文件。 散列文件散列文件 散列文件也称为哈希（散列文件也称为哈希（hashhash）文件或者直接存取文件，其特点是）文件或者直接存取文件，其特点是使用散列存储方式组织文件。使用散列存储方式组织文件。 链式文件链式文件 链式文件中的连结点一般都比较大，同时也不定长。在文件存储链式文件中的连结点一般都比较大，同时也不定长。在文件存储方式中，链式文件通常都是结合索引文件一起使用，例如多关键字文件等。方式中，链式文件通常都是结合索引文件一起使用，例如多关键字文件等。3 3、文件基本操作、文件基本操作（1 1）文件检索）文件检索 文件检索就是在文件中查找满足给定条件的数据记录，实现途径可以是按文件检索就是在文件中查找满足给定条件的数据记录，实现途径可以是按照记录进入外存的时间顺序（逻辑序号）查找，也可以是按照记录的关键字照记录进入外存的时间顺序（逻辑序号）查找，也可以是按照记录的关键字大小查找。大小查找。 顺序检索顺序检索 通过逐次读取所有序号小于通过逐次读取所有序号小于i i的记录，定位所需要的第的记录，定位所需要的第i i号记录。号记录。 直接检索直接检索 不通过逐次读取所有序号小于不通过逐次读取所有序号小于i i的记录而直接定位第的记录而直接定位第i i号记录。直号记录。直接检索也称为随机检索。接检索也称为随机检索。 按关键字检索按关键字检索 定位关键字与给定关键字相同或相关的数据记录。定位关键字与给定关键字相同或相关的数据记录。 简单检索：询问单个关键字等于给定值的记录。简单检索：询问单个关键字等于给定值的记录。 范围检索：询问单个关键字属于某个范围内的所有记录。范围检索：询问单个关键字属于某个范围内的所有记录。 函数检索：规定单个关键字的某个函数，询问该函数的某个值。函数检索：规定单个关键字的某个函数，询问该函数的某个值。 布尔检索：以上三种询问用布尔运算布尔检索：以上三种询问用布尔运算( (与、或、非与、或、非) )组合起来的询问。例如查组合起来的询问。例如查询某成绩表中，查找表中询某成绩表中，查找表中( (数学成绩数学成绩90)and90)and（性别（性别=“=“女女”) )的记录。的记录。3 3、文件基本操作、文件基本操作（1 1）文件检索）文件检索2 2按操作的处理方式，可分为实时与批量处理两种不同的方式按操作的处理方式，可分为实时与批量处理两种不同的方式: :实时处理实时处理：响应时间要求严格，要求在接受询问后几秒种内完成检索和：响应时间要求严格，要求在接受询问后几秒种内完成检索和更新。更新。批量处理批量处理：响应时间要求宽松一些，不同的文件系统有不同的要求。：响应时间要求宽松一些，不同的文件系统有不同的要求。 例如一个银行的账户系统，需要满足实时检索要求，也例如一个银行的账户系统，需要满足实时检索要求，也可进行批量更新，即可以将一天的存款和提款记录在一个事可进行批量更新，即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进行批量处理。务文件上，在一天的营业之后再进行批量处理。3 3、文件基本操作、文件基本操作2 2（2 2）文件）文件更新更新 数据库文件的维护操作可以分为文件更新、故障恢复、安全性保护数据库文件的维护操作可以分为文件更新、故障恢复、安全性保护和完整性约束等基本情形和完整性约束等基本情形。文件更新操作文件更新操作类型：类型： 插入记录插入记录 在给定文件中插入给定的数据记录。此时是针对整条数据记在给定文件中插入给定的数据记录。此时是针对整条数据记录的操作。录的操作。 删除记录删除记录 在给定文件中删除其中一条或多条记录，此时也是针对整条在给定文件中删除其中一条或多条记录，此时也是针对整条记录的操作。记录的操作。 修改记录修改记录 在给定文件中修改其中一条记录的某个或多个数据项，此时在给定文件中修改其中一条记录的某个或多个数据项，此时是针对记录中部分数据项的操作。是针对记录中部分数据项的操作。10.2.1 10.2.1 顺序文件存储结构顺序文件存储结构顺序文件在存储介质中可以有两种不同的存储结构：连续结构顺序文件在存储介质中可以有两种不同的存储结构：连续结构和链式结构。和链式结构。连续结构连续结构是指逻辑上相邻的记录其存储位置是相邻的是指逻辑上相邻的记录其存储位置是相邻的; ;连续顺序文件连续顺序文件链式结构链式结构是指物理记录之间的次序由指针链来表示。是指物理记录之间的次序由指针链来表示。链接顺序文件链接顺序文件10.2.2 10.2.2 基于磁带基于磁带/ /磁盘的顺序存储磁盘的顺序存储1 1、基于顺序存储器的顺序文件基于顺序存储器的顺序文件存储在存储在顺序存储器（如磁带）顺序存储器（如磁带）上的文件，只能是顺序文件，这种文件只能上的文件，只能是顺序文件，这种文件只能进行进行“顺序存取顺序存取”和和“成批处理成批处理”。磁带磁带是一种典型的顺序存储设备是一种典型的顺序存储设备。磁带适合于存放文件数据量大、文件中的记录平时变化少、只作批量修改磁带适合于存放文件数据量大、文件中的记录平时变化少、只作批量修改的情况。的情况。存储在磁带上的顺序文件只能采用存储在磁带上的顺序文件只能采用顺序查找法顺序查找法，即顺序扫描文件，按记录，即顺序扫描文件，按记录的主关键字逐个查找。的主关键字逐个查找。优点：优点：连续存取时速度快，例如，如果文件中的第连续存取时速度快，例如，如果文件中的第i i个记录刚被存取过，个记录刚被存取过，而下一个要存取的记录就是第而下一个要存取的记录就是第i+1i+1个记录，则此次存取将会很快完成。批个记录，则此次存取将会很快完成。批处理效率高，节省存储空间。处理效率高，节省存储空间。缺点：缺点：实时性差，特别是更新操作要复制整个文件，所以一般不做随机处实时性差，特别是更新操作要复制整个文件，所以一般不做随机处理，如删除记录时只做标记处理。理，如删除记录时只做标记处理。10.2.2 10.2.2 基于磁带基于磁带/ /磁盘的顺序存储磁盘的顺序存储2 22 2、基于直接存储器的顺序文件基于直接存储器的顺序文件顺序文件也可以存放在顺序文件也可以存放在直接存取设备直接存取设备上，上，磁盘磁盘就是一个直接存就是一个直接存取的存储设备。取的存储设备。存放于磁盘上的文件，既可以是存放于磁盘上的文件，既可以是顺序文件顺序文件，也可以是，也可以是索引结构索引结构或其它结构类型的文件。或其它结构类型的文件。对存储在这类设备上的顺序文件不仅可以进行对存储在这类设备上的顺序文件不仅可以进行顺序存取顺序存取，还可，还可进行进行分块查找分块查找、二分查找二分查找等查找方法。等查找方法。 对磁盘等直接存取设备，还可以对顺序文件进行对磁盘等直接存取设备，还可以对顺序文件进行插值查找插值查找和和跳跳步查找步查找。10.3.1 10.3.1 索引概念及操作索引概念及操作 索引结构索引结构是当文件信息存放在若干不连续物理块中时，系统为该文件建立是当文件信息存放在若干不连续物理块中时，系统为该文件建立一个专用数据结构即一个专用数据结构即索引表索引表，需要存储的文件（主文件）和索引表构成的，需要存储的文件（主文件）和索引表构成的二元组就是索引