外部排序 (External Sort)

约 151 个字 预计阅读时间 1 分钟

• 假设有\(N\)个数据，同时能处理\(M\)个record
• 最普通的方法需要\(1+\log{\lceil \frac NM \rceil}\)个pass
• 对于\(k-way\ merge\)，需要\(1+\log_{k}{\lceil \frac NM \rceil}\)个pass，使用\(2k\)个tapes

最优分配策略

对于\(k-way\ merge\)，如何分配才能使总的\(pass\)最小？以三阶合并为例（总共31个run）：

1. 写出\(k\)阶斐波那契数列

   1, 1, 2, 4, 7, 13, 24, 44

2. 寻找最优分配

找到第一个大于31的数：44

计算差值：44 - 31 = 13

初步分配：24, 13, 7

调整分配：(24-13), 13, 7，即11, 13, 7

评论