Что такое хэш индекс и как он работает

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

Понимаете ли вы, что индекс это не ускоритель вообще, а структура под конкретную форму запроса. У бэкендера на Node вопрос обычно вырастает из практики: запрос по равенству тормозит, и надо решить, чем его закрывать. Заодно смотрят, отличаете ли вы хэш-индекс в СУБД от хэш-таблицы в памяти процесса.

Как отвечать

Хэш-индекс не хранит ключи в порядке. Значение ключа прогоняется через хэш-функцию, её результат указывает на бакет, где лежат ссылки на строки. Поиск по равенству это одно вычисление хэша и чтение бакета, поэтому стоимость почти не зависит от размера таблицы.

Дальше сразу про ограничения, их и ждут. Хэш-индекс умеет только равенство. Ни диапазонов, ни сортировки, ни поиска по префиксу он не закрывает: порядок хэшей никак не связан с порядком значений.

CREATE INDEX idx_sessions_token ON sessions USING hash (token);

Практический вывод: B-tree закрывает и равенство, и диапазоны, поэтому дефолт это он, а хэш берут точечно, когда ключ длинный, запрос всегда по равенству и выигрыш в размере индекса заметен. В MySQL с InnoDB явно создать хэш-индекс вообще нельзя, там есть только внутренний адаптивный.

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

Говорят, что хэш-функция даёт уникальный код. Не даёт, коллизии неизбежны, и внутри бакета всё равно идёт сравнение исходных значений.

Обещают O(1) и на этом останавливаются. При перекошенном распределении бакет вырождается в длинный список, а на диске каждое обращение это ещё и чтение страницы.

Путают уровни. В Node хэш-таблица это Map или объект в памяти одного процесса: она исчезает с рестартом и не разделяется между инстансами за балансировщиком. Разгрузить базу здесь может внешний кэш вроде Redis, а не Map.