Хеш-адресацией или хеш-индексированием называется технология быстрого прямого доступа к хранимой записи на основе значения обычного числового поля.

Всякого рода индексирование, в том числе битовые индексы, предполагают наличие ещё одного файла: для десктоповских СУБД – физического, для SQL-сервера – логического (находящегося в одном физическом). Хеширование не требует дополнительного файла.

Основные принципы хеширования

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

(Т.е. берётся какое-то поле, от значения этого поля вычисляется хеш-функция, и это значение используется в качестве адреса, и запись располагается по этому адресу.)

2. Для извлечения нужной записи: по значению хеш-поля вычисляется хеш-адрес, потом считываются данные.

Хоть и для хеширования нет дополнительного файла, но поиск через индексный файл заменяется тем, что процессор считает хеш-функцию. Но в оперативной памяти функция считается достаточно быстро, основная проблема здесь – уникальные значения. Поскольку БД стали сейчас совсем большими, то возникает проблема: при большом количестве значений начинают появляться дубли. Даже для Primary Key трудно найти функцию, которая будет работать с таким объёмом данных. Это привело к тому, что вместо хеш-функции используется b3-дерево, где научились уходить от проблем.

Недостатки:
1. Неэффективное использование дискового пространства: адрес зарезервирован, а значения в полях никак не попадают в такие значения, в которые надо поместить запись по этому адресу. Некоторые адреса могут оставаться пустыми.

2. Есть вероятность возникновения КОЛЛИЗИЙ (когда 2 или > записи надо разместить по одному адресу).

Коллизии научились обходить:
1) Одним из способов борьбы с коллизиями является использования значения хеш-функции не в качестве адреса, а в качестве АДРЕСА ПРИВЯЗКИ, т.е. некоторой цепочки указателей; внутри цепочки производится потом дополнительный поиск в оперативной памяти. Фактически, для хорошей работы хеширования необходимо сначала рассчитать, какой размер таблицы и значений там будет. Например, перечень городов.

2) Второй способ – использование РАСШИРЯЕМОГО (или динамического) хеширования: доступ к диску разбивается как бы на 2 части. При этом необходимо, чтобы значения в хеш-поле были уникальными или поле ключевым.

Основные принципы расширяемого хеширования:
Хранимый файл всегда имеет связанный с ним каталог, он состоит из заголовка, содержащего d значений, где d – глубина каталога, соответственно 2d указателей на страницы с несколькими записями на каждой. Таким образом, с помощью d значений можно организовать доступ к 2d страницам. В результате вычисления хеш-функции получается несколько бит псевдокода s, первые d бит рассматриваются как указатель на страницу, остальные используются для поиска записи на странице. Т.о. на одной странице могут появляться эти КОЛЛИЗИИ.

Основные проблемы расширяемого хеширования появляются при добавлении новых записей и особенно тогда, когда страница переполнена, следовательно, d надо менять. Если предусмотреть, что d взято с запасом, то особых проблем не будет.

Комментарии запрещены.