ГЛАВА 17. АДРЕСАЦИЯ ДАННЫХ В ПАМЯТИ ЭВМ ПО СОДЕРЖИМОМУ

17.1. Методы адресации данных при однозначном соответствии ключей и адресов

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

где А — адрес элемента данных;/— адресная функция; К— ключ записи.

Классификация методов адресации данных по содержимому представлена на рис. 17.1.

Рис. 17.1. Классификация методов адресации данных по содержимому

220

Методы однозначного соответствия ключей и адресов наибо­лее просты и легко реализуемы. Они обеспечивают определенную упорядоченность записей в файле. Адресная функция выбирается разработчиком БД и представляет собой зависимость, связыва­ющую значение ключа К и адрес А. Следует особо отметить, что для рассматриваемых методов адресная функция задает взаимноодноз­начное соответствие между множествами возможных значений

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

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

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

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

Пример. В базе данных «КАДРЫ» в качестве ключа используется поле «КОДСОТРУДНИКА», значения которого состоят из трех символов — буквы и двух цифр (например, И6 — код сотрудника Иванова). Будем считать, что фамилии сотрудников могут начинаться с 30 букв (за ис­ключением букв «ъ», «ы», «ь»). Множество возможных значений ключей составят следующие значения:

221

Будем считать, что буква кодируется числом от 1 до 30 (А — 1; Б — 2;... Я — 30). Тогда адресная функция имеет вид

А_от = (КОД_БУКВЫ - 1)100 + ЦИФРЫ_КОДА_СОТРУДНИКА,

где А_отп — относительный адрес; A_UW1 — машинный адрес; m — длина записи; b — адрес базы.

Очевидно, Что многие записи в таком файле окажутся пустыми. Об­щее количество записей будет составлять 3 000 шт.

Если в организации служат 300 сотрудников, 90 % записей окажутся пустыми.

Рассмотрим еще один пример.

Пример. Файл данных о продаже авиабилетов имеет логическую струк­туру: {HP; ДВ; НСМ} (номер рейса; дата вылета; наличие свободных мест). Первичный ключ такой записи составляют первые два поля. Пусть номер рейса меняется от 01 до 50; дата вылета — от 001 до 366; размер записи — 20 байт. Структура ключа записи и адреса записей будут иметь вид:

 

HP	ДВ	Относительный адрес
01	001	0
02	001	]
50	001	49
01	366	365-50
02	366	365 50+1
50	366	365-50 + 49

Тогда адресная функция имеет вид:

Достоинства этого метода очевидны — это простота и высокая скорость поиска. Недостаток метода также понятен: малое запол­нение памяти, отведенной для хранения файла. Действительно, если бы номера рейсов могли принимать значения от 0001 до 9 999 (как в действительности и бывает), то первичный ключ изменял­ся бы от 0 001 001 до 9 999 366 и нужно было бы 9 999 • 366 = 3 659 634 участков памяти.

Если же аэропорт в день обслуживает 50 рейсов (что реально для многих аэропортов), то реально нужны всего 18 300 участков

222

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

Пример. Пусть файл «ОКЛАДЫ» в БД «КАФЕДРА» содержит инфор­мацию о вакантных местах работы на кафедре и имеет поля: должность; ученая степень; ученое звание и тарифный разряд сотрудника. Будем счи­тать, что на кафедре имеются вакантные должности старшего научного сотрудника, преподавателя, старшего преподавателя, доцента.

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

Например, для старшего научного сотрудника:

 

ДОЛЖНОСТЬ	УЧЕНАЯ^СТЕПЕНЬ	УЧЕНОЕ_ЗВАНИЕ
Старший научный сотрудник	Нет	Нет
Старший научный сотрудник	Нет	Есть
Старший научный сотрудник	Есть	Нет
Старший научный сотрудник	Есть	Есть

Для преподавателя:

 

ДОЛЖНОСТЬ	УЧЕНАЯ__СТЕПЕНЬ	УЧЕНОЕ_ЗВАНИЕ
Преподаватель	Нет	Нет
Пре подаватель	Нет	Есть
Преподаватель	Есть	Нет
Преподаватель	Есть	Есть

и далее для старшего преподавателя и доцента.

Если ввести поле «КОДЛОЛЖНОСТИ», можно записать:

 

ДОЛЖНОСТЬ	КОД__ДОЛЖНОСТИ
Старший научный сотрудник	1
Преподаватель	2
Старший преподаватель	3
Доцент	4

223

Тогда легко составить таблицу соответствия:

 

код_должности	УЧЕНАЯ_СТЕПЕНЬ	УЧЕНОЕ_ЗВАНИЕ	А ^отн
1	0	0	0
1	0	1	1
1	1	0	2
1	1	1	3
2	0	0	4
2	0	1	5
4	1	1	15

Адресная функция имеет вид:

А™ = (КОД_^ЦОЛЖНОСТИ - 1)4 + УЧЕНАЯ_СТЕПЕНЬ 2 + + УЧЕНОЕ_ЗВАНИЕ.

Таким образом для старшего преподавателя, имеющего ученое зва­ние, но не имеющего ученой степени, аргументом адресной функции будет:

 

код_должности	УЧЕНАЯ_СТЕПЕНЬ	УЧЕНОЕ_ЗВАНИЕ
3	1	0

Относительный адрес такой записи равен 10.

⇐ Предыдущая33343536373839404142Следующая ⇒

Поделиться: