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

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

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

Основные компоненты хэш-индекса

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

    *   **Детерминированной**: одинаковый ключ всегда даёт одинаковый хеш.
    *   **Равномерно распределяющей**: минимизирует коллизии.
    *   **Вычислительно эффективной**.
    *   Пример простой хеш-функции для строк в PHP (для иллюстрации):

function simpleStringHash($key, $tableSize) {
    $hash = 0;
    for ($i = 0; $i < strlen($key); $i++) {
        $hash = ($hash * 31 + ord($key[$i])) % $tableSize;
    }
    return $hash;
}

• Хеш-таблица (массив ячеек): Это массив фиксированного или динамически изменяемого размера, где каждая ячейка (или "bucket") может хранить одну или несколько записей. Индекс вычисляет хеш ключа, который определяет номер ячейки.

• Механизм разрешения коллизий: Когда два разных ключа дают одинаковый хеш (коллизия), необходимо решить, где хранить вторую запись. Основные методы:

    *   **Цепочки (chaining)**: Каждая ячейка содержит список (например, связный список) всех записей с одинаковым хешем.
    *   **Открытая адресация (open addressing)**: Если ячейка занята, алгоритм ищет следующую свободную ячейку согласно определённой стратегии (линейный поиск, двойное хеширование).

Алгоритм работы с хэш-индексом

1. Вставка (INSERT):

    *   Хеш-функция вычисляет хеш от ключа новой записи.
    *   Определяется номер ячейки (например, `хеш % размер_таблицы`).
    *   Запись помещается в эту ячейку. Если используется метод цепочек, запись добавляется в список этой ячейки.

1. Поиск по точному ключу (SELECT WHERE key = value):

    *   Хеш-функция вычисляет хеш от поискового ключа.
    *   Определяется номер ячейки.
    *   Происходит поиск записи внутри этой ячейки (например, линейный поиск по списку в случае цепочек). Это операция **O(1)** в среднем случае при хорошей хеш-функции и отсутствии большого числа коллизий.

1. Удаление (DELETE):

    *   Аналогично поиску: находится ячейка и конкретная запись внутри нее, затем удаляется.

Пример упрощенной реализации в контексте базы данных

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

class HashIndex {
    private $hashTable = [];
    private $size;

    public function __construct($size) {
        $this->size = $size;
        $this->hashTable = array_fill(0, $size, []); // Инициализируем ячейки как пустые списки (цепочки)
    }

    private function hash($key) {
        return crc32($key) % $this->size; // Используем CRC32 как пример хеш-функции
    }

    public function insert($key, $dataPointer) {
        $index = $this->hash($key);
        $this->hashTable[$index][] = ['key' => $key, 'pointer' => $dataPointer];
    }

    public function find($key) {
        $index = $this->hash($key);
        foreach ($this->hashTable[$index] as $entry) {
            if ($entry['key'] == $key) {
                return $entry['pointer']; // Возвращаем указатель на данные в основной таблице
            }
        }
        return null; // Не найдено
    }
}

// Использование
$index = new HashIndex(100);
$index->insert('user_123', 'адрес_в_хранилище_данных');
$pointer = $index->find('user_123'); // Быстро получаем адрес данных

Особенности и ограничения хэш-индексов

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

    *   **Сверхбыстрый поиск по точному ключу** в среднем случае (O(1)).
    *   Простая концепция.

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

    *   **Не поддерживает диапазонные запросы или частичные совпадения** (например, `WHERE key > 10` или `LIKE 'A%'`). Для этого нужны другие индексы (B-tree).
    *   **Коллизии** могут снижать производительность, превращая поиск в O(n) внутри одной ячейки.
    *   **Динамическое расширение** (рехеширование) может быть дорогостоящей операцией при увеличении таблицы.
    *   В большинстве реальных систем (например, MySQL, PostgreSQL) хэш-индексы используются **в памяти** или для специфических случаев, поскольку **B-tree индексы** более универсальны и эффективны для диапазонных запросов и сортировки.
    *   **Неэффективен для сортировки данных** или получения их в порядке ключа.

В заключение, хэш-индекс — это мощный инструмент для точного поиска, работающий как ассоциативная карта, переводящая ключ в адрес данных через хеш-функцию. Однако его применимость в базах данных ограничена из-за отсутствия поддержки операций с диапазонами, что делает B-tree более популярным выбором для большинства сценариев использования индексов в SQL-базах.