Материал: Л-9 - Методы доступа к данным

Основные свойства хеш-функции (2)

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

Для реальных функций хеширования допускается совпадение значений функции h(K) для различных ключей.

Для разрешения неопределенности при совпадении адресов после вычислении h(K) используются

специальные методы.

Недостатки хеширования

Количество данных и распределение значений ключа должны быть известны заранее.

Записи обычно упорядочены по значению ключа, что приводит к дополнительным затратам при выполнении сортировки.

Преимущества хеширования

Преимущество – ускорение доступа к данным по значению ключа.

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

При этом не нужны дополнительные структуры (типа индекса) и затраты памяти на их хранение.

Использование хеширования (1)

В таблице есть уникальный ключ, и большинство запросов обращается к записям по значению этого ключа:

SELECT <список выбора>

FROM <таблица>

WHERE unique_key = <значение>;

Значение, указанное в условии, хешируется.

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

Использование хеширования (2)

Для неуникального хеш-ключа все записи с таким значением ключа помещаются в одном блоке, который также можно прочитать за один раз.

Таблица практически статична (редко обновляется).

Число записей и их средний размер можно определить заранее и сразу выделить под таблицу требуемое физическое пространство.