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

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

/ Занести бит уничтожения записи 2 Декодировать каждый ключ в записи и уменьшить

длину списка на единицу

Справочник

С

Рис. 8-3. Уничтожение полной записи.

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

Н а рис. 8-4 иллюстрируется удаление отдельных клю­

на к а ж д а я запись по очереди кроме третьей, в которой будет проанализирован бит удаления ключа, запись про­

165

физическая запись) может быть переформирована и за­

Добавление/уничтожение/модификация неключевых данных

1.Считывание записи из ЗУПД в память. Изменение записи

2.Если запись укоротилась, то переформировать дорожку и запи­ сать ее в ЗУПД

3.Если запись удлинилась и

2. Если переформированная д о р о ж к а превышает ее физическую длину, то полная запись уничтожается со­ гласно процедуре - удаления, описанной на рис. 8-3, а пол­ ная измененная запись добавляется к файлу в соответст­ вии с процедурой, описанной в табл . 8-1. Это означает, что запись будет появляться в файле д в а ж д ы — один раз в своей немодифицированной форме и другой раз в изме­ ненной форме, но в первом случае бит удаления записи

будет равен единице, так что поисковая программа будет пропускать эту запись при любом просмотре списка. К а к указывалось выше, те записи, для которых бит удаления

единственное различие м е ж д у состояниями дорожки до и после изменения состоит в том, что запись R3 стала боль­

167

ми. При этом увеличивается эффективность поиска, хотя

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

Т а б л и ц а 8-3

Добавление ключей

1.Считывание записи из ЗУПД по адресу ДА в память и добав­ ление ключей

2.Декодирование ключа /' по справочнику

3.Передача начального адреса списка ключа і из справочника в поле адреса связи ключа в модифицированной записи

4.Адрес ДА становится новым начальным адресом ключа і по справочнику

5. Уведичение длины списка ключа і в справочнике на единицу

6.Повторение пп. 2—5 для всех добавляемых ключей

7.Запомнить модифицированную запись в соответствии с проце­ дурой изменения неклгачевых данных

рование по справочнику 1-го ключа, который был добав ­ лен к записи. Третий — передача начального адреса і-го ключа из справочника в область адреса связи ключа в из­ меняемой записи. Четвертый — помещение адреса новой записи в качестве начального адреса t-го ключа в спра-

168

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

быть применена к восстанавливаемым данным . Это озна­ чает, что запись может быть удалена и помещена в ф а й л

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

Т а б л и ц а 8-4 Добавление полной записи (инвертированный список)

1.Редактирование записи для входа в файл

2.Присвоение адреса ДА к новой записи

3.Декодирование і-го ключа по справочнику инвертированного списка переменной длины

4.Добавление ДА в список. Если резервная область^ исчерпана, добавить дополнительный блок записи и вставить адрес связи в качестве последнего слова предыдущей записи

5.Увеличение длины списка на единицу

6. Повторение пп. 3—5 для всех ключей новой записи

7. Запоминание новой записи в ЗУПД по адресу ДА

169