《数据结构与算法分析(Java版） 教学课件 ppt 作者 第10章》由会员分享，可在线阅读，更多相关《数据结构与算法分析(Java版） 教学课件 ppt 作者 第10章（17页珍藏版）》请在金锄头文库上搜索。
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）若要更新文件中的某个记录，则必须将整个文件进行复制。 顺序文件的优点是连续存取的速度快，因此主要用于只进行顺序存取、批量修改的情况。顺序文件的存储介
5、质比较典型的是磁带。,10.2 文件的分类,10.2.2 索引文件 索引文件是有索引区和文件数据区两部分组成，其中文件数据区按关键字有序的称为索引顺序文件；文件数据区中记录不按关键字顺序排列称为索引非顺序文件；索引非顺序文件通常是指索引文件。 数据区和索引表构成索引文件。 建立索引文件的主要目的是提高查询速度，对索引文件而言其检索步骤为：首先将外存上含有索引区的页块送入内存，查找所需记录的物理地址，然后在将该记录的页块送入内存。若索引表不大，则可将索引表一次读入内存，因此索引文件中进行检索只需两次访问外存：一次读索引，一次读记录。,10.2 文件的分类,索引非顺序文件适合于随机存取，不适合于顺
6、序存取。索引顺序文件既适合于随机存取，又适合于顺序存取；索引顺序文件是稀疏索引，占用空间较少；而索引非顺序文件是稠密索引。 ISAM（索引顺序存取方法） VSAM VSAM文件有如下优点： 较高的查找效率，查找一个后插入记录和查找一个原有记录具有相同的速度； 动态地分配和释放存储空间，而且不必对文件进行再组织。,10.3 直接存取文件（散列文件）,散列文件是利用散列存储方式组织的文件，亦称为直接存取文件 与散列表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶 假如一个桶能存放m个记录，则当桶中已有m个同义词的记录时，存放第
7、m+1个同义词会发生“溢出” 散列文件的优点是：文件随机存放，记录不需进行排序；插入、删除方便；存取速度快；不需要索引区，节省存储空间。 散列文件的缺点是：不能进行顺序存取，只能按关键字随机存取，询问方式简单，大量增删后，需要重新组织文件。,10.4 多关键字文件,1、多重表文件 2、倒排文件 优点：可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取；存储具有相对独立性。 缺点：存取速度慢，同时不便于插入、删除。,10.5 文件的存储,文件的存储结构是指文件在外存上的组织形式。基本组织形式分为：顺序组织、索引组织、散列组织和链组织 考虑辅助存储器的主要原因是辅助存储器和主存储
8、器相比主要有两个优点： (1) 辅助存储器存储的文件是永久的，也就是当电源断电后，数据永久性地保存在辅助存储器中，而主存储器（RAM）中存储的内容会因断电而丢失； (2) 辅助存储器可以方便的把磁盘等存储介质拿到其它计算机上使用，为计算机之间的信息传递提供了方便，而主存储器则不能。,10.5 文件的存储,10.5.1 磁盘和磁带 磁盘通常称为直接访问存储设备。磁盘是随机存取设备，磁盘中通常存储非顺序文件为主，磁盘的读取单位不是以位为单位，而是以扇区为单位。使用磁盘时主要有三个时间需要考虑： (1) 寻找时间：磁头从当前位置移到数据存放磁道位置后，所花的时间，或者叫做寻道时间。 (2) 延迟时间
9、：磁头从当前扇区移动到数据存放扇区位置时，所花的时间，或者叫做旋转时间。 (3) 传送时间：数据从磁盘读取数据，并将数据传送到内存的时间。,10.5 文件的存储,磁带通常称为顺序存储设备。磁带是顺序存取设备，使用磁带时和磁盘不同，它只能顺序访问。磁带如果不正转或者反转，就不能从当前位置到达目标位置。 磁带的存取单位是磁带长度，每一个存储单位是块，影响磁带的一个物理特性是磁带驱动器需要花费时间使磁带停下来，这就需要磁带的块间间隔，I/O磁头需要识别间隔，同时间隔也浪费大量空间。一般将多条记录组织到一个块中，一个块中的记录的个数称为块因子。,10.5 文件的存储,磁带的另一个性能度量是数据的传送速
10、度，块间间隔减少了数据的存储密度，提高传输的速率。 磁带只适用于顺序访问，一般不能存储存取速度要求比较高的数据，它价格比较便宜，通常用它来备份数据或归档。 对于外存来说：磁带只适宜存储顺序文件，磁盘则适宜存储顺序、索引、散列和多关键字等随机存取文件。,10.6 外部排序,所谓外部排序就是利用内排序的方法，实现外存中的数据的排序，主要原因是内存的容量有限，数据量太大的时候无法一次完全加载内存，而借助辅助内存的方法处理排序的数据。在整个外部排序过程中，很关键的一点就是尽量减少磁盘的存取次数，可以通过缓冲区来实现。 外部排序的最常用的方法是合并排序法。 合并排序是对记录顺序地完成一系列扫描。在每一趟
11、扫描中，使和并的子序列越来越大，最后形成一个有序的序列。,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 外部排序,一种好的外部排序算法需要做好以下几个方面： (1)尽量减少初始顺串。 (2)在所有阶段尽可能把输入、处理和输出进行并行处理。 (3)使用尽可能的多的工作主存，以减少内外存交换次数，达到节约时间的目的，对外部排序而言，更快的CPU在运行时间方面影响不大。 (4)使用多个外存（最好是随机存储设备），使I/O处理具有更大的并行性，并允许顺序文件处理。,
