Другие организации файлов
В некоторых случаях к одному и тому же файлу требуется как последовательный, так и прямой доступ. Например, счета за электричество выгоднее составлять, последовательно просматривая записи о потребителях электроэнергии, в то время как выдача потребителям справок по телефону требует прямого доступа. Другими словами, организация файла должна быть такой, чтобы обеспечить прямой доступ без просмотра ненужных записей и последовательный без обращения к таблице индексов. Этим условиям удовлетворяет файл с прямым доступом, чьи записи упорядочены по ключу. Однако в случаях переполнения какой-либо записи, вставке или уничтожении сохранить упорядоченность невозможно.
Проблема уничтожения решается довольно просто. Одного бита в начале записи достаточно, чтобы обозначить отсутствие записи, а соответствующий элемент таблицы индексов может быть помечен или даже уничтожен. Для обеспечения некоторого числа вставок или переполнении можно выделить дополнительное пространство и дополнительные указатели. Для этого после определенного количества записей резервируется свободная область, чтобы иметь возможность вставлять новые записи, значения ключей которых лежат в диапазоне между значениями ключей этих записей. Такая свободная область обычно отводится на той же дорожке. Когда осуществляется вставка записи, то либо несколько записей сдвигаются, чтобы вставка произошла в нужном месте, либо новая запись размещается в свободной области, а к ее предшественнику по ключу добавляется указатель. Первоначально незаполненное пространство можно использовать и для переполнившихся записей. Можно также завести дополнительные дорожки переполнения, когда первоначально выделенные области оказываются заполненными. Однако при этом тратится память на указатели и, что более важно, требуются дополнительные обращения к несмежным цилиндрам. В конце концов последовательная обработка становится настолько неудобной, что возникает необходимость реорганизации файла.
Детали реализации таких индексно-последовательных файлов различны в разных системах. Организация файла, которая дает возможность как прямого, так и последовательного доступа, имеет два существенных недостатка. Во-первых, с самого начала требуется дополнительная память для вставляемых или переполнившихся записей. Во-вторых, если файл все время изменяется, то при последовательной обработке все больше времени тратится на косвенный доступ к записям и, следовательно, файл нужно часто переупорядочивать.
Список возможных организаций файлов на этом не исчерпывается. Другими полезными организациями являются инвертированные файлы для записей с несколькими ключевыми полями, многосписковые файлы, имеющие произвольную структуру указателей, файлы с древовидной структурой, которые часто реализуются списками. Среди деревьев возрастает значение В-деревьев для реализации различных организаций файлов.
Управление файлами невозможно отделить от управления устройствами, на которых они размещаются. В некоторых системах они тесно взаимосвязаны, в других , хотя и зависят друг от друга, но определяются отдельно. Управляющие функции лежат в широком диапазоне: от работы с файлами на символическом уровне до действий в терминах физических устройств, Часто всю совокупность функций удобно свести в некоторую линейную иерархию, в которой операции любого уровня могут быть реализованы без знания деталей реализации на более низких уровнях. Это означает, что разработку и реализацию управляющих программ ввода/вывода можно было бы осуществить с помощью модульной технологии программирования. При этом модули управляющих программ на каждом уровне пользовались бы услугами модулей более низкого уровня, и взаимодействие между ними осуществлялось бы только с помощью передачи параметров и вызовов.
Учитывая разнообразие функций, рассмотренных в этой и предыдущих главах, тот факт, что существует несколько способов организаций множества операций в иерархию, не должен вызывать удивления. Обычно модули программного обеспечения называются “базовая система файлов”, “логическая система файлов” и “физическая система файлов”. К сожалению, функции модулей с одинаковыми названиями в двух разных системах могут сильно различаться. По-видимому, нет единого мнения относительно того, что должны означать эти имена. Поэтому далее имя модуля будет указываться функцией, которую он выполняет.
