Способы доступа по первичному ключу

Доступ по первичному ключувыполняется следующими способами: последовательное сканирование, блочный, двоичный, индексно-последовательный, индексно-произвольный, рандомизация.

Последовательное сканирование

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

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

· для неупорядоченного списка сравнение повторяется до достижения конца списка. В этом случае, если совпадения ключей так и не было, делается вывод об отсутствии нужного элемента в списке;

· для упорядоченного списка проверяется условие, например, превышения значения ключа доступа Кдоступ значения ключа Кэ: если список упорядочен по возрастанию, поиск продолжается; если по убыванию – поиск прекращается ввиду отсутствия нужного элемента.

Пример 1. Для списка из таблицы 1 требуется просмотреть адрес студента по фамилии Скворцов, т.е. qпросмотр = (Фамилия = Скворцов, Домашний адрес), а Кдоступ = Скворцов (здесь и далее значение ключа доступа выделяется курсивом).

Доступ осуществляется последовательным выполнением шагов:

1. выбирается первый элемент списка;

2. ключевое поле элемента Кэ = Строков сравнивается с ключом доступа: Строков = Скворцов;

3. поскольку поля не равны, выбирается следующий - второй - элемент списка;

4. ключевое поле элемента сравнивается с ключом доступа: Скворцов = Скворцов;

5. поскольку поля равны, выводится адрес: пр. Мира, 45 – 3; алгоритм заканчивает работу.

Пример 2. Пусть требуется просмотреть домашний адрес студента, отсутствующего в списке, например, по фамилии Сидоров, т.е. qпросмотр = (Фамилия = Сидоров, Домашний адрес), где Кдоступ = Сидоров.

Работа алгоритма для неупорядоченного списка (таблица 1):

1. выбирается первый элемент списка;

2. ключевое поле элемента сравнивается с ключом доступа: Строков = Сидоров;

3. поскольку поля не равны, выбирается следующий - второй - элемент списка;

4. ключевое поле элемента сравнивается с ключом доступа: Скворцов = Сидоров;

5. вследствие того, что поля не равны, выбирается следующий - третий - элемент списка;

6. ключевое поле элемента сравнивается с ключом доступа: Соколов = Сидоров;

7. из-за того, что поля не равны, делается попытка обратиться к следующему элементу списка;

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

Работа алгоритма для упорядоченного списка из таблицы 2 (список упорядочен по возрастанию первичного ключа – фамилии):

1. выбирается первый элемент списка;

2. ключевое поле элемента сравнивается с ключом доступа: Скворцов = Сидоров;

3. поскольку поля не равны, определяется возможность присутствия искомого элемента в продолжении списка. Для этого проверяется другое условие: Скворцов < Сидоров (напомним, что список упорядочен по алфавиту фамилий – первичных ключей);

4. условие не выполняется, поэтому выдается диагностическое сообщение об отсутствии искомого элемента в списке, и алгоритм заканчивает работу.

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

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

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

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