sorting - 索引可以放入 RAM 时的外部排序

Question

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

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

标签： sortingdisk

Answer 1

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

对于典型的外部合并排序，文件以足够小的“块”读取，内部排序可以对“块”进行排序，并将排序后的“块”写入外部媒体。在这个初始通道之后，对“块”进行 k 路合并，在每个合并通道上将合并的“块”的大小乘以 k，直到产生单个排序的“块”。读/写操作可以一次读取多条记录。假设您有 1GB 的内存并使用 16 路合并。对于 16 路合并，使用 16 个“输入”缓冲区和 1 个“输出”缓冲区，因此缓冲区大小可以是 63MB（1GB/17 向下舍入一点用于可变空间），这将允许读取或写入 3150 条记录时间，大大减少了随机访问和命令开销。假设初始传递创建大小为 0.5 GB 的排序块，