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

ведении выборочного расчета будет показано,

что на

практике фактор ветвления обычно составляет

несколь­

ко сотен.

мяти, применяемой при использовании

некоторых типов

З У П Д , предположим, что устройства

памяти относятся

Однако

в этом случае

не имеет

значения, на каких до­

р о ж к а х

хранятся вершины дерева . Н а

рисунке

обо­

значает /-ю д о р о ж к у і-го цилиндра.

Н а ч и н а я с нижнего уровня дерева, фрагменты клю­

чей, соответствующие

полным

ключам,

можно

читать

ключа/адреса связи с заголовком списка

или с дорожкой,

в которой хранится следующий

уровень/длина списка.

При создании дерева его

вершины

приписываются

порядке.

В рассматриваемом примере выбран обратный

порядок,

поэтому

последние

три

фрагмента

( E Y E R

D Y S O ,

D Ö N L ) помещаются

в правую д о р о ж к у

наиболе

глубокого

уровня

Ті3.

Соответствующие длины

списков

Л І / L I , А2/Ьо

и A3/L3 вместе с

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

заголовком

адресов

списка т а к ж е

вводятся в

запись.

Последний

рожки . Он т а к ж е

вводится в

д о р о ж к у

второго

уровня

в качестве ссылки. Следовательно,

указателем последней

записи д о р о ж к и Г 1

0

является

E Y E R / Г І З , обозначающий

что E Y E R является

последним

фрагментом ключа

на до­

р о ж к е

третьего уровня

Тіз. П о л е

длины

списка,

равное

нулю

( 0 ) , указывает, что эта ссылка относится к другой

д о р о ж к е в справочнике,

а не к

списку

в

файле .

Следующие три фрагмента

ключей

(начиная

с

ниж ­

ней части с п и с к а ) — э т о

C R O Z ,

C A R T

и C A R D ;

они

нами списков. Последний

фрагмент на д о р о ж к е — C R O Z .

Он

вводится

на д о р о ж к у

второго

уровня

ТІ0 как

ссылка

на

позицию

следующей

записи

и имеет

ссылку

и

нулевую длину списка.

К а к показано на рис.

6-1, т р а к т о в к а следующих трех

ративной

памяти к а к

EYER/Тю и у к а з ы в а е т

последнюю

запись на

д о р о ж к е TiQ

(EYER) . Д л и н а списка

не исполь­

тивной памяти,

не

ведут

непосредственно

к

записям

файла .

Следующие

три

записи

т а к ж е хранятся

в

обратном

порядке. Это В А К Е ,

B A I L

и BABS . Они помещаются на

дорожку третьего уровня Т0І, а последний фрагмент име­

ет ссылку на

д о р о ж к у

Г 0 0

в виде

В А К Е / Г О і / 0 .

В списке

остается

еще

один

фрагмент — В А В В . Н а

на; В А В В помещается

во

вторую

запись

д о р о ж к и

Too

вместе с адресом связи

Аіз

и длиной

списка

L 1 3 . Послед­

ним фрагментом дорожки

второго

уровня

является

те­

уровневого

дерева

д л я

15

ключей, список которых

дан

в табл . 6-1.

Необходимо отметить, что в действительности

имеет­

ся только

13

ключевых ссылок, т а к

как два

ключа

де­

кодируются неоднозначно. Это имена

B E L L и

B E L L S O N ,

которые оба сводятся к B E L L , и B L A C K и B L A C K W E L L ,

которые сводятся к В L A C .

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

с помощью

этого

дерева

выполняется

следующим

образом .

Пусть

надо

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

имя

CARD ER. Д л я получения фрагмента

ключа

выделяются

первые четыре буквы CARD. Поиск на уровне оператив­

ной памяти дает, что CARD старше (при алфавитном

упорядочении), чем В А К Е ,

но

младше, чем

EYER;

сле­

довательно, о б р а щ а ю т с я к

д о р о ж к е

второго

уровня

Гю-

Эта д о р о ж к а

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

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

что

CARD

старше, чем B L A C , но младше, чем CROZ; поэтому про­

