Прямой доступ к файлу

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

В методе адресации перемешиванием логический адрес (АЛ) определяется выражением

АЛ = f (ключ)

где f – функция перемешивания (кэширования, расстановки или рассеивания).

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

1) для всех записей файла с ключом КЛ
0 £ f(кл) £ n;

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

На практике очень трудно удовлетворить свойству (2). Необходимо допустить возможность конфликтов. Можно привести следующий пример конфликтной ситуации. Ключом является выражение Автор = ‘Иванов’. Т.е. необходимо отыскать запись, которая определяет книгу, написанную Ивановым. Очевидно, что таких книг может быть несколько. В случае конфликта необходим дополнительный этап для определения искомой записи, который называется обработка конфликтов.

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

В методе индексированного доступа отношение между ключом и логическим адресом оформляется в виде таблицы, называемой индексом. Этот метод существенно ускоряет процедуру поиска записи в файле. Обратимся вновь к примеру файла «перечень книг», в котором каждая запись состоит из атрибутов автор, издатель, год выпуска и др. пусть ключом является выражение Автор = <фамилия автора>. Упорядочим всех авторов в порядке алфавита.

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