数据结构与算法第八章文件管理和外排序

《数据结构与算法第八章文件管理和外排序》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构与算法第8章文件管理和外排序任课教员：张铭http://db.pku.edu.cn/mzhang/DS/mzhang@db.pku.edu.cn北京大学信息科学与技术学院网络与信息系统研究所©版权所有，转载或翻印必究为什么需要文件管理和外排序？¢文件结构(filestructure)¢对于在外存中存储的数据¢数据量太大不可能同时把它们放到内存中¢需要把全部数据放到磁盘中¢文件的各种运算¢外排序是针对磁盘文件所进行的排序操作¢提高文件存储效率和运算效率北京大学信息学院张铭编写©版权所有，转载或翻印必究Page

2、2大纲¢8.1主存和外存的比较¢8.2外存储器¢8.3外存文件组织¢8.4缓冲区和缓冲池¢8.5外排序的基本算法北京大学信息学院张铭编写©版权所有，转载或翻印必究Page38.1主存储器和外存储器¢基本概念¢主存和外存的价格比较¢外存的优缺点北京大学信息学院张铭编写©版权所有，转载或翻印必究Page4基本概念¢主存储器(primarymemory或者mainmemory，简称“内存”，或者“主存”)¢随机访问存储器(RandomAccessMemory,即RAM)¢高速缓存(cache)¢视频存储器(videome

3、mory)¢外存储器(peripheralstorage或者secondarystorage，简称“外存”)¢硬盘、磁带、软盘北京大学信息学院张铭编写©版权所有，转载或翻印必究Page56¢MB10B(内存)9¢GB10B(硬盘)12¢TB10B(磁盘阵列)15¢PB10B(磁带库)¢Google是10的多少次方？100¢10¢8,058,044,651张网页(2004年12月)北京大学信息学院张铭编写©版权所有，转载或翻印必究Page6主存储器和外存储器之价格比较2001年底2002年底2003年早介质价格价格期

4、价格内存11.51硬盘0.0170.0130.011软盘1272.5磁带0.0080.0110.0075北京大学信息学院张铭编写©版权所有，转载或翻印必究Page7外存的优缺点¢优点：永久存储能力、便携性¢缺点：访问时间长¢访问磁盘中的数据比访问内存慢五六个数量级（10万到100万倍）。¢所以讨论在外存的数据结构及其上的操作时，必须遵循下面这个重要原则：¢尽量减少访外次数！北京大学信息学院张铭编写©版权所有，转载或翻印必究Page88.2外存储器¢磁盘(几十G-几百T)¢磁盘访问时间估算¢磁带(几个P)北京大学信息

5、学院张铭编写©版权所有，转载或翻印必究Page9物理存储介质概览基本存储高速缓冲存储器易失性主存储器辅助存储快闪存储器(联机存储)磁盘非易失性存储光盘三级存储(脱机存储)磁带北京大学信息学院张铭编写©版权所有，转载或翻印必究Page10磁盘的物理结构主轴盘片磁道活动臂（回转臂）柱面读写磁头北京大学信息学院张铭编写©版权所有，转载或翻印必究Page11磁盘盘片的组织扇区扇区间间隙位数据（bit）北京大学信息学院张铭编写©版权所有，转载或翻印必究Page12磁盘存取步骤¢选定某个盘片¢选定某个柱面¢这需要把磁头移动到该

6、柱面，这个移动过程称为寻道(seek)¢确定磁道¢确定所要读写的数据在磁盘上的准确位置¢这段时间一般称为旋转延迟(rotationaldelay或者rotationallatency)¢真正进行读写北京大学信息学院张铭编写©版权所有，转载或翻印必究Page13磁盘磁道的组织（交错法）磁头磁头旋转旋转（a）没有扇区交错；（b）以3为交错因子北京大学信息学院张铭编写©版权所有，转载或翻印必究Page14磁盘性能指标¢容量（G）¢磁盘旋转速度(rpm)¢交错因子¢寻道时间¢旋转延迟时间北京大学信息学院张铭编写©版权所有，

7、转载或翻印必究Page15总存取时间(1)（1）数据连续存放，且给出了平均寻道时间。总存取时间=[平均寻道时间]+[第一道读取时间]+(总磁道数–1)×[(第二次寻道时间)+(读取整道的时间)]=[平均寻道时间]+[(0.5圈延迟+交错因子)×每圈所花时间]+(总磁道数–1)×[磁道转换时间+(0.5圈延迟+交错因子)×每圈所花时间]北京大学信息学院张铭编写©版权所有，转载或翻印必究Page16总存取时间(2)（2）数据随机存放。总存取时间=簇数×{[平均寻道时间]+[旋转延迟]+[读一簇时间]}=簇数×{[平均寻

8、道时间]+[0.5圈延迟×每圈所花时间]+[交错因子×（每簇扇区数/每道扇区数）×每圈时间]}北京大学信息学院张铭编写©版权所有，转载或翻印必究Page17¢例8.1假定一个磁盘总容为16.8GB，分布在10个盘片上。每个盘片上有13085个磁道，每个磁道中包含256个扇区，每个扇区512个字节，每个簇8个扇区。扇区的交错因子是3。磁盘旋转速率是5400rp