Оптимизированные цепочки элементов

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

Например, основной список  представлен таблицей 27. Индексы модифицированы и показаны в таблицах 32 – 34 (дополнительные поля показаны заливкой). Значения полей Длина цепочки – это количество элементов основного списка с соответствующим значением вторичного ключа.

                  

     Таблица 32                                         Таблица 33 

№ п/п	Шифр учебной группы	Ссылка	Длина цепочки		№ п/п	Дисциплина	Ссылка	Длина цепочки
1	01-АС	4	1		1	Информатика	1	2
2	01-ИЭ	1	3		2	Программирование	2	2
3	02-ВТ	2	1		3	Физика	5	1

Таблица 34

№ п/п	Оценка	Ссылка	Длина цепочки
1	3	3	1
2	4	2	2
3	5	1	2

Пример 14. Пусть надо просмотреть список студентов группы 01-ИЭ, сдававших экзамен по Физике, т.е. q^{просмотр} = (Шифр учебной группы = 01-ИЭ, Дисциплина = Физика, ФИО студента), где К_доступ =  01-ИЭ, Физика.

Задача решается следующим образом:

1. в индексах для вторичных ключей Шифр учебной группы и Дисциплина ищутся элементы со значениями полей 01-ИЭ и Физика: это, соответственно, элементы с номерами 2 и 3 (см. таблицы 32 и 33);

1. анализируется, для какого индекса Длина цепочки имеет минимальное значение: очевидно, длина цепочки для ключа со значением Физика короче, чем для ключа со значением 01-ИЭ, поэтому для поиска в основном списке определяется ключ Дисциплина со значением Физика;

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

1. у выбранного элемента анализируется поле Шифр учебной группы: его значение равно 01-ИЭ, поэтому данный элемент удовлетворяет обоим условиям доступа, а потому фамилия и инициалы студента Яковлев Я.Я. выводятся в качестве первого результата;

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

Рассмотрим, как решается задача добавления.

Пример 15. Пусть в основной список таблицы 27 надо добавить элемент со структурой:

ФИО студента	Шифр учебной группы	Дисциплина	Оценка
Ковалев К.К.	02-ВТ	Программирование	2

т.е. q^{добавление} = (ФИО студента = Ковалев К.К., Шифр учебной группы = 02-ВТ, Дисциплина = Программирование, Оценка = 2), где К_доступ = Ковалев К.К.

Модифицированный основной список идентичен таблице 28, а три индекса показаны в таблицах 35 – 37. Измененные значения ссылок, длин цепочек, а также новый элемент в одном из индексов выделены заливкой; новый элемент в основном списке выделен полужирным шрифтом:

              Таблица 35                                                Таблица 36   

№ п/п	Шифр учебной группы	Ссылка	Длина цепочки		№ п/п	Дисциплина	Ссылка	Длина цепочки
1	01-АС	5	1		1	Информатика	1	2
2	01-ИЭ	1	3		2	Программирование	2	3
3	02-ВТ	2	2		3	Физика	6	1

Таблица 37

№ п/п	Оценка	Ссылка	Длина цепочки
1	2	2	1
2	3	4	1
3	4	3	2
4	5	1	2