北大数据结构与算法课件08文件管理和外排序

数据结构与算法第8章文件管理和外排序信息科学与技术学院网络与信息系统研究所北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2为什么需要文件管理和外排序？„文件结构(filestructure)„对于在外存中存储的数据„数据量太大不可能同时把它们放到内存中„需要把全部数据放到磁盘中„文件的各种运算„外排序是针对磁盘文件所进行的排序操作„提高文件存储效率和运算效率北京大学信息学院张铭编写©版权所有，转载或翻印必究Page3大纲„8.1主存和外存的比较„8.2外存储器„8.3外存文件组织„8.4缓冲区和缓冲池„8.5外排序的基本算法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page48.1主存储器和外存储器„基本概念„主存和外存的价格比较„外存的优缺点北京大学信息学院张铭编写©版权所有，转载或翻印必究Page5基本概念„主存储器(primarymemory或者mainmemory，简称“内存”，或者“主存”)„随机访问存储器(RandomAccessMemory,即RAM)„高速缓存(cache)„视频存储器(videomemory)„外存储器(peripheralstorage或者secondarystorage，简称“外存”)„硬盘、磁带、软盘北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6„MB106B(内存)„GB109B(硬盘)„TB1012B(磁盘阵列)„PB1015B(磁带库)„Google是10的多少次方？„10100„8,058,044,651张网页(2004年12月)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7主存储器和外存储器之价格比较0.00750.0110.008磁带2.5712软盘0.0110.0130.017硬盘11.51内存2003年早期价格2002年底价格2001年底价格介质北京大学信息学院张铭编写©版权所有，转载或翻印必究Page8外存的优缺点„优点：永久存储能力、便携性„缺点：访问时间长„访问磁盘中的数据比访问内存慢五六个数量级（10万到100万倍）。„所以讨论在外存的数据结构及其上的操作时，必须遵循下面这个重要原则：„尽量减少访外次数！北京大学信息学院张铭编写©版权所有，转载或翻印必究Page98.2外存储器„磁盘(几十G-几百T)„磁盘访问时间估算„磁带(几个P)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10物理存储介质概览基本存储高速缓冲存储器主存储器快闪存储器磁盘光盘磁带非易失性存储三级存储(脱机存储)易失性辅助存储(联机存储)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11磁盘的物理结构活动臂（回转臂）主轴盘片磁道读写磁头柱面北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12磁盘盘片的组织扇区间间隙位数据（bit）扇区北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13磁盘存取步骤„选定某个盘片„选定某个柱面„这需要把磁头移动到该柱面，这个移动过程称为寻道(seek)„确定磁道„确定所要读写的数据在磁盘上的准确位置„这段时间一般称为旋转延迟(rotationaldelay或者rotationallatency)„真正进行读写北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14磁盘磁道的组织（交错法）（a）没有扇区交错；（b）以3为交错因子磁头旋转磁头旋转北京大学信息学院张铭编写©版权所有，转载或翻印必究Page15磁盘性能指标„容量（G）„磁盘旋转速度(rpm)„交错因子„寻道时间„旋转延迟时间北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16总存取时间(1)（1）数据连续存放，且给出了平均寻道时间。总存取时间=[平均寻道时间]+[第一道读取时间]+(总磁道数–1)×[(第二次寻道时间)+(读取整道的时间)]=[平均寻道时间]+[(0.5圈延迟+交错因子)×每圈所花时间]+(总磁道数–1)×[磁道转换时间+(0.5圈延迟+交错因子)×每圈所花时间]北京大学信息学院张铭编写©版权所有，转载或翻印必究Page17总存取时间(2)（2）数据随机存放。总存取时间=簇数×{[平均寻道时间]+[旋转延迟]+[读一簇时间]}=簇数×{[平均寻道时间]+[0.5圈延迟×每圈所花时间]+[交错因子×（每簇扇区数/每道扇区数）×每圈时间]}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page18„例8.1假定一个磁盘总容为16.8GB，分布在10个盘片上。每个盘片上有13085个磁道，每个磁道中包含256个扇区，每个扇区512个字节，每个簇8个扇区。扇区的交错因子是3。磁盘旋转速率是5400rpm，磁道转换时间是2.2ms，随机访问的平均寻道时间是9.5ms。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page19„如果读取一个1MB的文件，该文件有2048个记录，每个记录有512字节（1个扇区）。对于以下两种情况，估算进行文件处理的总时间。„（1）假定所有记录在8个连续磁道上；„（2）假定文件簇随机地散布在磁盘上。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page20解：我们先总结出一些共有的特性„每个簇为4KB„8个扇区＝512byets×8＝4KB„每个磁道有32簇„256个扇区＝256扇区÷8（扇区/簇）=32个簇„每个盘片有1.68GB„16.8GB÷10=1.68GB„每转一圈的时间为11.1ms„(60×1000)ms/5400圈=11.1（ms/圈）=11.1（ms/道）„一个磁道是一个整圈，因此，下面计算公式中，所用的单位“圈”等同于“道”北京大学信息学院张铭编写©版权所有，转载或翻印必究Page21„数据连续存放，而且给出了平均寻道时间。总存取时间=[平均寻道时间]+[(0.5圈延迟+交错因子)×每圈所花时间]+(总磁道数–1)×[磁道转换时间+(0.5圈延迟+交错因子)×每圈所花时间]=[9.5ms（平均寻道时间）]+[(0.5（半圈旋转延迟）+3（交错因子）)×11.1ms/圈+（8-1）个其他磁道×[2.2ms磁道转换时间+(0.5圈延迟+3交错因子)×11.1ms/圈]=9.5ms+48.4ms+7×41.1ms=335.7ms北京大学信息学院张铭编写©版权所有，转载或翻印必究Page22„数据随机存放„总簇数：8个磁道×32(簇/磁道)=256簇总存取时间=簇数×{[平均寻道时间]+[0.5圈延迟×每圈所花时间]+[交错因子×（每簇扇区数/每道扇区数）×每圈时间]}=256×{[9.5ms（平均寻道时间）]+[0.5（半圈旋转延迟）×11.1ms/圈]+[3(交错因子)×8(扇区/簇/)÷256(扇区/道)×11.1ms/圈]}≈256×{9.5+5.55+1.04}≈4119.04ms北京大学信息学院张铭编写©版权所有，转载或翻印必究Page23„定位并读一簇时间为：„[平均寻道时间]+[0.5圈延迟×每圈所花时间]+读一簇数据时间=[9.5ms(平均寻道)]+[0.5(半圈)×11.1ms/圈]+1.04≈9.5+5.55+1.04=16.09ms„其中，只是读一簇数据（不包括寻道定位等）的时间为„[3(交错因子)×8(扇区/簇/)÷256(扇区/道)×11.1ms/圈]≈1.04ms北京大学信息学院张铭编写©版权所有，转载或翻印必究Page24„读一个扇区的时间„[9.5ms(平均寻道时间)]+[0.5(半圈旋转延迟)×11.1ms/圈+[1扇区÷256(扇区/道)×11.1ms/圈]＝15.1ms„读一个字节的时间„[9.5ms(平均寻道时间)]+[0.5(半圈旋转延迟)×11.1ms/圈]＝15.05ms„“一次访外”操作„磁盘一次I/O操作访问一个扇区，通常称为访问“一页”（page），或者“一块”(block)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page25磁带„主要优点：使用方便、价格便宜、容量大、所存储的信息比磁盘和光盘更持久„缺点：速度较慢，只能进行顺序存取北京大学信息学院张铭编写©版权所有，转载或翻印必究Page26磁带运行示意图磁带卷在一个卷盘上，运行时磁带经过读写磁头，把磁带上的信息读入计算机，或把计算机中的信息写在磁带上。源盘接收盘磁头磁带向前运动方向北京大学信息学院张铭编写©版权所有，转载或翻印必究Page27磁带发展史„手工阶段„自动化磁带库系统„虚拟磁带技术北京大学信息学院张铭编写©版权所有，转载或翻印必究Page288.3外存文件的组织„文件组织„C++的流文件北京大学信息学院张铭编写©版权所有，转载或翻印必究Page2910300已婚分析员男周力6206200未婚程序员女陈萍9506900未婚程序员女赵莉5108900已婚分析员女李珍8607800未婚程序员男张东156工资婚姻状况职务性别姓名职工号„文件是一些记录的汇集，其中每个记录由一个或多个数据项组成。„数据项有时也称为字段，或者称为属性。例如，一个职工文件里的记录可以包含下列数据项：职工，姓名，性别，职业，婚姻状况，工资等。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page30文件组织„逻辑文件(logicalfile)„对高级程序语言的编程人员而言„连续的字节构成记录，记录构成逻辑文件„物理文件(physicalfile)„成块地分布在整个磁盘中„文件管理器„操作系统的一部分„把逻辑位置映射为磁盘中具体的物理位置北京大学信息学院张铭编写©版权所有，转载或翻印必究Page31文件的逻辑结构„文件是记录的汇集„当一个文件的各个记录按照某种次序排列起来时，各纪录间就自然地形成了一种线性关系。„因而，文件可看成是一种线性结构。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page32文件的存储结构„顺序结构——顺序文件„计算寻址结构——散列文件„带索引的结构——带索引文件北京大学信息学院张铭编写©版权所有，转载或翻印必究Page33文件上的操作„检索：在文件中寻找满足一定条件的记录„修改：是指对记录中某些数据值进行修改。若对关键码值进行修改，这相当于删除加插入。„插入：向文件中增加一个新记录。„删除：从文件中删去一个记录。„排序：对指定好的数据项，按其值的大小把文件中的记录排成序列，较常用的是按关键码值的排序。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page34C＋＋的流文件„C++程序员对随机访问文件的逻辑视图是一个单一的字节流，即字节数组。„程序员需要管理标志文件当前位置的文件指针。„常见的三个基本文件操作，都是围绕文件指针进行的：„把文件指针设置到指定位置（移动文件指针）„从文件的当前位置读取字节„向文件中的当前位置写入字节北京大学信息学院张铭编写©版权所有，转载或翻印必究Page35C＋＋操作二进制文件的常用方式——fstream类„fstream类提供函数操作可随机访问的磁盘文件中的信息。„fstream类的主要成员函数包括open，close，read，write，seekg，seekp。北京大学信息学院张铭编写©版权所有，转载或翻印必究Page36fstream类的主要函数成员#includefstream.h//fstream=ifstream+ofstream//打开文件进行处理。//模式示例:ios::in|ios::binaryvoidfstream::open(char*name,openmodemode);//处理结束后关闭文件。voidfstream::close();北京大学信息学院张铭编写©版权所有，转载或翻印必究Page37ftream类的主要函数成员（续1）//从文件当前位置读入一些字节。//随着字节的读入，文件当前位置向前移动。fstream::read(char*ptr,intnumbytes);//向文件当前位置写入一些字节//(覆盖已经在这些位置的字节)。//随着字节的写入，文件当前位置向前移动。fstream::write(char*ptr,int