1 Файловые системы. Логическая организация файлов. Основные понятия - Поле (field). Является основным логическим элементом данных. Поле содержит единственное значение и характеризуется длиной (фиксированной или переменной) и типом данных (символьная строка, десятичное число и т.д.). - Запись (record). Является набором логически связанных между собой полей, которые могут быть обработаны как единое целое. Запись может быть фиксированной или переменной длины (либо одно или несколько полей в ней переменной длины, либо запись имеет переменное количество полей). - Файл (file). С точки зрения логической организации, представляет собой набор однородных (одинаковых по структуре) записей. Как правило, файл рассматривается пользователем как единое целое. Однако доступ (создание, корректировка, удаление) может осуществляться как на уровне целого файла, так и на уровне его записей и даже отдельных полей. - База данных (data base). Представляет собой набор явно связанных между собой данных и может состоять из нескольких файлов различных типов. Способы представления внутренней организации файлов с точки зрения пользователя.

2 Файловые системы. Логическая организация файлов. Все используемые в настоящее время способы логической организации файлов являются комбинациями 5 базовых типов. 1. Смешанный файл ЗАПИСИЗАПИСИ Наименее сложный способ логической организации файлов. Данные накапливаются в порядке поступления. Каждая запись состоит из одного пакета данных. Записи могут иметь могут иметь различное число полей переменной или фиксированной длины. Каждое поле должно описывать само себя (имя и собственное значение), длина каждого поля указывается либо неявно (применением разделителя), либо явно (в составе поля содержится значение его длины). Поскольку смешанный файл не имеет жесткой структуры, доступ к конкретной записи (полю) осуществляется путем полного перебора всех записей (полей) от начала файла (записи). Такая организация файла достаточно экономична и удобна для первичного накопления и сохранения больших массивов разнородных данных. Однако, обновление (корректировка) уже имеющихся данных в файле с такой организацией крайне трудоемка, поскольку для поиска и доступа применим только полный перебор всех записей. Часть памяти должно отводиться для сохранения служебной информации (сведения о полях), что, при больших размерах файлов, приводит к существенному уровню «непроизводительного» использования памяти.

3 Файловые системы. Логическая организация файлов. 2. Последовательный файл ЗАПИСИЗАПИСИ Наиболее распространенный способ логической организации файлов (таблица). Записи в таком файле состоят из одинакового количества полей фиксированной длины, расположенных в одном порядке. Поскольку тип, длина и позиция каждого поля известны, то сохранению подлежит только собственно его значение. Атрибутами (характеристиками) данного способа логической организации файлов являются имя и длина каждого поля. Одно (обычно первое) поле в каждой записи называется ключевым полем. С помощью него каждая запись файла идентифицируется однозначно, так как значения ключевого поля для различных записей различны. Записи в последовательном файле сохраняются в алфавитном (если ключевое поле символьное) или числовом порядке. Последовательный файл удобен для хранения больших структурированных наборов данных, которые не подвергаются частным операциям корректировки и должны обрабатываться преимущественно целиком. Обращение к отдельной записи последовательного файла (в частности, поиск) занимает достаточно много времени. Дополнение файла новыми записями весьма трудоемки и, как правило, не могут выполняться в режиме реального времени. Типичной технологией, применяемой для корректировки последовательного файла, является: (1) накопление изменений в специальном рабочем файле (журнале), имеющем точно такую же структуру записей, как исходный файл; (2) в режиме администрирования выполняется слияние основного файла и журнала в новый файл с корректной расстановкой ключей (значений ключевого поля).

4 Файловые системы. Логическая организация файлов. 3. Индексно-последовательный файл Уровни 2 индексации 1 N Главный файл Файл переполнения При таком способе логической организации файла выделяются три структуры: главный файл (собственно содержащий данные), который является обычным последовательным файлом с ключевым полем; индексный файл – в общем случае многоуровневая структура, каждый уровень которой является последовательным файлом с записями из двух полей: собственное ключевое поле и указатель на номер ключа в главном файле. В файле переполнения, который имеет структуру главного файла, помещаются все изменения (дополнения новых записей).

5 Файловые системы. Логическая организация файлов Поиск записи 5: доступ к записи за 7 шагов. Поиск в обычном последовательном файле занял бы 4 шага Поиск начинается в индексе высшего уровня, в котором ищется наибольший элемент, не превышающий искомое значение ключа, после чего поиск производится в индексе следующего уровня и так далее до передачи процесса поиска в главный файл.

6 Файловые системы. Логическая организация файлов Поиск записи 9: доступ к записи за 7 шагов. Поиск в обычном последовательном файле занял бы 8 шагов Чем больше записей в файле, тем эффективнее поиск записей с большими значениями ключевого поля.

7 Файловые системы. Логическая организация файлов Поиск записи 17: доступ к записи за 9 шагов. Поиск в обычном последовательном файле занял бы 16 шагов При организации индексно- последовательного файла обычно ограничиваются одним уровнем индексации. Чем чаще установлены «метки» перехода в индексном файле, тем эффективнее осуществляется поиск записей. Задание: посчитать за сколько шагов будет найдена запись с номером 22.

