Инвертированные списки

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

Например, пусть основной список показан в таблице 23. Соответствующие индексы показаны в таблицах 38 – 40:

Таблица 38 Таблица 39 Таблица 40

Расположение всех ссылок для некоторого вторичного ключа в одном поле позволяет исключить перебор элементов в цепочке элементов при их поиске.

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

Пример 16. Пусть надо просмотреть список всех студентов, сдававших информатику, т.е. q^{просмотр} = (Дисциплина = Информатика, ФИО студента), где К _доступ = Информатика. Поиск осуществляется последовательным выполнением шагов:

1. по индексу для ключа Дисциплина (таблица 39) находится соответствующий элемент: это первый элемент в списке;

2. выбираются ссылки для этого элемента: это множество {1, 3};

3. по основному списку (таблица 23)выбираются последовательно элементы с номерами 1 и 3 и выводится содержимое поля ФИО студента для этих элементов; получаем список - Иванов И.И. и Сидоров С.С. Работа алгоритма закончена.

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

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

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

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

Таблица 41

Таблица 42 Таблица 43 Таблица 44