Организация файлов

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

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

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

Последовательная организация файла предполагает создание на диске последовательного файла.

Последовательный файл – файл, к компонентам которого обеспечивается лишь последовательный доступ в соответствии с упорядоченностью этих компонентов.

В последовательных файлах размещают наборы данных с последовательной организацией. Обычно в последовательных файлах используют один указатель от одного блока к другому (рис.5.9). Иногда для ускорения доступа применяют двойные ссылки.

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

- один физический блок под одну логическую запись;

- несколько физических блоков под одну логическую запись;

- один физический блок под несколько логических записей.

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

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

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

Доступ к записи в последовательном файле требует в среднем чтения и просмотра половины блоков файла.

Непрерывная организация файла предполагает создание на диске непрерывного файла.

Непрерывный файл – файл на носителе, состоящий из ряда физических блоков, которые все расположены в одной сплошной области дискового пространства.

Непрерывная организация файла представляет собой жесткую структуру, что обеспечивает самый быстрый доступ к данным. Размер непрерывного файла фиксирован и задается в момент создания файла. Файл не может быть увеличен в размере, однако уменьшение длины непрерывного файла допускается. Главный недостаток непрерывной организации файла в том, что во внешней памяти не всегда может быть выделено нужное количество смежных физических блоков.

Доступ к записям непрерывного файла достаточно прост. Если обозначить через r – номер записи, l – длину записи и L – длину блока, то номер b блока, где находится запись, вычисляется по формуле

b=l*r/L.

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

Обновление записи r совершается очень просто – она просто перекрывается новыми данными. При этом происходит обращение к нужному количеству физических блоков.

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

Сегментированная организация файла предполагает создание сегментированного файла.

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

Сегментированный файл называют также индексным файлом.

Такая организация предназначена для преодоления недостатков доступа в последовательных файлах. Индекс представляет собой меру произвольности доступа и средство обслуживания добавления в файл.

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

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

Поиск по сайту: