跳到主要内容

外部排序

外部排序用于处理数据量大到无法一次全部加载进内存的排序任务。它通常依赖磁盘文件和多路归并。

一、适用场景​

  • 大文件排序；
  • 日志排序；
  • 数据库排序；
  • 搜索引擎索引构建；
  • 数据仓库离线处理。

二、基本思想​

外部排序通常分为两个阶段：

三、外部归并排序​

步骤：

  1. 按内存大小切分大文件。
  2. 对每个小块使用内部排序。
  3. 生成多个有序临时文件。
  4. 使用多路归并合并文件。
  5. 删除临时文件。

四、多路归并​

多路归并可以使用最小堆优化。

五、性能关注点​

外部排序的瓶颈通常不是 CPU，而是磁盘 I/O。

优化方向：

  • 增大缓冲区；
  • 减少归并趟数；
  • 使用顺序读写；
  • 临时文件分布到不同磁盘；
  • 使用压缩减少 I/O；
  • 合理选择归并路数。

六、练习​

  • 生成一个大文本文件。
  • 每行一个数字。
  • 按固定内存大小切分。
  • 对每个块排序。
  • 使用多路归并输出最终有序文件。