ds chap12 文件

《ds chap12 文件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十二章文件112.1有关文件的基本概念12.2顺序文件12.3索引文件12.4索引顺序文件12.5直接存取文件12.6多关键字文件212.1文件的基本概念3一、文件即为记录的集合，和“查找表”的差别在于，“文件”指的是存储在外存储器中的记录的集合。记录是文件中可以存取的数据的基本单位。4二、文件可按其中记录的类型不同而分成两类：其一为操作系统的文件，文件中的记录仅是一个字符组。由于操作系统中的文件仅是一维的连续字符序列，为了用户存取和加工的方便，将文件中的信息划分为若干组，其中每一组信息称作一个记录；5其二为数据库文件，文件中的记录带有结构，是数据项的集合。记录

2、是文件中可以存取的数据基本单位，数据项是文件中可以使用的数据最小单位。6三、记录中能识别不同记录的数据项被称为关键字，若该数据项能唯一识别一个记录，则称为主关键字，若能识别多个记录则称为次关键字。7四、文件的逻辑结构指的是呈现在用户面前的文件中记录之间的逻辑关系；文件的物理结构指的是文件中的逻辑记录在存储器中的组织方式。8记录的逻辑结构--记录对用户或应用程序员的呈现方式，是用户对数据的表示和存取方式。其设计着眼于用户的使用方便。记录的物理结构--记录在物理存储器的存储方式，是数据的物理表示和组织。其设计着眼于存取速度和空间利用率。两者的关系：①1:1一个物理记录

3、存放一个逻辑记录②1:M一个物理记录存放多个逻辑记录③M:1多个物理记录存放一个逻辑记录9五、文件的操作检索修改排序101．检索顺序存取：存取“当前记录的”下一个记录；直接存取：存取第i个记录；按关键字存取：存取其关键字等于给定值的记录。11对数据库文件可有四种查询方式：简单查询：=区域查询：in,>,<等函数查询：f(k)组合查询：and,or,not122．修改往文件中插入一个或一批记录；更新文件中某个记录的属性从文件中删除一个或一批记录；实时操作--直接执行，瞬间完成。如订票系统。批量操作--周期性地定时执行。如银行业务。13文件的操作方式可以实时处理或批量

4、处理3．排序14本章讨论文件的几种常见的物理结构。顺序文件索引文件索引顺序文件直接存取文件多关键字文件1512.2顺序文件16记录在文件中的排列顺序是由记录进入存储介质的次序决定的，即文件物理结构中记录的排列顺序和文件的逻辑结构中记录的排列顺序一致。结构特点：17串联文件：物理记录之间的顺序由指针相链。连续文件：次序相继的两个物理记录其存储位置相邻;顺序文件的具体组织形式有两种：18操作特点：1．便于顺序存取；2．不便于直接存取。为取第i个记录，必须先读出前i-1个记录，对于磁盘上的等长记录的连续文件可以进行折半查找；3．插入新的记录只能在文件末尾；4．删除记录时

5、，只作标记；5．更新记录必须生成新的文件。19顺序文件的插入、删除和更新操作一般采用批处理方式；为处理方便，构成有序文件，称作“主文件”；将所有操作构成“事务文件”（经过排序也成为有序文件）；所谓“批处理”，就是将这两个文件“合”为一个新的主文件。相当于归并两个有序表。20（1）对于事务文件中的每个操作首先要判别其“合法性”；（2）事务文件中可能存在多个操作是对主文件中同一个记录进行的。但有两点不同：21假设主文件中含有n个记录，事务文件中含有m个记录，则对事务文件进行排序的时间复杂度为O(mlogm)；内部归并的时间复杂度为O(m+n)，则总的内部处理的时间为O

6、(mlogm+n)；批处理的时间分析：22假设对外存进行一次读/写为s个记录，则整个批处理过程中读/写外存的次数为2（m/s+(m+n)/s）（其中s为对外存进行一次读/写的记录数）2312.3索引文件24一.结构特点1．索引文件由“主文件”和多级“索引”组成。2．索引中每个记录由“关键字”和“指针”组成。3．通常，索引文件中的主文件是无序文件，索引是(按关键字有序)的有序文件。4．“索引”是在输入数据建立文件时自动生成。初建时的“静态索引”为无序文件，经过排序后成为有序文件。25二.操作的特点１．检索方式为：直接存取和按关键字存取。“按关键字检索”将分

7、两步进行：先查索引，然后根据索引中指针所指索取记录。２．插入记录时，“记录”插入在主文件的末尾，而相应的“索引项”必须插入在索引的合适位置上。因此，最好在建索引表时留有一定“空位”。26３．删除记录时，仅需删除索引表中相应的索引项即可。４．更新记录时，应将更新后的记录插入在主文件的末尾，同时修改相应的索引项。27１．多级静态索引28主文件索引表查找表第二查找表第三查找表…...…...…...…...１．多级静态索引29对主文件中每个记录建立一个索引项：主关键字记录在主文件中的存储位置称作稠密索引，由这些索引项构成索引表；30从索引表建立的索引称查找表，其中每个索

8、引项为：最