文件处理&外部排序

#

• IO次数成为重要衡量标准

文件处理 黄金准则

#

• 尽可能减少磁盘存储的次数

物理数据存储

#

• 引用的局部性
• 块
• 簇

磁盘存取花费

#

= 寻道时间 + 旋转延迟 + 传输时长

Buffers and Buffer Pools

#

…

用内排if虚拟内存ook

#

改内排到外排

#

归并排序very good

• 在logn次中处理n个元素

简单2路外排归并

#

RAM

• 2 input buffers
• 2 output buffers

DISK

• 2 input files
• 2 output files

步骤

#

1. 分割文件到两个输入
2. 以一个block开始读每个输入文件到input buf
3. 重复步骤1 - 2 直到两个输入文件耗尽
   1. 取奇数次运行于input buf，输出到第一个output buf
   2. 取偶数次运行于input buf，输出到第二个output buf
4. 写出output buf
5. 交替输出和输入文件
6. 重复步骤2 - 5（除开第二个input文件为空）
7. 第一个input文件为所求

初始runs个数越少（长度越长），pass越少，需要的I/O操作越少，速度越快