我想排序一个包含20kb记录的多TB文件。我只需要从每个记录中读取几个字节以确定其顺序，因此我可以在内存中对索引进行排序。
但是，我无法将记录本身放在记忆中。随机访问比顺序访问慢，我也不想随机访问输出文件的写入。是否有任何已知的算法可以利用排序索引来“策略化”在将记录从输入文件复制到输出文件时重新排列记录的最佳方式？
根据排序索引算法有重排序列，但它们涉及随机访问。即使在SSD的情况下，虽然随机访问本身不是问题，但是由于随机访问而一次读取或写入一条记录的吞吐量比一次读取或写入多条记录的速度慢，这通常是外部的合并排序。
对于典型的外部合并排序，文件以“块”形式读取，该块足够小，以便内部排序对“块”进行排序，并将排序的“块”写入外部介质。在该初始传递之后，在“块”上进行k路合并，在每次合并传递上将合并的“块”的大小乘以k，直到产生单个排序的“块”。读/写操作一次可以读取多个记录。假设您有1GB的RAM并使用16路合并。对于16路合并，使用16“输入”缓冲区和1“输出”缓冲区，因此缓冲区大小可以是63MB（1GB / 17向下舍入一点用于可变空间），这将允许在a处读取或写入3150条记录。时间，大大减少了随机访问和命令开销。假设初始传递创建大小为0.5 GB的排序块，经过3次（16路）合并传递后，块大小为2TB，4次传递后，它为32TB，依此类推。