数据结构与算法分析第10章

1、第10章 文件管理和外排序 10.1 文件的基本概念 10.2 文件的分类 10.3 直接存取文件（散列文 件） 10.4 多关键字文件 10.5 文件的存储 10.6 外部排序 10.1 文件的基本概念 10.1.1 文件定义文件的定义是性质相同的记录的集合，它通常存储在外存（辅助存储器）上，本章以外存储器为主考虑。 在文件中常见的术语有：记录：是文件中存取的基本单位，数据项是文件可使用的最小单位。数据项：有时也称为字段，或者称为属性。主关键字项：其值能惟一标识一个记录的数据项或数据项的组合称为主关键字项。 次关键字项：其值不能惟一标识一个记录的数据项则称为次关键字项。10.1 文件的基本概

2、念主关键字（或次关键字）：主关键字项（或次关键字项）的值称为主关键字（或次关键字）。单关键字文件：若文件中的记录只有一个惟一标志记录的主关键字。多关键字文件：若文件中的记录只有一个惟一标志记录的主关键字外，还含有若干个次关键字。按照构成文件的记录结构的长度分为定长记录文件和不定长记录文件。文件中记录含有的信息长度相同，称为定长记录，由定长记录组成的文件称为定长文件。若文件中记录含有的信息长度不等，则称为不定长文件。 10.1 文件的基本概念10.1.2 文件逻辑结构及操作记录的逻辑结构是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式 对应不同结构的记录也分别称为物理记录和

3、逻辑记录，它们之间有以下关系：（1）一条物理记录存放一条逻辑记录。（2）一条物理记录存放多条逻辑记录（3）多个物理记录存储一条逻辑记录。 10.1 文件的基本概念中文件的检索有三种方式：（1）顺序存取：按记录号依次存取逻辑记录。（2）直接存取：按照记录号或记录的相对位置直接取得需要的记录。（3）按关键字存取：给定一个关键字的值，查询一个或椅披关键字与给定值相关的记录，一般有四种查询： a.简单查询：查询关键字等于给定值的记录。例如查询学号是“00001”的记录。 b.区域查询：查询关键字属于某个范围的的记录。例如查询成绩在80分以上的所有记录。 c.函数查询：给顶的关键字的值使函数成立的记录。

4、例如查询所有男生的记录。 d. 布尔查询：通过布尔运算组合起来的查询。例如查询男生中成绩在90分以上的2003届的所有记录。 10.2 文件的分类 10.2.1 顺序文件 记录按其在文件中的逻辑顺序依次存入存储介质所建立的文件。顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。其特点是：（1）存取第I个记录，必须先搜索第I-1个记录。（2）插入新的记录时只能加在文件的末尾。（3）若要更新文件中的某个记录，则必须将整个文件进行复制。顺序文件的优点是连续存取的速度快，因此主要用于只进行顺序存取、批量修改的情况。顺序文件的存储介质比较典型的是磁带。 10.2 文件的分类10.2.2

5、索引文件 索引文件是有索引区和文件数据区两部分组成，其中文件数据区按关键字有序的称为索引顺序文件；文件数据区中记录不按关键字顺序排列称为索引非顺序文件；索引非顺序文件通常是指索引文件。 数据区和索引表构成索引文件。 建立索引文件的主要目的是提高查询速度，对索引文件而言其检索步骤为：首先将外存上含有索引区的页块送入内存，查找所需记录的物理地址，然后在将该记录的页块送入内存。若索引表不大，则可将索引表一次读入内存，因此索引文件中进行检索只需两次访问外存：一次读索引，一次读记录。 10.2 文件的分类索引非顺序文件适合于随机存取，不适合于顺序存取。索引顺序文件既适合于随机存取，又适合于顺序存取；索引

6、顺序文件是稀疏索引，占用空间较少；而索引非顺序文件是稠密索引。 ISAM（索引顺序存取方法） VSAM VSAM文件有如下优点： 较高的查找效率，查找一个后插入记录和查找一个原有记录具有相同的速度；动态地分配和释放存储空间，而且不必对文件进行再组织。 10.3 直接存取文件（散列文件） 散列文件是利用散列存储方式组织的文件，亦称为直接存取文件 与散列表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶 假如一个桶能存放m个记录，则当桶中已有m个同义词的记录时，存放第m+1个同义词会发生“溢出” 散列文件的优点是：文件随机存放，

