Что лучше использовать для индексации даты: хэш или дерево и почему

Что проверяют

Понимаете ли вы, что тип индекса диктуется формой запросов, а не типом колонки. Дату почти всегда спрашивают диапазоном, и кандидат, отвечающий «хэш быстрее, у него O(1)», показывает, что смотрит на сложность в вакууме.

Как отвечать

Дерево. Обосновать через операции, которые реально нужны по дате:

• B-дерево держит ключи упорядоченно, поэтому BETWEEN, >=, ORDER BY created_at DESC LIMIT 50 и поиск последней записи идут по индексу;
• хэш умеет только равенство. Запрос «все заказы за март» по нему невозможен, останется полный скан;
• у хэш-индекса в PostgreSQL нет ни составного ключа, ни поддержки уникальности, ни сортировки, то есть сценариев у него остаётся один;
• у дерева предсказуемый худший случай O(log n), а O(1) у хэша амортизированный и портится коллизиями и перестройкой таблицы.

Хорошая добавка: если строки приходят по времени и физически лежат в порядке даты, для большой таблицы уместен BRIN. Он занимает килобайты вместо гигабайт и закрывает ровно диапазонные запросы.

В самой программе логика та же: dict для точного ключа, отсортированный список и bisect для диапазона.

Где спотыкаются

Оборачивают колонку функцией. Условие вида WHERE date(created_at) = ... обычный индекс по created_at не использует, нужны границы суток диапазоном либо функциональный индекс.

Второе: путают тип и точность. Хранят момент времени, сравнивают с датой и теряют записи на границе суток, а если колонка ещё и с часовым поясом, границы разъезжаются у разных пользователей.

Третье: считают индекс бесплатным. Каждый индекс замедляет вставку и занимает место, а на маленькой таблице или на неселективном условии планировщик его всё равно не возьмёт и пойдёт последовательным чтением.