Способы организации файлов
Файловые системы поддерживают несколько функционально различных типов файлов, в число которых, как правило, входят обычные файлы, файлы-каталоги, специальные файлы, именованные конвейеры, отображаемые в память файлы и другие.
Обычные файлы, или просто файлы, содержат информацию произвольного характера, которую заносит в них пользователь или которая образуется в результате работы системных и пользовательских программ. Большинство современных операционных систем никак не ограничивает и не контролирует содержимое и структуру обычного файла. Содержание обычного файла определяется приложением, которое с ним работает. Например, текстовый редактор создает текстовые файлы, состоящие из строк символов, представленных в каком-либо коде. Это могут быть документы, исходные тексты программ и т.п. Текстовые файлы можно прочитать на экране и распечатать на принтере. Двоичные файлы не используют коды символов, они часто имеют сложную внутреннюю структуру, например исполняемый код программы или архивный файл. Все операционные системы должны уметь распознавать хотя бы один тип файлов — их собственные исполняемые файлы.
Каталоги — это особый тип файлов, которые содержат системную справочную информацию о наборе файлов, сгруппированных пользователями по какому-либо неформальному признаку (например, в одну группу объединяются файлы, содержащие документы одного договора, или файлы, составляющие один программный пакет). Во многих операционных системах в каталог могут входить файлы любых типов, в том числе другие каталоги, за счет чего образуется древовидная структура, удобная для поиска. Каталоги устанавливают соответствие между именами файлов и их характеристиками, используемыми файловой системой для управления файлами. В число таких характеристик входит, в частности, информация (или указатель на другую структуру, содержащую эти данные) о типе файла и расположении его на диске, правах доступа к файлу и датах его создания и модификации. Во всех остальных отношениях каталоги рассматриваются файловой системой как обычные файлы.
Специальные файлы — это фиктивные файлы, ассоциированные с устройствами ввода-вывода, которые используются для унификации механизма доступа к файлам и внешним устройствам. Специальные файлы позволяют пользователю выполнять операции ввода-вывода посредством обычных команд записи в файл или чтения из файла. Эти команды обрабатываются сначала программами файловой системы, а затем на некотором этапе выполнения запроса преобразуются операционной системой в команды управления соответствующим устройством.
Современные файловые системы поддерживают и другие типы файлов, такие как символьные связи, именованные конвейеры, отображаемые в память файлы.
При выборе способа организации файла важно учитывать несколько критериев.
- Быстрота доступа.
- Легкость обновления.
- Экономность хранения.
- Простота обслуживания.
- Надежность.
Относительный уровень приоритета этих критериев зависит от приложений, которые будут работать с файлом. Например, если файл предназначен только для обработки в пакетном режиме, когда одновременно выбираются несколько записей, быстрый доступ для выборки одной записи заинтересует нас менее всего. Файл, сохраненный на CD-ROM, никогда не будет обновлен, поэтому вопрос легкости в обновлении не имеет смысла.
Перечисленные критерии могут конфликтовать между собой. Так, для экономии при сохранении необходима минимальная избыточность данных. С другой стороны, избыточность является главным фактором увеличения скорости доступа к данным. В качестве примера можно привести использование индексов.
Количество разных способов организации файлов, которые уже реализованы на практике или только предложены, слишком велико и их рассмотрение даже в книге, посвященной файловым системам, невозможно. В нашем кратком обзоре в общих чертах описаны пять фундаментальных способов организации. Большинство структур, используемых в реальных системах, либо подпадают под одну из этих категорий, либо могут быть реализованы как комбинация этих способов организации. Ниже приводятся пять способов организации файла:
- Смешанный файл.
- Последовательный файл.
- Индексно-последовательный файл.
- Индексированный файл.
- Файл прямого доступа (хешированный).
Наименее сложная форма организации файла может быть названа смешанной. Данные накапливаются в порядке своего поступления. Каждая запись состоит из одного пакета данных. Такая форма упрощает накопление всей массы данных и их хранение. Записи могут иметь как различные поля? так и одинаковые поля, расположенные в различном порядке. Поэтому каждое поле должно описывать само себя, включая как значение, так и имя. Длина каждого поля должна быть либо указана неявным образом посредством применения разделителя, либо явно включена как подполе (или известна для данного типа файла заранее).
Поскольку смешанный файл не имеет никакой структуры, то доступ к записи осуществляется путем полного перебора всех записей файла. Т.е. если необходимо найти запись, содержащую определенное поле с определенным значением, проверяется каждая запись до тех пор, пока не будет найдена искомая или пока весь файл не будет пересмотрен. Если необходимо найти все записи, содержащие определенное поле, или все записи, содержащие поле с определенным значением, то поиск должен производиться по всему файлу.
Смешанные файлы встречаются тогда, когда данные накапливаются и сохраняются перед обработкой, или если данные неудобны для организации. Файлы этого типа рационально использует дисковое пространство при работе с данными различного размера и структуры; он хорошо подходит для полного перебора, но недостаточно прост при обновлении данных. В большинстве других случаев этот тип файла непригоден.
Наиболее распространенным видом файловой структуры является последовательный файл. В нем для записей используется фиксированный формат. Все записи имеют одинаковую длину и состоят из одинакового количества полей фиксированной длины, организованных в определенном порядке. Поскольку длина и позиция каждого поля известны, то сохранению подлежат только значения полей; атрибутами файловой структуры являются имя и длина каждого поля.
Одно определенное поле, обычно — первое поле в каждой записи, называется ключевым полем, которое идентифицирует запись уникальным образом, так что ключевые значения различных записей всегда различны. Более того, записи сохраняются в "ключевой" последовательности: в алфавитном порядке для текстового ключа и в числовом порядке для числового ключа.
Последовательные файлы часто используются пакетными приложениями и обычно являются оптимальным вариантом, если эти приложения выполняют обработку всех записей. Только файл с последовательной организацией может быть одинаково легко сохранен как на магнитной ленте, так и на диске или другом носителе.
Для диалоговых приложений, которые работают с запросами и/или выполняют обновление индивидуальных записей, последовательный файл является малоэффективным. Для нахождения необходимой записи нужно произвести последовательный перебор записей файла. Если в основную память может быть внесен весь файл целиком или большая его часть, то возможно использование более эффективных методов поиска. Тем не менее обращение к записи в большом последовательном файле занимает, как правило, относительно много времени. Дополнения к файлу также создают проблемы. Обычно последовательный файл сохраняется с последовательной организацией записей внутри блоков. Другими словами, физическая организация файла на магнитной ленте или на диск в точности соответствует логической организации файла. В этом случае обычно выполняется размещение новых записей в отдельном смешанном файле, называемом журнальным файлом или файлом транзакции. Периодически в пакетном режиме выполняется слияние основного и журнального файлов в новый файл корректной последовательностью ключей.
Альтернативной организацией может служить физическая организация последовательного файла в виде списка с использованием указателей. В каждом физическом блоке сохраняется одна или несколько записей. Каждый блок на диске содержит указатель на следующий блок. Для вставки новых записей достаточно изменить указатели, и нет необходимости в том, чтобы новые записи занимали определенную физическую позицию. Это удобство достигается за счет определенных накладных расходов и дополнительной работы.
Популярным методом преодоления недостатков последовательного файла является индексно-последовательная организация файла. Индексно-последовательный файл сохраняет главную особенность последовательного файла: записи организованы последовательно на основании значений ключевого поля. Но при описываемой организации добавлены две особенности: индекс файла для поддержки произвольного доступа и файл (или область) переполнения. Индекс обеспечивает возможность быстрого поиска требуемой записи. Файл переполнения подобен журнальному файлу, используемому файлом последовательного доступа, однако организован таким образом, что записи в нем размещаются, следуя указателю предшествующей записи.
В простейшей индексированно-последовательной структуре используется единственный уровень индексации, и индекс в этом случае представляет собой простой последовательный файл. Каждая запись в индексном файле состоит из двух полей: ключевого поля, идентичного ключевому полю в основном файле, и указателя в основной файл с ключами. Для обнаружения определенного поля сперва выполняется поиск в индексном файле, после того как в нем найдено наибольшее значение ключа, которое не превышает искомое, продолжается поиск в основном файле в позиции, определенной указателем из индексного файла.
Индексно-последовательный файл сохраняет одно ограничение последовательного файла: эффективная работа с файлом ограничена работой с ключевым полем. Если необходимо производить поиск записи по какой-либо иной характеристике, отличной от ключевого поля, то оказываются непригодными обе организации последовательного файла, в то время как в некоторых приложениях эта гибкость крайне желательна.
Для достижения гибкости необходимо использование большего количества индексов, по одному для каждого типа поля, которое может быть объектом поиска. В обобщенном индексированном файле доступ к записям осуществляется только по их индексам. В результате в размещении записей нет никаких ограничений до тех пор, пока указатель по крайней мере в одном индексе ссылается на эту запись. Кроме того, в таком файле легко реализуются записи переменной длины.
Используются два типа индексов. Полный индекс содержит по одному элементу для каждой записи главного файла. Сам по себе индекс организовывается в виде последовательного файла для облегчения поиска. Частный индекс содержит элементы для записей, в которых имеется интересующее нас поле. (Некоторые записи переменной длины могут не содержать всех полей.) При добавлении новой записи в главный файл необходимо обновлять все индексные файлы.
Индексированные файлы используются прежде всего теми приложениями, в которых время доступа к информации является критической характеристикой и редко требуется обработка всех записей в файле. Примерами могут служить системы заказа авиабилетов или системы инвентаризации.
Файл прямого доступа, или хешированный файл, использует возможность прямого доступа к блоку с известным адресом при хранении файлов на диске. Как в последовательных файлах и файлах индексно-последовательного доступа, в каждой записи должно иметься ключевое поле. Однако концепция последовательного размещения данных здесь не используется.
Файл прямого доступа применяет хеширование ключевых значений. Файлы прямого доступа используются, когда необходим очень быстрый доступ, при записях фиксированной длины, а также в случаях, когда доступ осуществляется ко всем записям. Примерами могут служить каталоги, прайс-листы, расписания и списки имен.