数据结构课件-版-ds文件与外排序

第7章外部分 Slide.1-文件系统是数据库系统的基础，从、高效和系统软件研制角度看，文件系统1、相关概文件是用于表示驻留在 器中的数据，是同性质记录的有序集合①文件的数据量通常很大，被放置在外存上②数据结构中讨论的文件主要是数据库意义上的文件，不是操作系统义上的文件③操作系统中研究的文件是一维的无结构连续字符序列。数据库究的文件是带有结构的记录集合，每个记录可由若干个数据项构哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-记录是文件中存取的基本单位，数据项是文件可使用的最小单位。数项有时也称为字段(Field)，或者称为属性(Attribute)或)。为讨论方便起见，一般不严格区分关键字项和关键字。即在不时，将主(或次)关键字项简称为主(或次)关键字，并且假定主关键字项只一个数据项张男 女王女陈男 男林女关键 主关键 次关键哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-不定长记录文文件的逻辑结构和物理结逻辑结构：呈现给用户，描述记准考证政语数外物理结构 结构，记录 器中的组织，连续，链式哈尔滨工业大学计算机科学与技术学2、文件操操

第7章外部分 Slide.1-检索方式：实 成更新方式：实 成(即记录存入文件时的顺序编号)①简单查询：只查询单个关键字等于给定值的记 ”的哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-②范围查询：只查询单个关键字属于某个范围内的所有记【例】下表的学生文件中，查 >18的所有学生的记录③函数查询：规定单个关键字的某个函数，查询该函数的某个【例】下表的学生文件，查询全体学生的平均数学成绩是多少 查询：以上三种查询 运算(与、或、非)组合起来的查询【例】下表的学生文件中，要找出所有语文成绩低于80的男生以及所数学低于80 ，查询条件是 =“男”)and(语文 =“女”)and(数学张男张男 女王女陈男 男林女哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-操作主要是①对文件进行记录的插入、删除及修改等②为提高文件的效率，进行再③文件被破坏后的恢复操作，以及文件中数据的安文件上的检索和更新操作，都可有实时和批量两种不同的处理①实时处理：响应时间要求严格，要求在接受询问后几秒种内完②批量处理：响应时间要求宽松一些，不同的文件系统有不同要求个 票系其和更新都应实时处理银行的账户系统需要实时检，但可进行批量更新，即可以将一天的存和提款记录在一个事务文件，在一天的营业之后再行批量处理。哈尔滨工业大学计算机科学与技术学一.顺序方

第7章外部分 Slide.1-顺序方索引方散列方方顺序一致的文件。磁盘文由柱面和磁道组

文件改程

职工新文磁带文件磁带文件操作实哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-顺序文件分顺序有序文记录按其主关键字有序的顺序文件为顺序顺序无序文记录未按其主关键字有序排列的顺序文件为顺序无序文注意为提高检索效率，常将顺序文件组织成有序文件顺序有序文件存取的查找方顺序存 器（磁带）上文件存取的查找方顺序查找法即顺序扫描文件，按记录的主关键字逐个查找。要索第i个记录，必须检索前i-1个记录哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-①这种查找法对于少量的检索是不经济的，但适合于批量检索②顺序存 器上的文件只能用顺序查找法存直接存 （磁盘）上文件存取的查找方顺序查找分块查找具体方法100个记录为一块，各块的最后一个记录的主关键字为Kl00，K200，…，1i…：查找时，将所要查找的记录的主关键字K，依次和各块的最大于K100(i-且小于或等于块内进行扫描。注意分块查找法在查找时不必扫描整个3）分查找①二分查找法只适合对较小的文件或一个文件的索引进行查找哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-②当文件很大，在磁盘上占有多个柱面时，二分查找将引起磁头来移动，增加寻查时间③对磁盘等直接存取设备，还可以对顺序文件进行插值查找和跳步查顺序文件的修顺序文件的修改操由于文件中的记录不能像向量空间的数据那样“移动”，故只能通 批量处理方式实现顺序文件的更①把所有对顺序文件(以下称主文件)的更新请求，都放入一个的事务文件②当事务文件变得足够大时，将事务文件按主关键字排序③再按事务文件对主文件进行一次全面的更新，产生一个新的件④最后，清空事务文件，以便积累此后的更新内容哈尔滨工业大学计算机科学与技术学二.索引方

第7章外部分 Slide.1- 索引顺序文件(IndexedSequential索引非顺序文件(IndexedNonSequentail哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-索引文件索引文件索引文件 器上分为两个区：索引区和数据区。索引区存放引表，数据区存放主文件索引文件的建建立索引文件的无序的一起就形成了索引文件。10.2如表10.3所示，排序后的索引表见表.4，表10.2和表4一起形成了一个索引文件。哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-哈尔滨工业大学计算机科学与技术学索引文件的操

第7章外部分 Slide.1-检索操检索分两步进行①将外存上含有索引区的页块送人内存，查找所需记录的物②将含有该记录的页块送人内注意①索引表不大时，索引表可一次读入内存，在索引文件中检索只需外存：一次读索引，一次读记②由于索引表有序，对索引表的查找可用顺序查找或二分查找等方法更新操（1）插入：将插入记录置于数据区的末尾，并在索引表中插入索引（2）删除：删去相应的索注意：修改主关键字时，要同时哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-利用查找表建立多级查找对索引表建立的索引，称为查找表。查找表的建立可以为占据多个块的索引表的查阅减少外存次数。【例】表10.410.5所示。检索记录时，先查找查找表，再查索引表，然后记录，三次外存即可表哈尔滨工业大学计算机科学与技术学动态索

第7章外部分 Slide.1-当数据文件在使用过程中记录变动较多时，利用二叉排序树(或AVL树)、B_树(或其变型)等树表结构建立的索引，为动态索引树表①插入、删除方②本③建立索引表的过程即为排序过程树表结构选①当数据文件的记录数不很多，内存容量足以容纳用二叉排序树(或AVL树)做索引；②当文件很大时，索引表(树表)外存的阶-树(或其变型)作为索引表为宜m）。外存的索引表的查找性能评由于外存的时间比内存中查找的时间大得多，所以外存的索引表的查找性能主要着眼于外存的次数，即索引表的深度。哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-三.散列文件 方式组织的文件，亦称直接存取文件。即根 散列表与散列文件比散列文比较项单若干记录为桶处理办开放地址法、拉链拉链哈尔滨工业大学计算机科学与技术学基桶和溢出

第7章外部分 Slide.1-在散列文件的(Bucet)个记录，个同义词会发生溢出。需要将第溢出桶。相对地，称前m个同义词存放的桶为"基桶"注意出桶和基桶大小相同，相互之间用指针相在基桶中没有找到待查记录时，就沿着指针到所指溢出桶中230526，01，18，02，27，1，0，0，0，1，0，1，3，2。桶的容量，桶数。用除余法作散列函数(k7。由此得到的散列文件如下图所示。哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-哈尔滨工业大学计算机科学与技术学散列文件的查找

第7章外部分 Slide.1-在散列文件中查找的过程根据给定值求出散列桶地将基桶的记录读人内存，进行顺序查散列文件的删除操在散列文件中删去一个记录，仅需对被删记录作删除标记即可哈尔滨工业大学计算机科学与技术学散列文件的特

第7章外部分 Slide.1-散列文件的优文件随机存放，记录不需进行排序插入、删除方便存取速度快；不需要索引区，节 空间散列文件的缺不能进行顺序存取，只能按关键字随机查询方式限于简单查 在经过多次插文件哈尔滨工业大学计算机科学与技术学四、多关键字文

第7章外部分 Slide.1-多关键字文包含有多个次关键字索引的文件称为多关键字文注意：次关键字索引本身可以是顺序表或多关键字文件和其他文件的区多关键字文其它文包含的关建立的建立主关键字索引多个次关键字的只有有主关键索查对主关键字索引和关键字索只能顺序存取记录进行比较，效低文件组织四种方式均四种方式均哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-多重链表文件的组织方多重链表文件是将索引方法 方法相结合的一种组织方式具体组织方式对主关键字索对每个需要查询的次关键字建立一个索引，同时将具有相同次关的记 成一个链表并将此链表的头指针、链表长度及次关键字，作为索引表的一项通常多重链表文件的主文件是一个顺序文哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-【例】上表是一个多重表文件的示例。主关键字是职工号，次关键字是职务和工资级别。它设有两个字段，分别将具有相同职务和相同工资级哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-多重表文件的查询操单关键字简单查询基本思据给定值，在对应次关键字索引表中找到对应索引项，从头指针发，列出该链表上所有记录【例】针对上面的多重表查询所有软件人员，则只需在职务索引表中先找到次关键字软件人员该链表上所有的记录即可。多关键字组合查询基本思【例】若要查询工资级别为引的硬件人员哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-注意（多个多重表的更新操插入新记相同次关键字链表不按主关键字大 时，在主文件中插入新录后，将记录在各个次关键字链表中插在链表的头指针之后即删除记在删去一个记录的同时，需在每个次关键字的链表中删去哈尔滨工业大学计算机科学与技术学六、倒排文

第7章外部分 Slide.1-倒排文件的组织倒排文件和多重表文件的区别在于次关键字索引结构不在次关键字索引中，具有相同次关键字的记录之间不进 ，而列出具有该次关键字记录的物理倒排文件中的次关键字索引称做倒排表。倒排表和主文件一起就构了倒排文件哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-【例】将上表所示的多重表文件去掉两 字段后作为主文件所建立职务倒排表和工资级别倒排表，如下图所示哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-倒排文件的查从而提高查找速度。哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-【例】要找出所有工资级别小于的次关键字为的物理地址集合先做交运算：{108}∪{102，106}即符合条件的记录，其物理地址是101和102倒排文件的更在插入和删除记录时，还要修改倒列出主关键字的倒排列出主关键字的倒排表的特点取速度较②主关键字可看成是记录的符号地址，对 具有相对独立性【例】下面的表就是按上述方法对多重表文件所组织的职务倒哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-倒排文件与一般文件组织的区倒排。注意多重表文件实际上也是倒排文件，只不过索引的方哈尔滨工业大学计算机科学与技术学

第7章外部分 Slide.1-理。这样，在排序过程中必须不断地在内存与外存之间传送数据。这种基于外部外排序的基本当对象以文件形式存放于磁盘上的时候，通常是按物理 的物理块也叫做页块，是磁盘存取的基本单位每个页块可以存放几个对象。操作系统按页块对磁盘上的信息写哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-分两个阶段进第一阶段：首先，将文件中的数据分段输入到内存，在内存中采用内分类方法对其进行分类（分类完的文件段，称为归并段)，然后将有序段写回整个文件经过在内存逐段分又逐段写回外存，这样在外存中形个初始的归并段第二阶段：对这些初始归并段采用某种归并分类方法，进行多遍归并最后形成整个文件的单一归并段哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-如何进行多路归并以减少文件的归并遍如何巧妙地运用内存的缓冲区使I/O和尽可能并行工作根据外存的特点选择较好的产生初始归并段的方哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-设有一个入现用一台内存至多可容纳750个记录的计算机对该文件进行分类。输入文件放在磁盘上,每个页块可容250个记,这样全部记录可 在4500/个页块。输出文件也放在磁盘上,用以存放归并结果。由于内存中可用于分类 区域能容纳750个记录,因此内存中好能存3个页块的记录在外分类一开始,把18块记录,每3块一组,读入内存。利用某种内分类方法进行内分类形成初始归并段再写回外存。总共可得到6个初始归归并

哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-若把内存区域等份地分为3个缓冲区。其中的两个为输入缓冲区一个为输出缓冲区可以在内存中利2路归并函数merge()路归并首先,从参加归并排序的两个输入归并段R1和R2中分别读入一块250个记录放在输入缓冲区1和输入缓冲区2中。然后在内存中进行2路哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-当输出缓冲区装满250个记录时，就输出到、、R1 R2 R3 R4归并第一归并结第二归并结第三归并结哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-

…讨论问

m个归并段的归并多路归并——减少归并遍并行操作的缓冲区处理——使输入、输出和CPU处理尽可初始归并段的生哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-多路归并——减少归并遍m个初始段进行2路归并，需要遍归并一般地，m个初始段，采用K路归并，需要遍归并显然，K越大，归并遍数越少，可提高归并的效率在K路归并时，从K个关键字中选择最小记录时，要比K-1次。若记录总数为n，每遍要比较的次数为n*(K-1)*[logkm]=n*(K-1)可以看出，随着k增大，(K-1)/log2K也增大，当归并路数多时，处理的时间也随之增多。当PU处理时间大于因K为此要选择好的分类方法，以减少分哈尔滨工业大学计算机科学与技术学K选择树选最小对象

第7章外部分 Slide.1-69689选择69689分析第一次建立选择树的比较所花时间为O(k-1)=O(而后每次重新建造选择树所需时间O(log2k间加上n-1次重新选择树的时间：O((n-1)·log2k)+O(k)=O(n·log2kO(n·log2k·logkm)=O(n·log2m)(k路归并CPU时间与k无关)哈尔滨工业大学计算机科学与技术学第7章外部分 Slide.1-——使输入、输出和CPU对k个归并段进行k路归并至少需要k个输入和1哈尔滨工业大学计算机科学与技术学第7章外部分