33.1 Один оператор - одна задача
B-tree поддерживает <, <=, =, >=, > и выдаёт данные
отсортированными. Hash поддерживает только =. Это не недостаток,
а специализация: если запрос всегда WHERE key = значение и ни
диапазоны, ни сортировка не нужны, всё, кроме равенства, в B-tree -
лишний вес.
Идея hash проста: применить хеш-функцию к ключу и по результату сразу прыгнуть в нужное место, без спуска по уровням дерева. Поиск - это вычисление хеша и одно-два обращения к странице, а не log-уровней. Какой оператор какой AM поддерживает, помнишь из operator-classes: для hash в opclass есть только стратегия равенства.
33.2 Устройство: бакеты, переполнение, битовая карта
Hash-индекс собран из четырёх видов страниц:
| Страница | Роль |
|---|---|
| meta | служебная: число бакетов, маски, статистика |
| bucket | основная корзина для диапазона хешей |
| overflow | продолжение бакета, когда он переполнился |
| bitmap | учёт свободных overflow-страниц |
Хеш ключа (4 байта) определяет, в какой бакет попадёт запись.
Внутри бакета хранятся хеш-коды и ctid на строки. Если в один
бакет попало больше записей, чем влезает на страницу, заводится
overflow-страница, прицепленная к бакету. Bitmap-страницы помнят,
какие overflow-страницы свободны для переиспользования.
33.3 Линейное расширение
Когда записей становится много, число бакетов растёт - но не удвоением сразу, а постепенно, по одному бакету за раз (линейное хеширование). Это сглаживает рост: не нужно разом перестраивать половину индекса, расширение размазано во времени.
При расширении часть записей из старого бакета переезжает в новый по уточнённой маске хеша. Для пользователя это незаметно - индекс сам поддерживает разумную заполненность бакетов, чтобы overflow-цепочки не разрастались и поиск оставался коротким.
33.4 Что изменилось в PostgreSQL 10
Долгое время hash-индексы не рекомендовали, и по серьёзной причине: до PostgreSQL 10 они не писались в WAL. Это значит, что после сбоя hash-индекс мог оказаться повреждённым и не восстанавливался при recovery, и его не реплицировали на standby. По сути он был небезопасен в продакшене.
В PostgreSQL 10 hash-индексы стали полноценно журналируемыми: они переживают сбой и реплицируются, как B-tree. С этого момента ими можно пользоваться всерьёз. Если встречаешь старый совет «не используй hash» - он про эпоху до 10; на PostgreSQL 17 это ограничение давно снято.
33.5 Hash против B-tree
На чистом равенстве hash и B-tree сопоставимы, и выбор тонкий.
CREATE INDEX b_idx ON big USING btree (id);
CREATE INDEX h_idx ON big USING hash (id);
\di+ b_idx
\di+ h_idx
Hash хранит только хеш-коды фиксированной длины, поэтому на длинных
ключах (длинный текст) он может быть компактнее B-tree, который
хранит сами значения. На коротких ключах разница невелика, а B-tree
выигрывает универсальностью. Практическое правило: бери B-tree по
умолчанию; hash рассматривай, только когда запрос строго = по
длинному ключу и сортировка/диапазоны заведомо не понадобятся.
Сравнение - в hash-index.
33.5.1 Подводный камень: чего hash не умеет
Прежде чем менять B-tree на hash, проверь, что не нужно ничего из следующего - hash не делает этого в принципе:
- диапазоны (
<,>,BETWEEN) - только равенство; - сортировку (
ORDER BY) - порядок хеша не связан с порядком значений; - многоколоночность - hash строится по одной колонке;
- поиск по префиксу (
LIKE 'abc%') - это тоже про порядок.
Стоит запросам однажды захотеть диапазон или сортировку - и hash бесполезен, придётся добавлять B-tree рядом. Поэтому в большинстве случаев проще сразу взять B-tree: он покрывает и равенство, и всё остальное. Hash - это осознанный выбор под узкий профиль нагрузки.
Уроки в sandbox
lab-33.1. Сравнить hash и B-tree на равенстве
Построим оба индекса на одной колонке и сравним размер и план для
=. Перед \di+ предскажи, какой индекс окажется компактнее.
Создай таблицу:
CREATE TABLE big AS SELECT g AS id, md5(g::text) AS h FROM generate_series(1, 500000) g;.Построй оба индекса по текстовой колонке:
CREATE INDEX b_h ON big USING btree (h); CREATE INDEX g_h ON big USING hash (h); ANALYZE big;.Сравни размеры:
\di+ b_hи\di+ g_h(или через pg_relation_size). Запиши, какой меньше.Проверь план равенства:
EXPLAIN SELECT * FROM big WHERE h = md5('42');- используется индексный доступ.Попробуй диапазон:
EXPLAIN SELECT * FROM big WHERE h > 'a';- hash тут бесполезен, нужен btree. Объясни почему.
sandbox с автопроверкой - открыть в песочнице
Резюме
- Hash-индекс поддерживает только оператор равенства и ищет по хешу за одно-два обращения, без спуска по дереву.
- Устройство: meta, bucket, overflow и bitmap страницы; 4-байтный хеш ключа определяет бакет, переполнение уходит в overflow-страницы.
- Число бакетов растёт линейным хешированием - постепенно, по одному, без разовой перестройки половины индекса.
- До PostgreSQL 10 hash не писался в WAL (небезопасен после сбоя); с PG10 он полноценно журналируется и реплицируется.
- На длинных ключах hash может быть компактнее B-tree (хранит хеши, не значения); на коротких разница мала.
- Hash не умеет диапазоны, сортировку, многоколоночность и префиксный поиск - стоит им понадобиться, нужен B-tree.
- По умолчанию бери B-tree; hash - осознанный выбор под строго равенство по длинному ключу без потребности в порядке.
Контрольные вопросы
Почему hash-индекс не ускоряет `WHERE id > 100`?
Показать ответ
Потому что hash хранит записи по хешу ключа, а порядок хешей никак не связан с порядком значений: близкие значения попадают в произвольные бакеты. Диапазонный запрос требует найти все значения больше границы, то есть пройти по порядку - а hash порядок не сохраняет. Его operator class содержит только стратегию равенства. Для диапазонов и сортировки нужен B-tree, который хранит ключи упорядоченно.
Почему раньше советовали не использовать hash-индексы?
Показать ответ
Потому что до PostgreSQL 10 hash-индексы не писались в WAL. Это делало их небезопасными: после сбоя индекс мог быть повреждён и не восстанавливался при recovery, и его не реплицировали на standby. В PostgreSQL 10 hash стали полноценно журналируемыми - они переживают сбой и реплицируются, как B-tree. Старый совет «не используй hash» относится к эпохе до 10; на PostgreSQL 17 это ограничение снято.
В каком случае hash реально компактнее B-tree?
Показать ответ
Когда ключ длинный - например, длинная текстовая строка. B-tree хранит сами значения ключей, а hash - только их 4-байтные хеш-коды фиксированной длины. На длинных ключах это даёт заметную экономию места. На коротких ключах (например, int) разница невелика, и универсальность B-tree обычно перевешивает. Поэтому hash имеет смысл рассматривать прежде всего для равенства по длинному ключу.
Что значит «линейное расширение» бакетов?
Показать ответ
Это способ наращивать число бакетов постепенно, по одному за раз, а не удваивая разом. При росте данных hash добавляет по одному новому бакету и переселяет в него часть записей из старого по уточнённой маске хеша. Это размазывает работу по расширению во времени: не нужно одномоментно перестраивать половину индекса. Для пользователя процесс незаметен, а заполненность бакетов остаётся разумной, чтобы overflow-цепочки не разрастались.
Когда осознанно выбрать hash вместо B-tree?
Показать ответ
Когда запросы к колонке строго равенство (
=), сортировка и диапазоны по ней заведомо не понадобятся, колонка одна (не составной индекс), а ключ достаточно длинный, чтобы hash дал экономию места. Это узкий профиль. Во всех остальных случаях B-tree предпочтительнее: он покрывает равенство не хуже и вдобавок диапазоны, сортировку и префиксный поиск, поэтому остаётся выбором по умолчанию.