Файл: Левковиц, Д. Структуры информационных массивов оперативных систем.pdf

память может

быть вызвано в зависимости от

разме ­

ра логической

записи несколько Элементов

и д а ж е

записи

могут быть вызваны из З У П Д с помощью

груп­

повых

операций. Второе обращение необходимо

только

даче

о выдаче

ежемесячных

накладных

по

данному

счету принять, что оперативная

система

хранит

сведе­

ния

о накладных, с к а ж е м ,

за

год, то подзапись

наклад ­

ной

д о л ж н а содержать 12

Элементов Н а к л а д н о й .

Если

предварительное

распределение

памяти,

образующее

зации

объема памяти

система

д о л ж н а

о б л а д а т ь

способ­

ностью

динамически

генерировать

новые

объемы дл я

записи

продолжений.

З а ш т р и х о в а н н ы е области

рис. 3-3

и 3-4 содержат

управляющую информацию дл я ассоциативных

связей

между

данными и все поля

данных,

п р и н а д л е ж а щ и х

Элементам. Н а рис. 3-5 и з о б р а ж е н

обобщенный

формат

для этой области Элементарной записи.

С о д е р ж а щ а я с я

запросу, в то время как данные печати проходят

через

различные процедуры

обработки, определяемые

кон­

кретным приложением

ка к м е ж з а п и с н а я обработка

про­

ния пользователя разница м е ж д у использованием

клю­

чей и классификаторов

несущественна,

но, как

показано

в гл. 1, система

поиска

и

размещения

обрабатывает их

по-разному. К а к ключи,

так и классификаторы,

вообще

говоря,

являются дескрипторами системного

файла .

К а ж д ы й

из них может иметь Им я (соответствующее его

признаку) и Значение. Например, Имя/Смит,

Возраст/21 .

Внутри записи ка к ключи, так и классификаторы

хра­

нятся в

общем

виде И м я

Ключа/Значение

или

И м я

К л а с с и ф н к а т о р а / З н а ч е п пе

*. В

случае ключа для каж ­

дой пары

Им я Ключа/Значение

генерируется

список или

происходит разбиение

файла .

Вообще говоря, существуют два класса

методов

орга­

низации

списковой структуры. К первому

п р и н а д л е ж а т

ото

Счет 4

0600

ИнВоп # 18

накладная/^

Страсх/о.]

Поручитель/^

ядpec связи ОЮО/у.

or,

Накладнаяы

Счет/аг

'

«2

Накладная

#2

0250

Поручитель #3

Счет/ф

Счет/ф

Суасх/у

fil

Поручитель #/

Счет//Зг

Страсх #/

Поручитель

#2

Накладиая/уц

Инбоп/у6

Счет//33

\Ддрес продолжения 0251

Страсх ъ 2

йакладиая/у5

Страсх # /

Страсх # J

Накладная/у2

Страсх

# 2

Накладная/а3

Ядрес связи 0600

Накладная/а.

Индоп/уя

Рис. 3-4. Пример

файла

с иерархическим

управле­

нием.

методы

последовательного

мультисписка

• , ко второ­

м у — м е т о д ы инвертированного

списка. В первом

случае

для образования

списка

разбиения ф а й л а

необходим

ча/Значению записывается Адрес связи,

у к а з ы в а ю щ и й

следующую запись в

З У П Д , с о д е р ж а щ у ю

то

ж е

И м я

Ключа/Значение

(или

З н а ч е н и е ) . З а п и с и

этого

списка,

вообще говоря,

физически не расположены последова­

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

образом

через адреса связи. Классификаторы не образуют

спис­

видуальные входы ( И м я

Классификатора/Значение)

внутри к а ж д о й записи. С

программной точки зрения

чей

(а не д л я классификаторов) .

В терминах

системы

с последовательным списком

такой

поиск должен

выпол­

няться д л я самого

короткого

списка

в к а ж д о й

дизъюнк ­

ции

запроса. П р и

этом предполагается, что

логическое

проса,

включающий

классификаторы,

рассматривается

только

в

момент, когда

запись списка выбирается из

З У П Д

и

переносится

в

оперативную

память

процессо­

ра. Очевидно, произвольный доступ или

просмотр списка

может

быть выполнен

только тогда,

когда в

к а ж д о й

Методы

инвертированного списка

т а к ж е

требуют

адреса связи

по ключу, но при такой

структуре

ф а й л а

у п р а в л я ю щ а я

информация списка расположена

несколь­

записей и помещены в виде компактных,

последователь­

ных списков

в другой

области З У П Д .

Таким

образом,

адреса

связи

не фигурируют внутри

записи

явно,

ка к

это

показано

на рис. 3-4, но тем не менее в системе

фай­

лов они существуют и выполняют

те ж е функции.

Следует отметить,

что в случае

запроса,

выраженно ­

го в терминах пар Имя/Значение,

система,

р а б о т а ю щ а я

со

списком,

с о д е р ж а щ и м Значения,

менее

эффективна,

чем

система

со списком пар И м я Ключа/Значение .

Сни­

жение

эффективности

происходит из-за необходимости

вести

более

длинный

поиск по списку. Однако

система

со списком Значений

более гибка,

не требует

от

пользо­

Разработчики . В той ж е

системе,

просматривая

список

Смитов и классифицируя

к а ж д у ю

запись после

ее пере­

бы найти всех Смитов только по запросу

Автор/Смит

или Главный

Разработчик/Смит, что возможно

только

в том случае,

когда

пользователь

знает,

что

Автор и

Главный Р а з р а б о т ч и к

есть имена

именно

тех

ключей,

сти, могут

оказаться

другие имена ключей, принимаю­

щие значение Смит, о которых он может не знать .

К а ж д а я

м л а д ш а я

или элементарная

запись

наряду

с Именем

элемента

обычно идентифицируется

номером

д л я доступа. Этот

номер

желательно

сделать

ключом

по длине списка с тем, чтобы поиск Элементов

можно

было производить

т а к ж е

по. номеру. Это особенно по-