исходит обращение к д о р о ж к е

третьего уровня Г 1 2 . Вну­

три д о р о ж к и

Тіі точное отображение CARD

содержится

в первой записи.

Н а

этом

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

завершается

Его

результатом являются

адрес

связи

Л 6

и длина спис­

ка

Ьв.

С помощью этого дерева все ключи,

кроме

ВАВВЕТ,

будут

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

за

два

обращения

к

диску,

а В А В В Е Т — за одно обращение. Если следовать

указан­

ной

схеме нумерации

дорожек,

то при

первом

обраще­

нии (ко второму уровню дерева)

требуется

перемещение

головок

и поворот дорожки,

в то время

как второе обра­

объясняется тем, что к а ж д а я

вершина занимает

в

З У П Д

объем,

соответствующий физической записи. Р а з м е р

этой

записи

ограничен объемом

З У П Д

либо оперативной

па­

мяти.

Обычно

физическая

запись

соответствует

полной

д о р о ж к е

(например, в 3 000

символов) . Если

тройка

фрагмент ключа/адрес/длина списка состоит из

15

сим­

волов,

то

в к а ж д у ю вершину дерева можно

поместить

200 фрагментов

и декодировать с помощью трехуровне-

го дерева

(200) 3 = 8 млн. ключей. Это означает,

что один

ния к З У П Д (если верхний уровень,

требующий 3 000

символов, не хранится в оперативной

п а м я т и ) , и за два

будет показано, что это является

оптимальным

подхо­

дом .

Предположим, что

сравнения

в вершине,

хранимой

в оперативной памяти, производятся

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

(на к а ж д о е сравнение

требуется

100

мксек,

т. е.

около

сравнение и упорядочение интервала требуется 200

мксек.

Количество сравнений

равно в этом случае

log2 200 = 8,

а время поиска

внутри

вершины — 1,6

мсек.

Д л я срав­

нения заметим,

что

время

обращения

к З У П Д

обычно

составляет

20—500

мсек

(точнее, 60—100 мсек).

Следо­

вательно,

время

просмотра

большой вершины в

опера-

жны быть плотно упакованы, т. е. в конце записи

надо

оставлять некоторое

количество

резервного пространст­

ва,

обеспечивающего

расширение

вершины.

Л а н д а у е р

[Л.

12]

рекомендует

д л я большинства систем

(основан­

ных на различных способах обновления)

оставлять

в ре­

зерве 10% занимаемого объема памяти.

Пусть,

напри­

мер,

к

справочнику

надо

добавить ключевое

слово

BINDER . Сначала получается фрагмент

B I N D , который

старше, чем ВАКЕ, но младше, чем EYER, следователь­

но, обращаются

к д о р о ж к е Гю; B I N D младше, чем

B L A C ,

следовательно,

обращаются

к д о р о ж к е

Гц.

Поскольку

B I N D

старше,

чем

B E L M ,

но

младше,

чем B L A C , он

должен

находиться

м е ж д у

этими

двумя

фрагментами .

передается в буферную память вывода,

причем

B I N D по­

мещается между B E L M и B L A C вместе с соответствую­

щим адресом ссылки и длиной списка

(равной

единице,

ку Гц. Если в результате

предшествующих

обновлений

резервное

пространство

было израсходовано

(10%

ре­

зервного

пространства

на

д о р о ж к е

в 200 ключей

дает

возможность сделать 20

обновлений

до переполнения),

ний

фрагмент

проталкивается на следующую дорожку

того

ж е самого

уровня, т. е. следующую дорожку и до­

Например,

пусть

на

д о р о ж к у

Ті2 добавляется

B L A C ,

а интервалом дорожки Гц становится затем

B I N D

(за­

меняющий

B L A C

на

д о р о ж к е Гю). Если д о р о ж к а

Г 1 2

не

имеет достаточного резерва, то на дорожке

Тіз

передви­

гается CROZ и т. д. Если получены сведения об исчер­

пании резервного

пространства

д о р о ж е к или

среднего

количества

продвижений, необходимых д л я

выполнения