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

пись файла,

с о д е р ж а щ а я

этот

ключ,

определяется

с помощью

адреса

связи,

помещенного

внутри

записи

и связанного,

с

соответствующим ключом так, как это

показано

на

рис. 3-5. Т а к и м образом,

если

ключ

появ­

ляется в 100 записях, то Справочник

содержит

един­

ственный

адрес,

указывающий на

первую

запись,

а, кро­

ме того,

внутри

к а ж д о й записи, содержащей ключ, запи­

сан адрес, у к а з ы в а ю щ и й на следующую

из

99 записей,

расположенных

в З У П Д .

Система

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

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

или

просто

мультисписок *

допускает

сколько

в записи

ключей.

Другой подход к организации списков

в

З У П Д вы­

текает

из

более

традиционных методов

обращения

к ф а й л а м .

Так, один

из

них — метод

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

списка — состоит

в изъятии

всех

адресов

связи

из

запи­

сей файла

и помещении

их

на

выходе

Справочника

в порядке

возрастания

адресов,

т. е. все

записи,

содер­

жащие заданный ключ X, представлены

списком — мо­

нотонной

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

адресов,

о б р а з у ю щ и х

запись переменной длины, адрес которой для ключа X

указывается в Справочнике

Ключей.

Указанные два метода представляют различные ва­

рианты

структуры

файла,

реализация

которых

приведет

к различным типам программирования, тем

не

менее

оба списка

могут

представлять

одну

и ту

ж е

структуру

Они сходны в том смысле, что используют одни

и те ж е

средства

определения логики

разбиения, а именно адре­

са связи;

в обоих случаях

д л я

получения разбиения

данного

файла необходимо указывать одно и то

ж е ко­

личество

адресов связи;

единственное различие

состоит

в местоположении этих адресов.

Метод инвертированного списка исключает разбро ­

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

системой

адреса связи из файла

ный между

Справочником

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

файлом .

Однако

эта

модификация

влечет

за

собой существенное

отличие

свойств обеих структур

во

времени отклика на

* Этот тип списковой структуры

сначала назывался

узловым

списком (см. [Л. 9]),

ционно

они различны и, как показано в

правой части

рис. 5-2,

совершенно полярны. П р и этом

оказывается,

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

но в то

ж е

время

мультисписковая

система

д а е т

некоторую

экономию

в объеме памяти файла и упрощает

програм­

мирование.

Поэтому естественно рассмотреть комбина­

цию

обоих

подходов, конструируя

спектр

различных

частично

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

мультисписковых

систем.

дением

некоторого

программного

параметра

можно

сде­

л а т ь непрерывным.

З а время

формирования

ф а й л а

па­

раметру

можно

присвоить

значение,

устанавливающее

д л я

структуры

ф а й л а

заранее

определенную

степень

инверсности,

которая

от одной

схемы формирования

фай­

л а

к другой

может

произвольно

изменяться.

Эта модификация основной концепции мультисписка

называется

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

с управляемой

длиной

спис­

ка.

Т а к а я структура

позволяет

проектировать

образова­

ние

списков

произвольной

максимальной длины, начи­

ная

от

единицы

и

кончая

фактической

длиной

списка.

но, ранг

мультисписковой системы, представленной на

рис. 5-2,

непрерывно расширяется от чисто мультисписко­

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

управляемой

длиной

списка,

равной единице. Поскольку

при переписи

ф а й л а

степень

инверсии введением длины

списка как

параметра про­

риодически

менять параметры

системы в

соответствии

с текущей

статистикой файла

и запроса.

Это позволит

тики

системы.

О д н а к о списковая

структура — не

единственное

средство разбиения файла . Д р у г и м

средством

может

быть физическое

разбиение

З У П Д на секторы,

имеющие

целью

направить

.поиск

тіо

ключу

на отобранные

сек­

торы

вместо просмотра

индивидуальных

записей.

При

внутри

сектора

зависит от таких

факторов, как

размер

сектора

(как в

числе записей,

т а к

и в количестве

симво­

лов),

ж е л а е м о й сложности

программирования, тип

З У П Д

и требование оперативного обновления и

харак ­

покажем, что

приписывание

записей

сектором

имеет

свои преимущества.

Т а к а я структура

уменьшает число

обращений

к

секторам,

причем группировка

записей

внутри сектора

о т р а ж а е т

их взаимное

р а с п о л о ж е н и е от­

носительно

запроса .

Н а рис.

5-2

схема

метода

разбиения на

секторы

ляется

функцией р а з м е р а сектора. Схема с м а л ы м и секто­

рами приближается к схеме с полной инверсией

записи

(одна запись в секторе) . Схемы с крупными

секторами

расположены ближе либо

к мультисписковой

системе,

если сектор внутри имеет

мультисписковую

структуру,

либо к

последовательному

файлу,

если

он

не

имеет

внутренней

списковой

структуры.

С другой

стороны,

если

сектор

имеет

внутреннюю

списковую

структу­

ру, по

схеме

инверсированного

списка, весь

файл не­

зависимо

от

размера

сектора

т а к ж е

окажется

инвер­

существенно различных этапов:

справочного декодирования

и

поиска

разбиения

файла .

, Техника программирования,

р е а л и з у ю щ а я

структуру

файла

на

к а ж д о м этапе,

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

и

оценивает­

ся в

двух

последующих

главах .

В

гл. 6

предлагаются

7—88

97

сложности

программирования, скорости

декодирования и

з а т р а т а м

памяти.

Вначале рассмотрим декодирующие

деревья, которые

чие упорядоченного

дерева

от неупорядоченного

состоит

в следующем: если

дерево

имеет N уровней, то

все клю­

время декодирования любого ключа,

недостатком — бо­

лее сложное программирование . В то

ж е время неупоря­

рость декодирования .

Н а

практике,

однако,

требуемая

словарем

ключей

глубина дерева в большинстве случаев

не

превышает

двух или трех уровней (в

зависимости

от типа

исполь­

зуемого

З У П Д ) .

Поэтому

использование

неупорядочен­

ных деревьев не

приведет

к существенному

сокращению

порядке в табл . 6-1. Дерево, изображенное

на

рис. 6-1,

уровень, хранимый

В оперативной

памяти

Уровни,

хранимые \

6 памяти

на дисках

ВЙВЩ вмщ\ BELLI BELM/BLRCI CRRd/CRRTI cm/

BUHLIOYSOIЕШІ

« А

R1JL1

Ulfa

Рис. 6-1. Дерево с усечением ключевых слов постоянной длины.

декодирует имена из таблицы, причем

к а ж д о е

имя со­

кращается

до первых

четырех букв. Д л я простоты пред­

полагается,

что уровни, хранимые в

памяти на

дисках,

Т а б л и ц а 6-1

Пример однозначного усечения

имени

Однозначно

Однозначно

Однозначно

закодиро­

Одн 13ЮЧНО

закодиро­

Полное имя

закодиро­

ванные

Полнее им я

закодиро­

ванные

ванный

фрагменты

ванный

фрагменты

фрагмент

для много­

фрагмент

для много­

уровневого

уровневого

дерева

д е р е Е а

ВАВВЕТ

В

В

BLACK

BL

. В

BABSON

BABS

ВA BS

BLACKWELL

BLACKW

BLACW

BAILEY

BAI

BAI

CARDER

С

С

BAKER

.ВАК

В

CARTON

CART

CART

BELL

BE

BE

CROZIER

CR

С

BELLSON

BELLS

B E L L S DUNLAP

D

D

BELMAN

B E I M

BELM

DYSON

DY

DY

EYERS

j

E

Е