8 Файловые системы. Логическая организация файлов Главный файлФайл переполнения Служебное поле: если ненулевое значение, то это указатель на номер записи в файле переполнения Последовательная обработка файла в текущем режиме происходит следующим образом: 1) Обрабатываются записи главного файла до тех пор пока в служебном поле не будет обнаружена ссылка на файл переполнения. 2) Обработка передается в файл переполнения пока не будет обнаружено нулевое значение в служебном поле. 3) Обработка возвращается в главный файл с записи, следующей за записью в которой была обнаружена ссылка на файл переполнения или обработка завершается. Периодически в автоматическом режиме производится слияние главного файла с файлом переполнения с корректной расстановкой записей по ключам, очисткой файла переполнения и обнулением значений служебного поля в записях главного файла. Индексно-последовательная организация файла при сохранении базового принципа последовательного файла значительно убыстряет поиск и обработку записей.

9 Файловые системы. Логическая организация файлов. 4. Индексированный файл ЗАПИСИЗАПИСИ П1 z1z1 z2z2 z3z3 z4z4 z5z5 z6z Полный индекс: индексируемое поле (П1) содержится во всех записях файла. ЗАПИСИЗАПИСИ П2 П1 П2П1 z1z1 z2z2 z3z3 z4z4 z5z5 z6z Частичный индекс: индексируемое поле (П2) содержится в некоторых записях файла. Главное отличие: возможность индексирования по всем полям, которые могут стать объектом для поиска.

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

11 Файловые системы. Логическая организация файлов. П1 «Фамилия»П2 «Имя»П3 «Возраст»П4 «Должность» ИвановНиколай30Инженер 1к ПетровИван25Техник СидоровПетр40Инженер 2к НиколаевСергей41Рабочий СергеевАндрей25Рабочий 1Иванов 2Николаев 3Петров 4Сергеев 5Сидоров Лексико-графический порядок по полю «Фамилия» Индексный файл по полю «Фамилия» / Числовой порядок по полю «Возраст» Индексный файл по полю «Возраст» 1Инженер 1к 2Инженер 2к 3Рабочий 4 5Техник /4 5 Лексико-графический порядок по полю «Должность» Индексный файл по полю «Должность»

12 Файловые системы. Логическая организация файлов. Сводная индексная таблица (разрешение неоднозначности в индексных файлах производится автоматически, чаще всего по времени создания записи) Индекс «Фамилия»Индекс «Возраст»Индекс «Должность» Запрос: Найти всех инженеров старше 30 лет, фамилия которых начинается до буквы «С». 1 Индекс «Фамилия» < 4 ; 3 Индекс «Возраст» 5 ; 1 Индекс «Должность» 2 (Иванов) (Петров) (Сидоров) (Николаев) (Сергеев) Результат поиска: запись 1 «Иванов»

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

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

15 Файловые системы. Логическая организация файлов. Основная информация Имя файлаКак правило, символьная строка, уникальная в соответствующем каталоге Тип файлаТестовый, двоичный, архивный, загружаемый модуль и т.д. Способ организации файла Для ОС, поддерживающих различные способы организации файлов Адресная информация Том (носитель)Определяет устройство (логическое или физическое), на котором размещен файл Начальный адресНачальный физический адрес в устройстве (например, номер цилиндра, дорожки или номер блока) Занимаемый размерТекущий размер файла в байтах (блоках) Выделяемый размерМаксимально возможный размер файла Информация об управлении доступом ВладелецПользователь (создатель), которому передано управление файлом Информация о доступе Имя и пароль каждого авторизированного пользователя файла Допустимые действияУправление чтением, записью, пересылкой файла

16 Файловые системы. Логическая организация файлов. Информация об использовании Дата созданияДата первоначального размещения файла в каталоге СоздательОбычно (но не всегда) текущий владелец Дата последнего чтения Дата последней операции чтения данных из файла Дата последнего изменения Дата последних процедур обновления, вставки и/или удаления записей Последний пользователь Пользователь, обращавшийся последним к файлу для чтения Дата последнего резервного хранения Дата создания последней копии (резервной) файла на другом носителе Текущее использование Информация о текущих действиях производимых с файлом: о процессах, открывших файл; о том, заблокирован ли файл для доступа; обновлен ли файл в ОП, но еще не обновлен на диске и т.п.

17 Файловые системы. Логическая организация файлов. Вся система каталогов на диске образует иерархическую структуру. В зависимости от типа файловой системы структура каталогов бывает древовидной (система FAT32 ОС Windows) или сетевой (файловая система ОС UNIX). K1 K11 K121 F1 K12 K13 F4 F2 F3 K122 F1 F5 F6 ? Для древовидной структуры один и тот же файл (по содержанию), находящийся в разных каталогах является разными файлами. Для сетевой структуры один файл может содержаться в разных каталогах.

18 Файловые системы. Логическая организация файлов.