В чем разница между хэш-индексом и B-tree индексом?

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

Понимаете ли вы, что универсальность важнее асимптотики, и знаете ли, почему хеш-индекс применяют редко.

Как отвечать

Хеш-индекс хранит хеш значения и ссылку на строку. Поиск по равенству в среднем за постоянное время. И на этом его возможности заканчиваются.

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

Что умеет только B-дерево:

• диапазоны: >, <, BETWEEN, потому что листья связаны и читаются подряд;
• сортировка: ORDER BY по индексированной колонке идёт без отдельного шага сортировки;
• префикс строки: LIKE 'abc%';
• минимум и максимум за один спуск;
• составные индексы с поиском по первым колонкам;
• уникальность: в PostgreSQL уникальным может быть только B-дерево, хеш-индекс уникальность не поддерживает;
• чтение только по индексу: хеш хранит хеш, а не значение, поэтому до таблицы дойти придётся всегда.

Где хеш-индекс может выиграть: очень длинные ключи, где хранить значение целиком дорого, и строго поиск по равенству. Выигрыш при этом невелик.

Историческая деталь про PostgreSQL, которую полезно знать: до версии 10 хеш-индексы не журналировались, то есть не переживали сбой и не реплицировались, поэтому их прямо не рекомендовали. С версии 10 это исправлено, но привычка и малая выгода оставили их редкими.

Итог: B-дерево универсально и потому используется по умолчанию, а специализированные типы берут под конкретные задачи (GIN для полнотекстового поиска и jsonb, GiST для геометрии, BRIN для огромных таблиц с естественным порядком).

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

Считают, что O(1) автоматически лучше O(log n).

Не знают, что хеш-индекс не поддерживает сортировку и диапазоны.

Ждут от хеш-индекса уникальности.

Не могут объяснить, почему у B-дерева так мало уровней.