当索引适合 RAM 时的外部排序
External sorting when indices can fit in RAM
我想对包含 20kb 记录的多 TB 文件进行排序。我只需要从每条记录中读取几个字节来确定它的顺序，这样我就可以对内存中的索引进行排序。
但是，我无法将记录本身放入内存中。随机访问比顺序访问慢，我也不想随机访问写入输出文件。是否有任何已知的算法可以利用已排序的索引 "strategize" 在记录从输入文件复制到输出文件时以最佳方式重新排列记录？
有根据排序索引算法重新排序数组，但它们涉及随机访问。即使在 SSD 的情况下，虽然随机访问本身不是问题，但由于随机访问而一次读取或写入一条记录的吞吐量比一次读取或写入多条记录的吞吐量慢，这通常由外部合并排序。
对于典型的外部归并排序，读取的文件 "chunks" 足够小以供内部排序对 "chunk" 进行排序，并将排序后的 "chunks" 写入外部媒体。在这个初始通道之后，在 "chunks" 上完成 k 路合并，在每个合并通道上将合并的 "chunks" 的大小乘以 k，直到生成单个排序的 "chunk"。 read/write 操作可以一次读取多条记录。假设您有 1GB 的内存并使用 16 路合并。对于 16 路合并，使用了 16 个 "input" 缓冲区和 1 个 "output" 缓冲区，因此缓冲区大小可以是 63MB（1GB/17 向下舍入了一点变量 space），这将允许 3150一次读取或写入的记录，大大减少了随机访问和命令开销。假设初始通道创建大小为 0.5 GB 的已排序块，经过 3 次（16 路）合并通道后，块大小为 2TB，经过 4 次通道后为 32TB，依此类推。
我想对包含 20kb 记录的多 TB 文件进行排序。我只需要从每条记录中读取几个字节来确定它的顺序，这样我就可以对内存中的索引进行排序。
但是，我无法将记录本身放入内存中。随机访问比顺序访问慢，我也不想随机访问写入输出文件。是否有任何已知的算法可以利用已排序的索引 "strategize" 在记录从输入文件复制到输出文件时以最佳方式重新排列记录？
有根据排序索引算法重新排序数组，但它们涉及随机访问。即使在 SSD 的情况下，虽然随机访问本身不是问题，但由于随机访问而一次读取或写入一条记录的吞吐量比一次读取或写入多条记录的吞吐量慢，这通常由外部合并排序。
对于典型的外部归并排序，读取的文件 "chunks" 足够小以供内部排序对 "chunk" 进行排序，并将排序后的 "chunks" 写入外部媒体。在这个初始通道之后，在 "chunks" 上完成 k 路合并，在每个合并通道上将合并的 "chunks" 的大小乘以 k，直到生成单个排序的 "chunk"。 read/write 操作可以一次读取多条记录。假设您有 1GB 的内存并使用 16 路合并。对于 16 路合并，使用了 16 个 "input" 缓冲区和 1 个 "output" 缓冲区，因此缓冲区大小可以是 63MB（1GB/17 向下舍入了一点变量 space），这将允许 3150一次读取或写入的记录，大大减少了随机访问和命令开销。假设初始通道创建大小为 0.5 GB 的已排序块，经过 3 次（16 路）合并通道后，块大小为 2TB，经过 4 次通道后为 32TB，依此类推。