Чем B-tree индекс принципиально превосходит hash-индекс?
- Когда использовать hash-индекс?
- Какие типы индексов есть в PostgreSQL?
B-дерево упорядочено — поддерживает равенство, диапазоны, сортировку и префиксы строк. Hash-индекс — только равенство. Поэтому почти всегда выбирают B-дерево.
- B-дерево:
=,<,>,BETWEEN,ORDER BY,LIKE 'abc%' - Hash: только
=, чуть компактнее для длинных ключей - Специальные: GIN (массивы, JSONB, полнотекст), GiST (геометрия, диапазоны), BRIN (огромные таблицы с естественным порядком)
А ещё Hash-индексы в PostgreSQL журналируются только с версии 10
Подробно
B-дерево хранит ключи по порядку в сбалансированном дереве страниц. Поиск значения — O(log n), диапазон — найти начало и идти по листьям, сортировка — просто читать по порядку. Подходит для чисел, строк, дат, составных ключей. Вариант по умолчанию в любой СУБД.
Hash-индекс хранит хеши ключей в корзинах. Поиск по точному значению — O(1) в среднем, но порядок теряется: никаких диапазонов, сортировки, префиксов. На практике выигрыш над B-деревом невелик (несколько уровней дерева всё равно в кэше), поэтому hash выбирают редко — для очень длинных ключей, по которым ищут только на равенство. В PostgreSQL до версии 10 hash-индексы не писались в WAL и не реплицировались.
Другие типы в PostgreSQL:
- GIN — инвертированный индекс: элементы массивов, ключи JSONB, полнотекстовый поиск (
tsvector), триграммы (pg_trgmдляLIKE '%abc%'); - GiST / SP-GiST — геометрия, диапазоны, ближайшие соседи;
- BRIN — минимумы и максимумы по блокам; крошечный индекс для огромных таблиц, где данные физически упорядочены (журналы по времени);
- частичные (
WHERE status = 'active') и функциональные (lower(email)) индексы.
Что хотят услышать
- Ключевое различие: упорядоченность.
- Какие операции поддерживает каждый.
- Почему по умолчанию B-дерево.
- Специальные типы индексов — плюс.
Частые ошибки
- Считать hash-индекс всегда быстрее.
- Пытаться ускорить
LIKE '%abc%'обычным B-деревом.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✗Гарантирует уникальность значений столбца и не допускает дубликатов
- ✓Поддерживает диапазоны и сортировку, а не только равенство
- ✗Быстрее hash-индекса на точном равенстве и занимает меньше места на диске
- ✗Не требует обновления структуры при вставке новых строк в таблицу
Что спросят дальше
- Что такое covering index?
- Когда индекс по равенству выгоднее B-tree?
Разбор темы
- Индексы и планы запросов
Устройство B-tree, hash vs B-tree, составной и covering индекс, цена записи и когда индекс не используется.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.