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

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

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

    

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

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

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

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

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

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

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

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

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

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

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

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

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

     

                                            Таблица 41

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

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

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