数据结构与算法分析第8章.ppt

数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysis陈星第8章文件管理和外排序主存储器和辅助存储器的比较减小磁盘访问次数的方法8.2磁盘扇区硬盘中读写数据的步骤：
寻道：移动硬盘的I/O磁头，定位到包含数据的磁道。（慢，占据读写数据的大部分时间）
等待包含数据的扇区旋转到磁头下面。
读取或写入一个扇区的数据。
安排扇区的交错法：概念：
引用的局部性：如果读出文件的一个扇区，很可能就要读出文件的下一个扇区。（假设）
簇：多个扇区组成，为文件分配的最小单位，大小由操作系统所定。
文件分配表：记录哪些簇（扇区）属于哪一个文件。
范围：一组物理上相连的簇。
内部碎片：由于数据没有填满一个扇区或一个簇而浪费的存储空间。8.2.2磁盘访问代价8.3缓冲区和缓冲池8.3缓冲区和缓冲池8.5外部排序8.6外部排序的简单方法对外部归并排序算法的改进：
对小的顺串不做归并排序。即对读入主存的数据做内部排序，并读入尽可能多的数据，减小归并排序的趟数。
每一趟扫描归并多个顺串，即多路归并技术。
所有好的外部排序算法都是基于：
把文件分成大的初始顺串（读入更多记录到主存，执行内部排序）。
把所有顺串归并在一起，形成一个已排序的文件。置换选择排序的过程：
在可利用的内存中构建一个数组（堆）、一个输入缓冲区和一个输出缓冲区。
从磁盘上读取记录填充数组。
构建一个最小值堆。设Last=m-1，m为数组大小，Last标识堆中最后一个记录。8.8多路归并