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

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

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

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

Таблица 34

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 37