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

пользована комбинация быстродействующей и медленной

сек

* Все процедуры включают перекодирование трехуровневого дерева; верхний уровень занесен в оперативную память [см. (6-11)].

вочника, инвертированных списков и файла по этим уст­ ройствам, а в табл . 8-14 содержатся вычисленные резуль­ таты. В табл . 8-9 приведены вычисления д л я времени поиска и обновления. Вычисления д л я времени поиска сделаны по формулам (7-1) — (7-3).

180

О д н а ко нельзя делать категорических обобщении из

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

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

8-6. СРАВНЕНИЕ МЕТОДОВ ОРГАНИЗАЦИИ ФАЙЛА

И з формул и таблиц д л я вычисления объема памяти фай­ ла и времени обработки, предложенные в гл. 6—8, видны трудности, возникающие при попытке д а т ь общую оцен­ ку одной структуры файлов по сравнению с другой. Н у ж ­ но учитывать всевозможные качественные и количествен­ ные факторы, такие как однозначное и неоднозначное декодирование, неявные издержки памяти З У П Д , поиско­ вые возможности декодеров, скорость декодера, требова­ ния п а м я т и д л я декодера, скорость поиска файла, выход­ ное оборудование (пишущая машинка, печатающее уст­

характеристики запроса, требования обновления в ре­

181

инвертированных списков и сскторпо-последопателыіых

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

сей из файла, как только логическая обработка выдает первый поисковый адрес и в дальнейшем выборка из ф а й л а может перекрываться с процедурами обработки списка. Это приведет к более быстрому начальному от­ вету д л я систем инвертированных списков. В системе с Э Л Т время последовательного ответа становится кри­ тическим, если оператор хочет быстро просмотреть отве­ ты. Поэтому инвертированный список в этом случае предпочтительнее, т а к как он всегда самый быстрый в этом случае и время ответа зависит только от среднего времени доступа к З У П Д . В оперативной системе с вы­ сокоскоростным печатающим механизмом время выборки (последовательное и общее) является самым в а ж н ы м фактором .

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

спомощью секторных разбиений.

Всекторно-последовательных системах нельзя вычис­ лить допоисковую статистику, за исключением некоторых

182