В учебниках по СУБД hash-индекс показывают одним из первых: «вычислил хэш ключа, нашёл бакет, прочитал список — готово, O(1)». Поэтому когда люди узнают, что в PostgreSQL по умолчанию все индексы — B-tree, многих это удивляет. Где же легендарный hash?

Он есть. Но история у него непростая.

Долгое возвращение из ада

С первых версий PostgreSQL поддерживал CREATE INDEX ... USING HASH. Но был один критический недостаток: hash-index не писался в WAL. Это значит:

• После crash recovery индекс мог оказаться повреждённым.
• Streaming replication его не передавала — на slave его просто не было.
• pg_dump его сохранял, а вот синхронный replay — нет.

Поэтому в документации висело предупреждение красным: «использовать на свой страх и риск, мы рекомендуем B-tree». В Postgres 10 (2017) Hash наконец получил WAL-логирование. С тех пор это полноценный, безопасный, реплицируемый тип индекса.

Структура: бакеты и переполнение

Hash-индекс хранит только хэш (4 байта) и tid (6 байт), не само значение. Это его сила и слабость одновременно:

• Плюс: записи маленькие. На колонке с длинными значениями (URL, email длиной 100+ байт) hash-index радикально меньше B-tree.
• Минус: индекс не способен проверить точное равенство — только то, что хэши совпали. Финальную проверку делает heap. Если есть коллизия — лишний disk read.

И, главное: hash-индекс умеет только =. Никаких <, >, BETWEEN, ORDER BY, LIKE 'prefix%', никаких составных ключей. Только точное равенство одного скаляра.

Сравним с B-tree на длинной колонке

Возьмём customers.email — текстовая колонка из примерно 25 символов.

Hash оказывается компактнее на длинных ключах. На коротких (int, bigint) разница минимальна или обратна — B-tree выигрывает.

В реальности B-tree-lookup на equality стоит 3 уровня дерева ≈ 3 page reads. Hash lookup — 1 page read для основного бакета + 0-2 для overflow. На single equality hash может быть быстрее на 20-50%.

Insert и update

Hash-индекс на insert: вычисли hash, проверь не переполнен ли бакет (если да — split bucket), запиши. Без перебалансировки дерева, без логарифмических page reads на верхних уровнях.

B-tree на insert: пройди от root до leaf (3-4 страницы), вставь, при переполнении leaf — split + апдейт parent (потенциально каскадный).

Для INSERT-heavy сценариев hash на equality-индексе может быть на 10-30% быстрее. Но Postgres 16+ настолько хорошо оптимизировал B-tree (deduplication, page split optimization), что преимущество стало размытым.

Сравнение размера на uuid

UUID — 16-байтный тип, хеш от него (4 байта) короче. На большой таблице с миллионами UUID hash-индекс может дать заметную экономию.

Hash на UUID обычно даёт 30-40% экономии по сравнению с B-tree. На 100M строк это означает несколько гигабайт. Но это работает только если строго нужны equality lookups — на UUID почти всегда так и есть, но проверь дважды.

Сравним insert-нагрузку

В реальной 16+ Postgres B-tree оптимизирован настолько хорошо, что разница на insert часто в пределах 10-20%. Раньше, до Postgres 13, hash был ощутимо быстрее на bulk-insert, но deduplication B-tree сильно сгладило преимущество.

Когда брать Hash, а когда B-tree

Бери Hash, если:

• Колонка длинная (TEXT, URL, JSONB-ключ через expression index).
• Доступ строго WHERE col = X (одиночный, не диапазон, не сортировка).
• Не нужны составные индексы (hash их не поддерживает).
• Нужна максимальная компактность индекса.

Оставь B-tree, если:

• Хоть иногда нужен ORDER BY или BETWEEN.
• Хочешь UNIQUE constraint (hash не поддерживает уникальность напрямую).
• Хочешь partial / multi-column / expression индексы.
• Тебе нужны IN (...) лучше планируемые (B-tree их склейку умеет).

Подводный камень: автовакуум hash-индексов был долго менее оптимальным. На сильно изменяющейся таблице B-tree обновляется чище. С Postgres 14+ это в основном выправлено.

Альтернатива: hash через выражение в B-tree

