0.介绍

假设有10GB数据文件，数据形式如下

1
2
3
4
5
6

...
120
123
58
789
...

每条数据元素使用换行符\n分割开，即每一行为一条数据。

现在需要排序该文件并输出结果文件。 由于数据量较大，无法直接在内存小于10G的计算机中排序。

下面介绍一种处理方法。

1.标记数据块

建立数据结构Block来保存文件分块信息

1
2
3
4
5

type 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.堆排序

1. 调整堆，取出堆顶元素并写入结果文件
2. 如果取出元素所在数据块还有数据，则从该数据块读取一个元素放到堆顶。
3. 否则，把堆的最后一项元素移动到堆顶，堆大小减一。
4. 调整堆。
5. 循环前面的步骤直至堆为空。
6. 结束。

5.内存分析

• 至少需要 数据块大小 的内存。
• 至少需要 (总数据大小 / 数据块大小)* 堆元素大小 的内存。

分析以上条件得出数据块大小 = (总数据大小 / 数据块大小)* 堆元素大小时占用内存最小， 即