базы данных

SRT Алгоритм Top-k: k лучших Куча из k с худшим наверху: поток читается один раз, почти каждый элемент отсеивается одним сравнением. O(n log k) 2 задачи DS Структура данных Хеш-таблица Поиск, вставка и удаление по ключу в среднем за O(1): ключ превращается в номер ячейки массива. O(1) в среднем 2 задачи DS Структура данных Фильтр Блума Отвечает «точно нет» или «возможно, да» о членстве в множестве, тратя около 10 бит на элемент. O(k) 2 задачи DS Структура данных Двоичное дерево поиска Меньшие налево, большие направо: поиск, порядок и k-й элемент за высоту дерева — от log n до n. O(h): от O(log n) до O(n) 2 задачи DS Структура данных Список с пропусками Связный список с экспресс-линиями по броскам монетки: поиск и вставка за O(log n) в среднем, без поворотов. O(log n) в среднем на поиск, вставку, удаление и ранг 1 задача DS Структура данных B-дерево Дерево с сотнями ключей в узле-странице: поиск среди миллиарда ключей читает пять страниц. O(log n) сравнений, O(log_B n) чтений страниц 2 задачи DS Структура данных LRU-кэш Словарь плюс двусвязный список: get и put за O(1), выселяется тот, к кому дольше всех не обращались. O(1) на get и put 2 задачи DP Приём Динамика по маскам Состояние — подмножество, записанное битами числа: точный коммивояжёр, назначения, раскладки по профилю. O(2ⁿ · n²) для коммивояжёра 2 задачи GEO Структура данных R-дерево Окно карты 10° × 5°: из 58 987 отрезков берега R-дерево проверяет 847 прямоугольников. И находит город, дальше всех от моря. окно — число открытых узлов × M; ближайший — обычно O(log n) узлов 1 задача GEO Приём Кривые Гильберта и geohash Пронумеровать плоскость так, чтобы соседи на карте стояли рядом в одномерном индексе: Z-порядок, geohash, Гильберт. O(k) на номер 1 задача SYS Алгоритм Консистентное хеширование Распределяет ключи по серверам так, что при добавлении сервера переезжает лишь его доля. O(log(N·v)) на поиск сервера 1 задача SYS Структура данных HyperLogLog Число разных элементов потока в килобайте памяти: длинные серии нулей в хешах и среднее по регистрам. O(1) на элемент, O(m) на оценку 2 задачи SYS Структура данных Дерево Меркла Хеши хешей: отпечаток всего набора, поиск расхождений за несколько сравнений и доказательство из log n хешей. O(n) на построение, O(log n) на доказательство и его проверку 2 задачи SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи SYS Структура данных LSM-дерево Записи копятся в памяти и ложатся на диск отсортированными прогонами; фоновые слияния держат число прогонов малым. запись O(1) амортизированно в памяти плюс O(L·T/B) на перезапись при слиянии; чтение — по прогону на уровень 2 задачи SYS Алгоритм Raft Реплицированный журнал на ненадёжных серверах: лидер, сроки, большинство; выдерживает падение меньшей половины. один круг сообщений до большинства на запись 2 задачи SYS Алгоритм Часы Лэмпорта и векторные часы Логические часы: одно число Лэмпорта согласовано с «случилось раньше», вектор по процессам отличает «раньше» от «параллельно». O(1) на событие у Лэмпорта, O(n) у векторных 2 задачи SYS Структура данных CRDT Данные, копии которых правят независимо и сливают в любом порядке: счётчики, множества, текст. O(1) на операцию у счётчика и множества; вставка в текст — O(1) в среднем 2 задачи SYS Алгоритм LFU и ARC Кэши, которые помнят частоту: LFU за O(1) на корзинах счётчиков и ARC, который сам делит места между свежими и частыми. O(1) на запрос у обоих 2 задачи TEC Приём Числа, которые стоит знать Кэш, память, диск и сеть отличаются в сотни раз — прикидка по этим числам показывает, что ускорять. прикидка — минута на салфетке 1 задача TEC Приём Сжатие координат Значения до миллиарда заменить их номерами по порядку — и строить массивы и деревья по номерам. O(n log n) на сжатие 2 задачи