Если ты хочешь иметь компактный индекс по длинной строке и при этом не отказываться от UNIQUE / partial / composite, есть альтернатива:

CREATE INDEX customers_email_btree_md5
  ON customers (md5(email));

-- Запрос:
SELECT id FROM customers WHERE md5(email) = md5('[email protected]');

Это expression index на B-tree. Записи в индексе короткие (16 байт), но это всё ещё B-tree со всеми его фичами. Минус — нужно везде писать md5(...) в WHERE; забыл — Seq Scan.

Современный совет в большинстве случаев: используй B-tree. Hash оправдан в узких сценариях (длинный текстовый ключ + миллиарды строк + только equality), и даже там разница в проценте ускорения часто не оправдывает риск операционных сюрпризов.

Внутри: linear hashing и split

Hash-индекс в Postgres использует алгоритм linear hashing (Litwin, 1980). Идея: количество бакетов растёт линейно, по одному за раз, без полного перестроения. Когда заполняемость превышает порог (fillfactor, по умолчанию 75%), берётся один бакет (по специальному порядку, начиная с нулевого), и его содержимое разделяется между ним и новым бакетом-«близнецом».

Это даёт два следствия:

1. Insert амортизированно O(1), но индивидуальные insert’ы могут быть дороже из-за split.
2. Bucket pages имеют overflow chain (если split не успевает) — поиск в худшем случае линейно проходит по chain.

В EXPLAIN это не видно прямо, но можно смотреть pg_stat_user_indexes.idx_scan и idx_tup_fetch — если на hash-индексе отношение fetch / scan велико (намного больше единицы), значит ходим по длинным overflow chain — пора REINDEX или поднять fillfactor.

REINDEX для hash

Hash-индексы исторически чаще требуют REINDEX, чем B-tree. Причины:

• Split при insert амортизированно работает, но при потоковой нагрузке overflow chains могут отрастать.
• VACUUM очищает мёртвые tid в hash-индексе менее агрессивно (это улучшилось в Postgres 13+, но всё ещё медленнее).

В production, если используешь hash-индексы, имеет смысл раз в неделю/месяц делать REINDEX INDEX CONCURRENTLY для критичных индексов.

Мониторинг hash-индексов

Полезные системные функции (расширение pageinspect):

SELECT * FROM hash_metapage_info(get_raw_page('sessions_token_hash', 0));
-- покажет magic, version, ntuples, ffactor, bsize, ovflpoint

Что смотреть:

• bucket fill ratio (ntuples / nbuckets): если выше 1.5x от ffactor — поиск ходит по overflow chains.
• ovflpoint растущий быстро — индекс «фрагментируется», пора REINDEX CONCURRENTLY.
• В pg_stat_user_indexes отношение idx_tup_fetch / idx_scan > 1.5 на equality-индексе — overflow chains или коллизии.

В отличие от B-tree, hash не подсвечивается так детально в стандартных мониторингах (Grafana, pganalyze) — придётся писать кастомные запросы.

Связь с hash join

Не путай hash index с hash join — это разные вещи. Hash join — это алгоритм соединения двух таблиц через построение хэш-таблицы в памяти на лету. Он использует hash-функции, но индекс при этом — обычный B-tree или вообще без индекса. Hash join не нуждается в hash-индексе и не выигрывает от него.

То же про hash partitioning: разделение таблицы по hash(col) — это feature партиционера, не индекса.

Hash index применим только к равенству на одной колонке индексированной таблицы.

Чек-лист

• Hash index — CREATE INDEX ... USING HASH. Только equality. Записи: 4-байт хэш + 6-байт tid.
• До Postgres 10 был crash-unsafe (no WAL). С 10-й версии — полноценный.
• На длинных ключах меньше B-tree, на коротких — сопоставим или хуже.
• Не поддерживает UNIQUE, ORDER BY, range, multi-column, partial expression — только одиночный equality.
• Insert немного быстрее B-tree, но Postgres 16+ догнал.
• Альтернатива: B-tree на md5(col) / hashtext(col) — компактно и сохраняет фичи B-tree.
• В 99% случаев выбирай B-tree. Hash — оптимизация для узких сценариев.