Организация данных в памяти эвм с использованием методов вычисления адреса по значениям ключей записей

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

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

Методы вычисления адреса подразделяют на две группы:

1. методы, в которых адресная функция реализует взаимно однозначное соответствие адресов и ключей;

2. методы перемешивания, в которых адресная функция реа­лизует только однозначное преобразование ключа в адрес; обрат­ное преобразование обычно не имеет места.

Методы первой группы.

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

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

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

В рассмотренных методах адресация выполняется в два этапа: вначале ключ преобразуется в относительный адрес (относитель­но начала файла), а затем относительный адрес преобразуется в машинный. Использование относительных адресов делает органи­зацию данных более гибкой.

Методы второй группы. Методы перемешивания известны так­же под названием методов хеширования, методов рассеянной па­мяти, иногда их называют методами рандомизации.

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

Таким образом, чтобы первоначально запомнить экземпляр записи, необходимо вычислить адрес хранения в памяти и поме­стить экземпляр по этому адресу. При поиске экземпляра записи выполняются те же самые вычисления и запись считывается из памяти по полученному адресу.

Рассмотренные выше методы первой группы, использующие числовое значение первичного ключа в качестве адреса хранимой записи (либо выполняющие взаимно однозначное преобразование значения ключа в адрес), можно использовать только для ограни­ченного круга приложений. В общем случае эти методы неприме­нимы потому, что диапазон значений первичного ключа обычно много шире диапазона адресов памяти, выделенных для хранения записей.

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