В. Столлингс - Операционные системы (1114679), страница 118

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 118)

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

Периодически в пакетно1 Режиме выполняется слияние основного и журнального Файлов в новый Файл корректной последовательностью ключей. Альтернативной организацией может служить Физическая организация пс следовательного Файла в виде списка с использованием указателей В каждо~ Физическом блоке сохраняется одна или несколько записей. Каждый блок н диске содержит указатель на следующий блок. для вставки новых записей дос таточно изменить указатели, и нет необходимости в том, чтобы новые записи зг нимали мали определенную физическую позицию. Это удобство достигается за сче определенных накладных расходов и дополнительной работы.

'В Возможна ситуация. когда ключ составляют несколько таких полей. — Прим. перев Гданьск 12..Управление файлами Ондексно-последовательный файл Популярным методом преодоления недостатков последовательного файла явля.тся индексно-последовательная организация Файла. Индексно-последовательный райл сохраняет главную особенность последовательного Файла: записи организованы -юследовательно на основании значений ключевого поля. Но при описываемой орга.гизации добавлены две особенности: индекс файла для поддержки произвольного доступа и Файл (или область) переполнения. Индекс обеспечивает возможность быстрого поиска требуемой записи. Файл переполнения подобен журнальному файлу, используемому Файлом последовательного доступа, однако организован таким образом, что записи в нем размещаются, следуя указателю предшествующей записи.

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

После того как в нем найдено наибольшее значение ключа, которое не превышает искомое, продолжается поиск в основном файле в позиции, определенной указателем из индексного Файла. Чтобы убедиться в эффективности этого подхода, можно в качестве примера рассмотреть последовательный Файл, содержащий 1 миллион записей. Для поиска определенного ключевого значения необходимо в среднем полмиллиона операций доступа к записям. Предположим, что создается индекс, содержащий 1000 элементовз, со значениями ключей индекса, более или менее равномерно распределенными в главном Файле. Теперь потребуется около 500 операций доступа к индексному файлу, после чего нужно еще около 500 опера:ций доступа к главному Файлу для нахождения требуемой записи. Итак, средняя длина поиска уменьшилась с 500000 до 1000.

Дополнения к Файлу обрабатываются следующим образом. В каждой записи главного Файла содержится дополнительное поле, невидимое для приложения и являющееся указателем на Файл переполнения. Если в файл производится вставка новой записи, она добавляется в Файл переполнения. Запись в главном файле, непосредственно предшествующая новой записи в логической последовательности, обновляется и указывает на новую запись в файле переполнения.

Если запись, непосредственно предшествующая новой, сама оказывается в файле переполнения, то обновляется указатель этой записи. Как и в случае с последовательным Файлом, время от времени выполняется слияние индексно-последовательного файла с Файлом переполнения. Индексно-последовательная организация намного сокращает время, необходимое для доступа к записи, не изменяя при этом последовательную природу Файла. Для последовательной обработки всего файла записи в главном Файле обРабатываются до тех пор, пока не будет обнаружена ссылка на Файл переполнения, После этого выполняются операции с цепочкой записей в Файле переполнения до тех пор, пока не встретится нулевой указатель, свидетельствующий о завеРшении цепочки. Затем продолжится обработка записей основного Файла с того места, на котором произошло обращение к файлу переполнения. з их иногда называюьп точками входа.

— прим. перев. Часть б. Операции ввода-вывода и файлы Для обеспечения большей производительности при обращениях может ис пользоваться многоуровневая индексация. При этом нижний уровень индексного файла рассматривается как последовательный Файл, для которого создается ин дексный файл верхнего уровня. Рассмотрим снова Файл с 1 миллионом записей Для него создается индекс нижнего уровня с 10000 элементами, после чего мо жет быть создан индекс верхнего уровня из 100 элементов для индекса нижнего уровня.

Поиск начинается с индекса верхнего уровня (средняя длина равна 50 обращениям) для нахождения точки входа в индексе нижнего уровня. Затем производится поиск в этом индексе (средняя длина равна 50 обращениям) для нахождения точки входа в главный файл, поиск в котором также требует в среднем 50 обращений. Таким образом, средняя длина поиска уменьшилась с 500000 до 1000 при одноуровневом индексе и до 150 — при двухуровневом.

Индексированный файл Индексно-последовательный файл сохраняет одно ограничение последовательного файла: эффективная работа с файлом ограничена работой с ключевым полем. Если необходимо производить поиск записи по какой-либо иной характеристике, отличной от ключевого поля, то оказываются непригодными обе организации последовательного Файла„в то время как в некоторых приложениях эта гибкость крайне желательна. Для достижения гибкости необходимо использование большего количества индексов, по одному для каждого типа поля, которое может быть объектом поиска.

В обобщенном индексированном файле доступ к записям осуществляется только по их индексам, В результате в размещении записей нет никаких ограничений до тех пор, пока указатель по крайней мере в одном индексе ссылается на эту запись. Кроме того, в таком файле легко реализуются записи переменной длины. Используются два типа индексов. Полный индекс содержит по одному элементу для каждой записи главного Файла, Сам по себе индекс организовывается в виде последовательного файла для облегчения поиска. Частный индекс содержит элементы для записей, в которых имеется интересующее нас поле. (Некоторые записи переменной длины могут не содержать всех полей.) При добавлении новой записи в главный файл необходимо обновлять все индексные файлы. Индексированные Файлы используются прежде всего теми приложениями, в которых время доступа к информации является критической характеристикой и редко требуется обработка всех записей в файле.

Примерами могут служить системы заказа авиабилетов или системы инвентаризации. Файл прямого доступа Файл прямого доступа, или хешированный файл, использует возможность прямого доступа к блоку с известным адресом при хранении файлов на диске. Как в последовательных Файлах и файлах индексно-последовательного доступа. в каждой записи должно иметься ключевое поле. Однако концепция последовательного размещения данных здесь не используется. Файл прямого доступа применяет хеширование ключевых значений (подробнее хеширование описано в приложении к главе 8, "Виртуальная память"). На рис.

8.24,б показано хеширование с таблицей переполнения, которое обычно используется при организации хеш-файле. Глава 12. 'Управление Файлами Файлы прямого доступа используются, когда необходим очень быстрый досок, при записях Фиксированной длины, а также в случаях, когда доступ осуще,вляется ко всем записям. Примерами могут служить каталоги, прайс-листы, асписания и списки имен. Габлнца 12.2. Элементы информации файлового каталога Основная ниформация Имя Файла Имя, выбранвое создателем (пользователем или программой). Должно быть единственным внутри определенного каталога Тяп Файла Е1апример, текстовый, двоичный, загружаемый модуль и т.п. ОРганизация файла Для систем, поддерживающих различные типы организации Адресная яяформапия Том (воситсль) Начальный адрес Определяет устройство, яа котором хранится файл Начальный физический адрес в устройстве внешней памяти (например, цилиндр, дорожка, номер блока на диске) Занимаемый размер Текущий размер файла в байтах, словах или блоках ,'одержимое Связующим звеном между системой управления файлами и набором Файлов лужит Файловый каталог.

Характеристики

Список файлов книги