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

Question

Hash-индекс использует хеш-таблицу для быстрого поиска точных совпадений и поддерживает только операции равенства (=, IN). Он не подходит для диапазонных запросов, сортировки или операций "больше/меньше". Hash-индекс эффективен для точечных запросов с уникальными значениями, таких как поиск по первичному ключу или уникальным идентификаторам, где требуется максимальная скорость поиска точных совпадений.

YeaHub · Accepted Answer

Hash-индекс основан на хеш-таблицах и обеспечивает константное время доступа O(1) для операций поиска точных совпадений.Принцип работы hash-индекса:Структура:Хеш-таблица с массивами бакетовХеш-функция преобразует ключ в номер бакетаКаждый бакет содержит указатели на данныеПроцесс поиска:Вычисление хеша от искомого значенияОпределение номера бакетаПоиск в цепочке бакетаВозврат найденных записейПоддерживаемые операции:Равенство: =Список значений: 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-индекс:Идеальные сценарии:Поиск по первичному ключуУникальные идентификаторы (UUID, email)Точные совпадения в словаряхКэширование часто запрашиваемых значенийПлохие сценарии:Диапазонные запросыСортировка результатовЧастичные совпаденияЧастые обновления данныхСравнение с B-tree:Преимущества hash-индекса:Быстрее для точных совпадений (O(1) vs O(log n))Проще структура данныхЭффективнее по памяти в некоторых случаяхНедостатки hash-индекса:Не поддерживает диапазонные запросыЧувствителен к коллизиям хешейТребует перестройки при изменении размераНе сохраняет порядок данныхРеализация в разных СУБД:MySQL: поддерживает HASH для MEMORY таблицPostgreSQL: имеет специализированные hash-индексыOracle: использует hash-кластерыSQL Server: не имеет нативных hash-индексов