7、记录不需进行排序；插入、删除方便；存取速度快；不需要索引区，节省存储空间。散列文件的缺点是：不能进行顺序存取，只能按关键字随机存取，询问方式简单，大量增删后，需要重新组织文件。 10.4 多关键字文件 1、多重表文件 2、倒排文件优点：可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取；存储具有相对独立性。缺点：存取速度慢，同时不便于插入、删除。 10.5 文件的存储 文件的存储结构是指文件在外存上的组织形式。基本组织形式分为：顺序组织、索引组织、散列组织和链组织 考虑辅助存储器的主要原因是辅助存储器和主存储器相比主要有两个优点：(1) 辅助存储器存储的文件是永久的，也就是当

8、电源断电后，数据永久性地保存在辅助存储器中，而主存储器（RAM）中存储的内容会因断电而丢失；(2) 辅助存储器可以方便的把磁盘等存储介质拿到其它计算机上使用，为计算机之间的信息传递提供了方便，而主存储器则不能。10.5 文件的存储10.5.1 磁盘和磁带磁盘通常称为直接访问存储设备。磁盘是随机存取设备，磁盘中通常存储非顺序文件为主，磁盘的读取单位不是以位为单位，而是以扇区为单位。使用磁盘时主要有三个时间需要考虑：(1) 寻找时间：磁头从当前位置移到数据存放磁道位置后，所花的时间，或者叫做寻道时间。(2) 延迟时间：磁头从当前扇区移动到数据存放扇区位置时，所花的时间，或者叫做旋转时间。(3) 传

9、送时间：数据从磁盘读取数据，并将数据传送到内存的时间。 10.5 文件的存储磁带通常称为顺序存储设备。磁带是顺序存取设备，使用磁带时和磁盘不同，它只能顺序访问。磁带如果不正转或者反转，就不能从当前位置到达目标位置。磁带的存取单位是磁带长度，每一个存储单位是块，影响磁带的一个物理特性是磁带驱动器需要花费时间使磁带停下来，这就需要磁带的块间间隔，I/O磁头需要识别间隔，同时间隔也浪费大量空间。一般将多条记录组织到一个块中，一个块中的记录的个数称为块因子。 10.5 文件的存储磁带的另一个性能度量是数据的传送速度，块间间隔减少了数据的存储密度，提高传输的速率。磁带只适用于顺序访问，一般不能存储存取速

10、度要求比较高的数据，它价格比较便宜，通常用它来备份数据或归档。对于外存来说：磁带只适宜存储顺序文件，磁盘则适宜存储顺序、索引、散列和多关键字等随机存取文件。 10.6 外部排序 所谓外部排序就是利用内排序的方法，实现外存中的数据的排序，主要原因是内存的容量有限，数据量太大的时候无法一次完全加载内存，而借助辅助内存的方法处理排序的数据。在整个外部排序过程中，很关键的一点就是尽量减少磁盘的存取次数，可以通过缓冲区来实现。外部排序的最常用的方法是合并排序法。合并排序是对记录顺序地完成一系列扫描。在每一趟扫描中，使和并的子序列越来越大，最后形成一个有序的序列。10.6 外部排序合并排序（以二路合并为例）的基本步骤是：(1)先将N个数据看成N个长度为1的表，将相邻的表成对合并，得到长度为2的N/2个有序表；(2)进一步将相邻的有序表合并，得到长度为4的N/4个有序表；(3)重复（2）步，直到所有数据均合并成一个长度为N的一个有序表为止。每一次合并过程，称做一趟排序。在每一趟两两合并的内部排序的过程中，有可能出现两种情况（假设合并之前的有序表的长度为L）： (1) 表的长度刚好是L的双倍；(2)一趟合并时，剩下两个有序表，其中一个有序表的长度是L，另一个有序表的长度是小于L； (3)一趟合并时，剩下一个长度等于或小于L的有序表。 10.6 外