Логическая организация файлов

Логический ввод-вывод предоставляет приложениям и пользователям доступ к записям.

Метод доступа

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

Различные методы доступа отражают различные структуры файлов и различные пути доступа и обработки данных.

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

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

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

Могут быть две ситуации:

1. Поддержание структуры данных целиком возлагается на приложения

2. В поддержании структуры файла определенная роль отводится файловой системе

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

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

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

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

· смешанный файл;

· последовательный файл;

· индексно-последовательный файл;

· индексируемый файл;

· файл прямого доступа.

При выборе способа организации файла нужно учитывать несколько критериев:

· быстроту доступа;

· легкость обновления;

· экономность хранения;

· простоту обслуживания;

· надежность.

Смешанный файл. Это наименее сложная форма организации файла. Данные накапливаются в порядке поступления, когда запись состоит из одного пакета данных. За­писи могут иметь различные или одинаковые поля, расположенные в различном порядке (рис. 4.12). Каждое поле описывает само себя, включая как имя, так и значение. Длина каждого поля должна быть указана явно либо посредством применения разделителя.

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

Последовательный файл. Для записей используется фиксированный формат. Все записи имеют одинаковую длину (но иногда и не одинаковую) и состоят из одинаково­го количества полей фиксированной длины, организованных в определенном порядке (рис. 4.13). Поскольку длина и позиция каждого поля известны, то сохранению подле­жат только значения полей. Атрибутами файловой структуры является имя и длина каждого поля.Одно определенное поле (или несколько полей) называется ключевым. Оно одно­значно идентифицирует запись, так как это поле различно для каждой записи. Более то­го, записи сохраняются в «ключевой» последовательности: в алфавитном порядке для текстового ключа и в числовом - для числового. Последовательные файлы часто ис­пользуются пакетными приложениями и обычно являются оптимальным вариантом, если эти приложения выполняют обработку всех записей. Удобно и то, что такой файл можно хранить как на диске, так и на магнитном диске. Для диалоговых приложений последовательный файл малоэффективен, поскольку для нахождения нужной записи требуется последовательный перебор записи файла. Правда, если в оперативную память загрузить весь файл, возможен более эффективный метод поиска. Дополнения к файлу или изменения в записях создают проблемы.

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

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

Индексно-последователъный файл. Одним из методов преодоления недостатков по­следовательного файла является индексно-последовательная организация файла. В этом случае файл состоит из трех частей (файлов): главный файл, содержащий запи­си с последовательно идущими ключами, индексный файл, содержащий индексное поле и указатель в главный с ключами, файл переполнения (рис. 4.14).

Для поиска нужной записи по ее ключу сначала выполняется поиск в индексном файле. После того как в нем найдено наибольшее значение ключа, которое не превыша­ет искомое, продолжается поиск в главном файле. Например, пусть последовательный файл (главный) содержит 1 млн. записей. Для поиска определенного ключевого значе­ния необходимо в среднем 0,5 млн. операций доступа к записям. Если создать индекс­ный файл, содержащий 1000 элементов, то потребуется в среднем 500 операций доступа к индексному файлу, после чего еще нужно в среднем 500 операций доступа к главному файлу. В результате средняя длина поиска уменьшается с 0,5 млн. до 1000. Еще лучший результат можно получить, используя многоуровневую индексацию. При этом нижний уровень индексного файла рассматривается как последовательный файл, для которого создается индексный файл верхнего уровня.

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

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

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

переменной длины.

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

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

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