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

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

В некоторых файлах записи имеют несколько ключей. За­пись закупка может иметь различные НОМЕР поставщика и номер покупателя, каждый из которых является ключом.

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

Основные проблемы при адресации файла можно сформули­ровать следующим образом:

• по первичному ключу определить местоположение записи с данным ключом;

• организовать набор записей, чтобы поиск потребовал как можно меньше затрат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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