大文件排序：如何对100GB文件进行外部排序？
给定一个100GB的大文件，每行一个整数（64位），服务器内存仅16GB。请设计一个外部排序(External Sort)算法，包括多路归并(Multi-Way Merge)的具体实现、排序过程中的IO优化策略、以及使用SSD和HDD的不同策略。
回答
小字辈
外部排序（External Sort）步骤：
阶段1：分割与内排序（Partition & Sort）
- 将100GB文件分割成N个200MB的chunk（留15GB给排序缓冲区）
- 每个chunk加载到内存，使用快速排序排好
- 写回磁盘，生成N个有序临时文件（约512个文件）
阶段2：多路归并（Multi-Way Merge）
- 从每个有序文件中读取第一行到输入缓冲区
- 使用败者树(K-Way Loser Tree)或小顶堆选择最小值
- 将最小值写入输出缓冲区
- 当输出缓冲区满时写入最终结果文件
败者树优化：
- 比较次数从O(K)降至O(logK)
- K=512路时，每次比较仅9次，而非512次
IO优化策略：
| 策略 | 说明 | 效果 |
|---|---|---|
| 双缓冲(Double Buffering) | CPU处理一个缓冲区时，IO写另一个 | CPU和IO并行 |
| 异步IO(AIO) | 使用aio_read()异步读取 | 减少IO等待 |
| 合并写入 | 输出缓冲区≥1MB再写盘 | 减少随机写 |
| 压缩中间文件 | LZ4/Snappy压缩临时文件 | 减少磁盘IO量 |
SSD vs HDD策略：
- HDD：尽量减少随机读写，增大chunk size减少文件数
- SSD：可接受更多随机读，适当减小chunk size减少内存使用
复杂度：IO次数 = 读取一次(100GB) + 写入N个chunk(100GB) + 归并读取(100GB) + 写入结果(100GB) ≈ 400GB IO