当索引可以放入RAM时进行外部排序

Question

我想对一个包含20kb记录的多TB文件进行排序。我只需要从每条记录中读取几个字节来确定其顺序，这样我就可以对内存中的索引进行排序。

然而，我不能将记录本身放入内存中。随机访问比顺序访问慢，我也不想对输出文件进行随机访问写入。在将记录从输入文件复制到输出文件时，是否有任何已知的算法可以利用已排序的索引来“策略化”重新排列记录的最佳方式？

Answer 1

根据排序索引算法有重排序数组，但它们涉及随机访问。即使在SSD的情况下，尽管随机访问本身不是问题，但是由于随机访问而一次读取或写入一个记录具有比通常由外部合并排序向下的一次读取或写入多个记录更慢的吞吐量。

对于典型的外部合并排序，文件以足够小的“块”读取，以便内部排序对“块”进行排序，并将排序的“块”写入外部介质。在此初始遍之后，对“块”执行k路合并，在每次合并遍时将合并的“块”的大小乘以k，直到产生单个排序的“块”。读/写操作可以一次读取多条记录。假设您有1 1GB的ram，并使用16路合并。对于16路合并，使用16个“输入”缓冲区和1个“输出”缓冲区，因此缓冲区大小可以是63MB (1 1GB/17向下舍入一个位用于可变空间)，这将允许一次读取或写入3150条记录，从而大大减少随机访问和命令开销。假设初始遍创建大小为0.5 GB的已排序块，在3次(16次)合并遍之后，块大小为2TB，在4遍之后为32TB，依此类推。