Способы адресации и методы доступа к записям

Как уже отмечалось выше, записи логического файла идентифицируются с помощью уникальной последовательности символов или некоторого числа — ключа. Таким ключом обычно является значение поля, расположенное в каждой записи в одной и той же позиции. Иногда бывает необходимо объединить несколько полей, чтобы обеспечить уникальность ключа, который в этом случае называется сцепленным ключом. В некоторых файлах записи имеют несколько ключей. Запись закупка может иметь различные НОМЕР ПОСТАВЩИКА и НОМЕР ПОКУПАТЕЛЯ, каждый из которых является ключом.

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

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

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

Существует несколько различных способов адресации и поиска записей, например, на основе упорядочения, различных индексов, преобразования «ключ—адрес».

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

Блочный поиск. Если записи упорядочены по ключу, то при сканировании файла не требуется чтение каждой записи. ЭВМ могла бы, например, просматривать каждую сотую запись по последовательности возрастания ключей. При нахождении записи с ключом большим, чем искомое значение, просматриваются последние 99 записей, которые были пропущены.

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

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

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

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

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

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

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

• ключ записи преобразуется в псевдослучайное число, находящееся в диапазоне от единицы до числа блоков, используемых для размещения записей;

• число преобразуется в адрес блока и, если в нем есть свободное место, то логическая запись размещается там;

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

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