Как устроен
внешняя память
Статьи
SRT
Алгоритм
Сортировка слиянием
Делит пополам, сортирует половины и сливает: n log n на любом входе, устойчиво, годится для внешней памяти.
O(n log n)
2 задачи
SRT
Алгоритм
Внешняя сортировка
Файл больше памяти: отсортированные прогоны, потом многопутевое слияние; замещающий выбор даёт прогоны длиной 2M.
O(n log n) сравнений; 2n·(1 + ⌈log_k R⌉) чтений и записей строк
1 задача
DS
Структура данных
B-дерево
Дерево с сотнями ключей в узле-странице: поиск среди миллиарда ключей читает пять страниц.
O(log n) сравнений, O(log_B n) чтений страниц
2 задачи
SYS
Структура данных
LSM-дерево
Записи копятся в памяти и ложатся на диск отсортированными прогонами; фоновые слияния держат число прогонов малым.
запись O(1) амортизированно в памяти плюс O(L·T/B) на перезапись при слиянии; чтение — по прогону на уровень
2 задачи
Задачи
Часто рядом
сортировка 3 классика 3 разделяй и властвуй 2 собеседования 2 базы данных 2 в проде 2 рекурсия 1 устойчивость 1 массив 1 дерево 1 дерево поиска 1 поиск 1