Hash-индекс — когда использовать, какие операции поддерживает (только equality)?

Hash-индекс основан на хеш-таблицах и обеспечивает константное время доступа O(1) для операций поиска точных совпадений.

Принцип работы hash-индекса:

1. Структура:

   • Хеш-таблица с массивами бакетов

   • Хеш-функция преобразует ключ в номер бакета

   • Каждый бакет содержит указатели на данные

2. Процесс поиска:

   • Вычисление хеша от искомого значения

   • Определение номера бакета

   • Поиск в цепочке бакета

   • Возврат найденных записей

Поддерживаемые операции:

• Равенство: =

• Список значений: IN

• Проверка на NULL: IS NULL (зависит от реализации)

Неподдерживаемые операции:

• Диапазоны: >, <, BETWEEN

• Сортировка: ORDER BY

• Поиск по префиксу: LIKE 'abc%'

• Частичное совпадение

Пример использования в MySQL:

-- Создание таблицы с hash-индексом
CREATE TABLE users (
    id INT PRIMARY KEY,
    email VARCHAR(255),
    INDEX idx_email_hash USING HASH (email)
);

-- Эффективные запросы
SELECT * FROM users WHERE email = 'user@example.com';
SELECT * FROM users WHERE id IN (1, 2, 3);

-- Неэффективные запросы
SELECT * FROM users WHERE email > 'a';
SELECT * FROM users WHERE email LIKE 'user%@%';

Когда использовать hash-индекс:

1. Идеальные сценарии:

   • Поиск по первичному ключу

   • Уникальные идентификаторы (UUID, email)

   • Точные совпадения в словарях

   • Кэширование часто запрашиваемых значений

2. Плохие сценарии:

   • Диапазонные запросы

   • Сортировка результатов

   • Частичные совпадения

   • Частые обновления данных

Сравнение с B-tree:

Преимущества hash-индекса:

• Быстрее для точных совпадений (O(1) vs O(log n))

• Проще структура данных

• Эффективнее по памяти в некоторых случаях

Недостатки hash-индекса:

• Не поддерживает диапазонные запросы

• Чувствителен к коллизиям хешей

• Требует перестройки при изменении размера

• Не сохраняет порядок данных

Реализация в разных СУБД:

• MySQL: поддерживает HASH для MEMORY таблиц

• PostgreSQL: имеет специализированные hash-индексы

• Oracle: использует hash-кластеры

• SQL Server: не имеет нативных hash-индексов