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

сированное

дерево» или рандомизированный, и если

ключ X по

адресу А2 не соответствует ключу

X запроса,

то в дополнение к полному значению ключа,

нотребовал-

чае у к а з ы в а л а бы на

другой

список

адресов, т а к ж е со­

д е р ж а щ и й в качестве

первого

слова

полный ключ. Если

роткому списку. В конце списка

адресов

д о л ж

н а быть

оставлена резервная зона таким

образом,

чтобы

при до-

бавлении записей

к данному списку можно было без пе­

реполнения вставить

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

щий адрес. Если

резервное

поле исчерпано,

как

показа­

но на рис. 7-9

д л я

ключа Y, то последний элемент

в запи­

си содержит

адрес

связи

к другой записи

переменной

ливается,

ключевые списки

снова собираются вместе

в единые

записи переменной

длины.

ше. Списки А , В и

С на рис. 7-6 соответствуют инверти­

рованным

спискам

на рис. 7-9.

7-7. ВРЕМЯ ВЫБОРКИ ИЗ ФАЙЛА

Время обработки

запроса в файле есть функция спо­

соба его

организации, характеристик З У П Д и количе­

счета общего времени требуется определить

некоторые

параметры,

связанные

с файлом,

запросом и З У П Д . Не­

которые

из

этих

параметров,

например,

параметры

З У П Д , могут быть

взяты из характеристик

машины. Па­

раметры

организаций

файла определяются

статистикой

его

генерирования. Д л я других

параметров

можно ука­

зать

лишь

первое

приближение,

которое

по

желанию

определение. П а р а м е т р ы , относящиеся к файлу,

следую­

щие: общее число различных ключей (т. е. пары

имя/зна­

чение), обозначаемое через V, количество записей в си­

стеме Nr, среднее

количество ключей на запись Ni,; сред­

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

как

N^Nh/V;

среднее количество символов на запись

Cf, сред­

нее количество записей на сектор в посекторно

расчле­

ненных

системах

і ? 0 и среднее

количество

секторов

на

ключ Ck-

Все

п а р а м е т р ы

запроса

относятся к запросу,

состоя­

щему из одночлена. Если

запрос состоит из суммы про­

изведений, время

д о л ж н о

быть

умножено на количество

слагаемых . Среднее число термов (отрицаемых

и неотри-

цаемых

ключей)

в

слагаемом

запроса — Ni,

а

количест­

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

термов — Np.

Д л и н а самого

короткого

списка

ключей,

из

числа

составляющих

запрос, —

L s ,

Т а б л и ц а 7-3

Параметры обработки

файла

Об ізначение

Определение

Тип параметра

зической

записи ЗУПД

А. Среднее

время

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

доступа,

исключая

задержк и

и

время

считывания

с ЗУПД

ТТ, скорость

передачи

данных

из ЗУПД

RT

(байт/сек)

и врем я оборота З У П Д

R.

TML=Ls(Tr+\,5R);

(7-1)

TIL=(Nt[L/A}

+ pLs)

(7Ѵ+1.5Я);

(7-2)

Tes = Np [Си/А]

(Tr

+ 1,5R) +

aCk

(TT + M i - ) .

(7-3)

П о д с т а в л я я (7-1)

в

(7-2), получаем

соотношение

вре­

ными

системами

(7-4)

Поэтому поиск в

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

списке быстрее,

чем в

мультисписке,

если

/ 1

Nt

Г 1

1

(7-5)

Р < 1

- 7 7

Т

•

Это

неравенство

показывает,

что

чем

больше число

физических записей приходится

на средний список

(LIA),

и чем меньше самый короткий

список

(Ls),

тем

вероят­

ней, что время выборки дл я

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

окажется

меньше, чем это время для инвертированного

списка.

Обычно неравенство (7-5) выполняется,

т а к как

у ж е

при

/Ѵ/>2

р очень мало. Например,

если Nt

= 3,

Л ='500,

L =

= 300

и L ä = 2 0 , то правая

часть

неравенства (7-5) равна

0,85.

Иначе говоря, чтобы

поиск

пересечений

инвертиро­

рых системах могут быть использованы два

(или более)

типов

З У П Д . Например , дл я хранения

справочника

мо­

жет использоваться дисковая память, а ЗУ

на

магнит­

ных

полосках — для

хранения файлов,

а

возможно

и

инвертированных списков. В таких случаях

параметры

З У П Д , используемые

в формулах, д о л ж н ы быть

соответ­

ственно изменены.