搜索
第7章文件与外排序数据结构与算法数据结构与算法数据结构与算法数据结构与算法DataStructruesandAlgorithmsg张岩张岩海量数据计算研究中心哈工大计算机科学与技术学院张岩Slide7-12013/12/112013/12/112013/12/112013/12/11哈工大计算机科学与技术学院第第77章章文件与外部排序文件与外部排序第第77章章文件与外部排序文件与外部排序2013/12/11Slide7-2第7章文件与外排序学习目标学习目标掌握文件的相关概念；文件的各种组织方法及特点；查询、更新操作及其算法。更新操作及其算法。掌握外部排序的一般过程，熟练掌握适合外存特点的归并排序的相关技术。序的相关技术。哈工大计算机科学与技术学院张岩Slide7-32013/12/11第7章文件与外排序本章主要内容本章主要内容本章主要内容本章主要内容7.1文件及文件操作7.2顺序文件7.3索引文件7.4ISAM和VSAM文件7.5直接存取文件（散列文件）7.5直接存取文件（散列文件）7.6多关键字文件7.7磁盘文件的归并排序7.7磁盘文件的归并排序7.8磁带文件的归并排序本章小结哈工大计算机科学与技术学院张岩Slide7-42013/12/11第7章文件与外排序7.17.1文件及文件操作文件及文件操作7.17.1文件及文件操作文件及文件操作相关概念文件（FILE）是性质相同的记录组成的集合。习惯上称存储文件（FILE）是性质相同的记录组成的集合。习惯上称存储在主存储器（内存储器）中的记录集合为表，称存储在二级存储器（外存储器）中的记录集合为文件。存储器（外存储器）中的记录集合为文件数据项：最基本的不可分的数据单位，是文件中可使用的数据的最小单位。属性记录中所有非关键字的数据项，称为记录的属性。属性：记录中所有非关键字的数据项，称为记录的属性。关键字、主关键字、次关键字记录学号姓名性别年龄数学语文物理其它A003张三男18908080B008李四女17909080C009王五女19897093D010陈中男19667768E011孙二男18918878哈工大计算机科学与技术学院张岩Slide7-52013/12/11E011孙二男18918878F012林森女20605967第7章文件与外排序7.17.1文件及文件操作文件及文件操作7.17.1文件及文件操作文件及文件操作文件的分类按记录的类型不同可分成：按记录的类型不同可分成：①操作系统的文件：操作系统中的文件仅是一维的连续的字符序列，无结构、无解释。②数据库文件：数据库中的文件是带有结构的记录的集合②数据库文件：数据库中的文件是带有结构的记录的集合。这类记录是由一个或多个数据项组成的集合，它也是文件中可存取的数据的基本单位。件中可存取的数据的基本单位。按记录中关键字的多少，数据库文件可分成：①单关键字文件：文件中的记录只有一个唯一标识记录的①单关键字文件：文件中的记录只有一个唯一标识记录的主关键字。②多关键字文件：文件中的记录除了含有一个主关键字外，还含有若干个次关键字。，还含有若干个次关键字。按记录含有信息的长度不同可分成：①定长记录文件：文件中每个记录含有的信息长度相同。哈工大计算机科学与技术学院张岩Slide7-62013/12/11①定长记录文件：文件中每个记录含有的信息长度相同。②不定长记录文件：文件中每个记录含有的信息长度不等第7章文件与外排序7.17.1文件及文件操作文件及文件操作7.17.1文件及文件操作文件及文件操作文件的逻辑结构和物理结构逻辑结构是呈现在用户或应用程序员的记录间的逻辑关系逻辑结构：是呈现在用户或应用程序员的记录间的逻辑关系，是用户对数据的表示和存取方式。着眼于用户使用方便。物理结构是数据在物理存储器上存储的方式，是数据的物物理结构：是数据在物理存储器上存储的方式，是数据的物理表示和组织。着眼于提高存储空间的利用率和减少存取记录的时间。录的时间。物理记录和逻辑记录之间可能存在下列3种关系：①一个物理记录存放一个逻辑记录；①一个物理记录存放一个逻辑记录；②一个物理记录包含多个逻辑记录；③多个物理记录表示一个逻辑记录。哈工大计算机科学与技术学院张岩Slide7-72013/12/11第7章文件与外排序7.17.1文件及文件操作文件及文件操作7.17.1文件及文件操作文件及文件操作文件的操作（运算）文件的检索：文件的检索：①顺序存取：存取下一个逻辑记录。②直接存取：存取第i个逻辑记录。②直接存取：存取第i个逻辑记录。①和②两种存取方式都是根据记录序号(即记录存入文件时的顺序编号)或记录的相对位置进行存取的。时的顺序编号)或记录的相对位置进行存取的。③按关键字存取：给定一个值，查询一个或一批关键字与给定值相关的记录。对数据库文件可以有如下4种查询方式给定值相关的记录。对数据库文件可以有如下4种查询方式：1.简单询问：查询关键字等于给定值的记录。1.简单询问：查询关键字等于给定值的记录。2.区域询问：查询关键字属某个区域内的记录。3.函数询问：给定关键字的某个函数。哈工大计算机科学与技术学院张岩Slide7-82013/12/113.函数询问：给定关键字的某个函数。4.布尔询问：以上3种询问用布尔运算组合起来的询问第7章文件与外排序7.17.1文件及文件操作文件及文件操作7.17.1文件及文件操作文件及文件操作文件的操作（运算）文件的修改：文件的修改：文件的修改包括插入一个记录、删除一个记录和更新一个记录3种操作。记录3种操作。文件的操作方式可以有实时和批量两种不同方式。通常实时处理对应答时可以有实时和批量两种不同方式。通常实时处理对应答时间要求严格，应在接受询问之后几秒钟内完成检索和修改，而批量的处理则不然。，而批量的处理则不然。例如，银行的帐户系统需实时检索，但可进行批量修改，即可以将一天的存款和提款记录在一个事务文件上，在一即可以将一天的存款和提款记录在一个事务文件上，在一天的营业之后再进行批量处理。文件的组织方式哈工大计算机科学与技术学院张岩Slide7-92013/12/11顺序方式、索引方式、散列方式、链接方式第7章文件与外排序7.27.2顺序文件顺序文件7.27.2顺序文件顺序文件概念：顺序文件（SequentialFile）：是记录按其在文件中的逻辑顺序文件（SequentialFile）：是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。连续文件：次序相继的两个物理记录在存储介质上的存储位置是相邻的顺序文件。串联文件：物理记录之间的次序由指针相连表示的顺序文件串联文件：物理记录之间的次序由指针相连表示的顺序文件特点：顺序文件是根据记录的序号或记录的相对位置来进行存取的顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。它的特点是：①存取第i个记录，必须先搜索在它之前的i-1个记录。①存取第i个记录，必须先搜索在它之前的i-1个记录。②插入新的记录时只能加在文件的末尾。③若要更新文件中的某个记录，则必须将整个文件进行复哈工大计算机科学与技术学院张岩Slide7-102013/12/11③若要更新文件中的某个记录，则必须将整个文件进行复制。第7章文件与外排序7.27.2顺序文件顺序文件7.27.2顺序文件顺序文件磁带上顺序文件的批处理主文件：待修改的原始文件。主文件：待修改的原始文件。事务文件：所有的修改请求集中构成的一个文件。磁带文件的批处理过程：终端磁带文件的批处理过程：首先对事务文件进行排序；然后将主文件和事务文件归并成一个新的主文件。事务文件排序然后将主文件和事务文件归并成一个新的主文件有序的事务文件主文件新主文件其中，主文件、事务文件和新的主文磁带文件批处理示意图件分别存放中一台磁带上。主文件按关键字自小至大（或自大至小）顺序有序，自大至小）顺序有序，事务文件必须和主文件有相同的有序关系。主文件新主文件文件修改程序哈工大计算机科学与技术学院张岩Slide7-112013/12/11的有序关系。事务文件磁带文件操作实例第7章文件与外排序7.27.2顺序文件顺序文件终端7.27.2顺序文件顺序文件磁带上顺序文件的批处理—归并事务文件排序在归并的过程中，顺序读出主文件与事排序有序的事务文件主文件新主文件在归并的过程中，顺序读出主文件与事务文件中的记录，比较它们的关键字并分别进行处理。对于关键字不匹配的主文件中的记录，则直接将其写入新主文件中。“更改新主文件•磁带文件批处理示意图记录，则直接将其写入新主文件中。“更改”和“删除”记录时，要求其关键字相匹配。“删去”不用写入，而“更改”则要将更。“删去”不用写入，而“更改”则要将更改后的新记录写入新主文件。“插入”时不要求关键字相匹配，可直接将事务文件上要插入的记录写到新主文件的适当位置。主文件新主文件文件修改程序磁盘上顺序文件的批处理磁盘上顺序文件的批处理和磁带文件类似，只是当修改项中插入的记录写到新主文件的适当位置。事务文件新主文件磁带文件操作实例磁盘上顺序文件的批处理和磁带文件类似，只是当修改项中没有插入，且更新时不增加记录的长度时，可以不建立新的主文件，而直接修改原来的主文件即可。显然，磁盘文件的哈工大计算机科学与技术学院张岩Slide7-122013/12/11主文件，而直接修改原来的主文件即可。显然，磁盘文件的批处理可以在一台磁盘组上进行。第7章文件与外排序7.37.3索引文件索引文件7.37.3索引文件索引文件基本术语：索引表：除了文件本身（称做数据区）之外，另建立的一张索引表：除了文件本身（称做数据区）之外，另建立的一张指示逻辑记录和物理记录之间一一对应关系的表。索引项：索引表中的每一项，由记录的关键字和记录的存放索引项：索引表中的每一项，由记录的关键字和记录的存放地址构成，总是按关键字（或逻辑记录号）顺序排列。索引文件：把索引表和主文件总称为索引文件(IndexedFile)索引顺序文件：数据区中的记录也按关键字顺序排列的文件索引非顺序文件：数据区中的记录不按关键字顺序排列的文件。件。稠密索引：由于数据文件中记录不按关键字顺序排列，则必须对每个记录都建立一个索引项，如此建立的索引表称为稠须对每个记录都建立一个索引项，如此建立的索引表称为稠密索引。非稠密索引：数据文件中的记录按关键字顺序有序，则可对哈工大计算机科学与技术学院张岩Slide7-132013/12/11非稠密索引：数据文件中的记录按关键字顺序有序，则可对一组记录建立一个索引项，这种索引表称为非稠密索引。第7章文件与外排序7.37.3索引文件索引文件7.37.3索引文件索引文件索引文件的建立：索引表是由系统程序自动生成的索引表是由系统程序自动生成的索引文件的建立过程：（1）按输入记录的先后次序建立数据区和索引表。其中索引表中关键字是无序的。（2）待全部记录输入完毕后对索引表进行排序，排序后的索引表和主文件一起就形成了索引文件。的索引表和主文件一起就形成了索引文件。物理记录号职工号姓名职务其他10129张三程序员.关键字物理地址号29101关键字物理地址号102104。程序员10305李四维护员.10402王五程序员.10538刘六测试员.0510302104381053110805103171102291013110810831...10943...11017...1124831108431091711048112311083810534310948112哈工大计算机科学与技术学院张岩Slide7-142013/12/1111248..(a)文件数据区48112(b)输入过程中建立的索引表48112(c) 索引表（排序后）第7章文件与外排序7.37.3索引文件索引文件7.37.3索引文件索引文件索引文件的检索检索方式：直接存取或按关键字（进行简单询问）存取检索方式：直接存取或按关键字（进行简单询问）存取检索过程：首先，查找索引表若索引表上存在该记录，则根据索引项的指示读取外存若索引表上存在该记录，则根据索引项的指示读取外存上该