Библиотечная структура данных

Эта структура (рис.2.9) представляет собой файл, состоящий, по сути, из последовательных подфайлов - наборов данных, имеющих собственное имя в составе данного файла. Такие отдельные наборы данных называют разделами файла. Расположение разделов в файле (библиотеке) в общем случае никак не упорядочено. Они записываются в файл на собственно информационный уровень по мере поступления. Расположение каждого отдельного раздела фиксируется в каталоге библиотеки, который размещен на учетном уровне файла. Для сокращения поиска элементы каталога, как правило, располагаются в алфавитном порядке следования имен разделов.

Рис. 2.9

Обращение к каждому отдельному разделу, т.е. элементу файла с библиотечной структурой, происходит через каталог.

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

Методы доступа к содержимому файлов

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

Последовательный доступ

При последовательной организации записи упорядочены; они могут обозначаться последовательными целыми числами. Однако эти порядковые номера записей не могут использоваться для функций доступа - единственной разрешенной для использования функцией является «следующий». Если текущая запись не является последней в файле, логический адрес следующей за ней записи определяется выражением

АДРЕС (текущий) + РАЗМЕР (текущий).

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

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

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

2.4.2. Прямой дост­уп

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

В файле с одним ключом каждая запись содержит единственный ключ, который однозначно ее идентифицирует; оставшаяся часть записи содержит информацию. Таким образом, две разные записи имеют всегда два разных значения ключа. Процедура поиска записи (точнее, ее логического адреса) по значению ключа ПОИСК (КЛЮЧ, АЛ) для каждого значения ключа:

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

- либо сигнализирует, что такой записи не существует (случай неудачи).

Процедура поиска реализует выбор элементарных операций прямого доступа : чтения, записи, модификации.

Операции чтения и модификации указывают на ошибку в случае сбоя процедуры ПОИСК; и наоборот, операция записи указывает на ошибку в случае успеха процедуры ПОИСК.

Процедура поиска записи наиболее часто реализуется двумя методами: методом адресации перемешиванием и введением индекса.

В методе адресации перемешиванием строится некоторая функция

АЛ = f (КЛЮЧ),

называемая функцией перемешивания (функцией хеширования).

Идеальная функция перемешивания реализует равномерную расстановку совокупности ключей. Предположим для npocтоты, что логическими адресами для файла из п записей являются 0, ..., n - 1. Функция перемешивания должна обладать следующими свойствами:

- для каждой записи файла с ключом КЛ 0 < f (KЛ) < n ;

- для каждой пары записей f (KЛl) № f (KЛ2), если КЛ1 № КЛ2.

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

- вероятность появления разных значений ключа;

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

На рис.2.10 схематично показан прямой доступ с помощью адресации перемешиванием.

Рис.2.10

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

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

Рис.2.11.

Пусть n - число записей файла. Если индекс организован последовательно в соответствии с порядком ключей и поиск ключа осуществляется последовательным просмотром, среднее число сравнений (и, следовательно, обращений к индек­с - таблице) равно n/2. Это число может быть уменьшено за счет древовидной организации индекс - таблицы.

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

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

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

Рис.2.12

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

Другие методы доступа

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

Если же последовательность обработки записей предвидеть нельзя, применяются базисные методы доступа. Базисными методами доступа читаются и записываются физические блоки. Блокирование и деблокирование (если они необходимы для конкретного приложения) выполняет сам пользователь. Управление возвращается в программу до завершения операции ввода-вывода. Различают следующие базисные методы доступа:

- BDAM (Basic Direct Access Method) - базисный прямой метод доступа - записи считываются и записываются по их адресам на дисках;

- BSAM (Basic Sequential Access Method) - базисный последовательный метод доступа - метод применим к последовательным или библиотечным файлам; записи выстроены в последовательность и единицей обмена является физический блок;

- ВРАМ (Basic Partitioned Access Method) - базисный библиотечный метод доступа - с помощью этого метода в библиотечных файлах обновляются директории (для работы с данными применяют BSAM);

- BISAM (Basic Indexed Sequential Access Method) - базисный индексно-последовательный метод доступа - этот метод применим только к индексно-последовательным файлам.

Не нашли, что искали? Воспользуйтесь поиском по сайту: