8.4. Организация поиска данных

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

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

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

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

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

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

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

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