Внутренняя структура БД. Расстановка (хеширование) записей

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

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

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

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

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

1-я новая запись à Кл₁ à h(Кл₁) = n à добавление новой записи по соотв. адресу.

M-я старая запись à Кл_М à h(Кл_М) = k à считывание записи по соотв. адресу.

Функция должна удовлетворять требованиям:

- ее результат должен находиться в пределах диапазона адресов области памяти, выделяемой под данные;

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

Основная проблема хеширования – появление одинаковых значений хеш-сверток при разных значениях ключевых полей.

Такие ситуации называются коллизиями.