Как устроен хэш-индекс в базах данных?

Хэш-индекс — это структура данных, основанная на хэш-таблице, которая позволяет выполнять поиск по ключу за время, близкое к O(1). Он работает следующим образом:

Принцип работы:

1. Хэширование ключа: Значение ключа (например, user_id) пропускается через хэш-функцию (например, crc32, murmurhash).
2. Определение позиции: Полученное хэш-значение (или его остаток от деления на размер таблицы) указывает на слот (bucket) в массиве, где хранится указатель на данные.
3. Разрешение коллизий: Если разные ключи дают одинаковый хэш (коллизия), используются методы:
   • Метод цепочек: Каждый слот содержит связный список записей.
   • Открытая адресация: Запись помещается в следующий свободный слот по определенному алгоритму (линейное/квадратичное пробирование).

Пример структуры (упрощенно):

-- Представление хэш-индекса для таблицы users по id
-- Хэш-функция: hash(id) % 3
Bucket 0: -> [id: 3, name: 'Alice'] -> [id: 6, name: 'Charlie'] (цепочка)
Bucket 1: -> [id: 1, name: 'John']
Bucket 2: -> [id: 2, name: 'Jane'] -> [id: 5, name: 'Bob']

Преимущества:

• Сверхбыстрый поиск по точному совпадению ключа.
• Эффективен для операций = и IN.

Недостатки и ограничения:

• Не поддерживает диапазонные запросы (BETWEEN, >, <, LIKE 'prefix%'). Данные не упорядочены.
• Требует обработки коллизий, что может деградировать до O(n) в худшем случае.
• Размер таблицы часто фиксирован или требует дорогостоящего ресайзинга (rehashing).
• Неэффективен для частичных ключей или ключей, которые часто обновляются.

Применение: Хэш-индексы идеальны для кэшей в памяти (например, MEMORY таблицы в MySQL, словари), для индексации временных данных или в системах, где критичен поиск по первичному ключу, а диапазонные запросы не нужны.