Блог

Я хочу отсортировать файл объемом в несколько ТБ, содержащий записи размером 20 КБ. Мне нужно всего лишь прочитать несколько байтов из каждой записи, чтобы определить ее порядок, чтобы я мог сортировать индексы в памяти.

Однако я не могу поместить сами записи в память. Произвольный доступ выполняется медленнее, чем последовательный доступ, и я также не хочу, чтобы произвольный доступ записывался в выходной файл. Известен ли какой-либо алгоритм, который использует отсортированные индексы для «разработки стратегии» оптимального способа переупорядочивания записей по мере их копирования из входного файла в выходной файл?

Существует массив переупорядочивания в соответствии с алгоритмами сортировки индексов, но они включают произвольный доступ. Даже в случае SSD, хотя сам произвольный доступ не является проблемой, чтение или запись одной записи за раз из-за произвольного доступа имеет меньшую пропускную способность, чем чтение или запись нескольких записей одновременно, что обычно снижается при внешней сортировке слиянием.

Для типичной внешней сортировки слиянием файл считывается «фрагментами», достаточно маленькими, чтобы внутренняя сортировка сортировала «фрагмент» и записывала отсортированные «фрагменты» на внешний носитель. После этого начального прохода для «блоков» выполняется k-образное слияние, умножающее размер объединенных «блоков» на k на каждом проходе слияния, пока не будет создан один отсортированный «блок». Операции чтения / записи могут считывать несколько записей одновременно. Допустим, у вас 1 ГБ ОЗУ, и вы используете 16-полосное слияние. Для 16-полосного слияния используются 16 буферов ввода и 1 буфер вывода, поэтому размер буфера может составлять 63 МБ (1 ГБ / 17 округлено немного в меньшую сторону для переменного пространства), что позволит одновременно считывать или записывать 3150 записей, что значительно сокращает объем произвольного доступа и накладные расходы на команды. Предполагая, что начальный проход создает отсортированные фрагменты размером 0,5 ГБ, после 3 (16 проходов) слияния размер фрагмента составляет 2 ТБ, после 4 проходов — 32 ТБ и так далее.