0.介绍
假设有10GB数据文件,数据形式如下1
2
3
4
5
6...
120
123
58
789
...
每条数据元素使用换行符\n
分割开,即每一行为一条数据。
现在需要排序该文件并输出结果文件。 由于数据量较大,无法直接在内存小于10G的计算机中排序。
下面介绍一种处理方法。
1.标记数据块
建立数据结构Block来保存文件分块信息1
2
3
4
5type Block {
id: Number, // 文件块ID
start: Number, // 文件块开始位置
end: Number // 文件块结束位置
}
打开数据文件,每次读取1MB的数据,处理好数据块边界,使得每块数据包含完整的记录。
这样我们得到数据块数组Block[]
2.对每个数据块排序
遍历数据块数组,对每块约1MB的数据排序并写回原文件。
这时数据文件大概是这样子:每块数据是有序的,总体数据无序的。1
1 4 7 || 3 6 9 || 2 5 8
3.建立堆结构
遍历数据块数组Block[],从每个数据块取出一个元素,建立小顶堆。
这里的每个元素要构造一个数据结构,要包含元素所在数据块的ID。1
2
3 1
/ \
3 2
4.堆排序
- 调整堆,取出堆顶元素并写入结果文件
- 如果取出元素所在数据块还有数据,则从该数据块读取一个元素放到堆顶。
- 否则,把堆的最后一项元素移动到堆顶,堆大小减一。
- 调整堆。
- 循环前面的步骤直至堆为空。
- 结束。
5.内存分析
- 至少需要
数据块大小
的内存。 - 至少需要
(总数据大小 / 数据块大小)* 堆元素大小
的内存。
分析以上条件得出数据块大小 = (总数据大小 / 数据块大小)* 堆元素大小
时占用内存最小, 即