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

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

Например, основной список представлен таблицей 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