8.2.2. Последовательная организация

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

Если была считана запись Ri, то следующая доступная запись – это Ri+1.

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

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

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

Единственной разрешенной для использования функцией доступа является функция «следующий».

Если текущая запись не является последней, то логический адрес следующей записи определяется выражением:

Адрес(текущий) + размер(текущий)

8.2.3. Индексная организация

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

При организации прямого доступа функции доступа выражаются в виде зависимостей от атрибутов записей (значений полей).

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

Ключом может быть одно или несколько полей.

1. Случай единственного ключа

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

Доступ осуществляется с помощью функции ПОИСК(КЛЮЧ,АЛ), которая:

1. Либо выдает логический адрес (АЛ) записи, если поиск завершился успехом;

2. Либо сигнализирует, что такой записи нет.

2. Адресация перемешиванием

В этом методе процедуру ПОИСК пытаются реализовать путем построения функции:

АЛ = f(КЛЮЧ);

Функция f называется функцией перемешивания, хеширования.

Сложность состоит в обеспечении условия:

f(КЛЮЧ1) <> f(КЛЮЧ2)

Поскольку этого почти никогда не удается добиться, то используют сочетание прямого и последовательного доступа.

Прямым доступом выбирают группу записей, а из этой группы последовательным доступом выбирают нужную запись.

3. Индексированные файлы

Этот метод поиска используют в сочетании с упорядоченностью множества ключей. Строится таблица соответствия (индексная таблица) между ключами и логическими адресами.

Индексная таблица

КЛЮЧ 1	…
	А Л1
КЛЮЧ 2	…
	АЛ2
КЛЮЧ 3	…
	А Л3
	…

…

Запись 2

…

Запись 1

…

Запись 3

…

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

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

8.3.1. Последовательное размещение

При последовательном размещении файл занимает совокупность последовательных блоков на носителе.

Такой способ является единственно возможным на магнитной ленте.

Последовательный доступ очень быстрый.

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

8.3.2. Размещение без использования свойства смежности

Сцепленные блоки

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

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

Таблица размещения

Для повышения эффективности прямого доступа все указатели помещаются в одну таблицу – таблицу размещения блоков.

Сцепленная таблица размещения

Для снятия ограничений по расширению файла таблицу можно организовать из сцепленных таблиц.

Многоуровневая таблица размещения

8.4. Дескриптор файла и реализация основных функций доступа к файлу

8.4.1. Состав дескриптора файла

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

Информация о физической организации

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

Информация об использовании

1. Информация о состоянии открыт/закрыт режим доступа (запись, чтение, добавление) текущее смещение степень разделения (число пользователей, одновременно открывших файл)

2. Информация о содержимом (тип) текст бинарный каталог

3. Информация о логической структуре записи фиксированного/переменного размера кратность размера записи размеру физического блока

4. Информация о прошлом использовании число открытий средний интервал обращений средняя степень разделения дата последнего обращения дата последней модификации

8.4.2. Реализация основных функций доступа

К основным функциям доступа к файлу относятся следующие функции:

1. Создание;

2. Уничтожение;

3. Открытие;

4. Закрытие;

5. Чтения;

6. Записи.

Операция создания

Windows:

HANDLE CreateFile(

LPCTSTR имя файла,

DWORD режим доступа, (чтение, запись)

DWORD режим разделения,

LPSECURITY_ATTRIBUTES атрибуты безопасности,

DWORD правила создания,

DWORD флаги и атрибуты,

HANDLE файл-шаблон

);

Linux:

int creat(

char * имя файла,

mode_t права доступа (владелец, группа, остальные)

);

Операция уничтожения

Windows:

BOOL DeleteFile(

LPCTSTR имя файла

);

Linux:

int remove(

char * имя файла

);

Операция открытия

Windows: (пример вызова)

HANDLE hFile = CreateFile(

name, // имя файла

GENERIC_READ, // открыть на чтение

FILE_SHARE_READ, // разделяемый на чтение

NULL, // нет атрибута безопасности

OPEN_EXISTING, // открыть, если существует

FILE_ATTRIBUTE_NORMAL, // нормальный файл

NULL // нет шаблона

);

Linux:

int open(

char * имя файла,

int режим доступа (чтение, запись)

)