Выбор ответа Middle Разборы систем обновлено
Структура для подсказок
Вопрос
Подсказки поиска должны отвечать быстрее 100 мс на каждый введённый символ. Какой подход стандартный?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Префиксное дерево в памяти с готовым топ-K на узлах. Префиксное дерево строится офлайн из логов, на узлах заранее посчитан топ-K, плюс кеш популярных префиксов: ответ это поиск префикса и чтение готового списка, микросекунды, а данные обновляются периодической пересборкой.
Варианты ответа
LIKE 'prefix%' ORDER BY count DESC LIMIT 10в основной БД- Полный перебор всех запросов в памяти на каждый символ
- Загрузить все запросы на клиент и сортировать там
- Префиксное дерево в памяти с готовым топ-K на узлахправильный ответ
Разбор
Префиксное дерево строится офлайн из логов, на узлах заранее посчитан топ-K, плюс кеш популярных префиксов: ответ это поиск префикса и чтение готового списка, микросекунды, а данные обновляются периодической пересборкой. Запрос в БД на каждый символ при тысячах RPS и сортировка по счётчику дороги. Полный перебор миллионов запросов и загрузка всего на клиент не укладываются ни в задержку, ни в трафик.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.