1. Метод складывания. Распределение элементов по бакетам показано в таблице 22:

                               

                                                               Таблица 22

Номер бакета	Содержимое бакета
0001
0002
0003	Скворцов	Олег	иванович	02544	пр. Мира, 45 - 3
0004	Соколов	Юрий	Кузьмич	01278	ул. Леонова, 23 - 98
	Супруненко	Виктор	Егорович	02347	Каштановая аллея, 23 - 5
0005
0006
0007
0008	Строков	Иван	Иванович	02343	ул. Красная, 9 - 2
0009

Как показывает анализ, все три метода с одинаковой равномерностью заполняют бакеты: один бакет содержит два элемента, остальные – по одному, т.е. методы равноэффективны.

Решим задачу просмотра элемента.

Пример 10. По ключу Супруненко требуется просмотреть домашний адрес студента, т.е. q^{просмотр} = (Фамилия = Супруненко, Домашний адрес), где К_доступ = Супруненко. Пусть линейный список после размещения соответствует таблице 22. Задача решается следующим образом:

1. по приведенным выше алгоритмам рандомизации определяется номер бакета для нужного ключа доступа – это 0004;

1. в данном бакете находится линейный список элементов, в общем случае, не упорядоченный по ключу. Поэтому к нему применим метод последовательного сканирования. Анализируется первый элемент бакета с ключом Соколов: Соколов = Супруненко;

1. поскольку условие не выполняется, выбирается следующий элемент;

1. его ключевое поле сравнивается с ключом доступа: Супруненко = Супруненко; условие выполняется, поэтому выводится результат – Каштановая аллея, 23 – 5. Алгоритм заканчивает работу.

Способы доступа по вторичному ключу

Доступ по вторичному ключу выполняется следующими способами: с помощью элементов, связанных в цепь, с помощью оптимизированных цепочек элементов и с помощью инвертированных списков.

Элементы, связанные в цепь

К исходному линейному списку не предъявляется никаких требований.  К нему достраиваются дополнительные списки – индексы - в количестве, соответствующем числу вторичных ключей доступа. Элементы таких списков имеют два поля: первое – значение вторичного ключа из основного списка, второе – ссылка на первый элемент в основном списке с таким же значением вторичного ключа. Сами элементы основного списка также модифицируются: они дополняются полями в количестве, соответствующем числу вторичных ключей доступа. Каждое поле служит для организации цепочек записей с одним значением вторичного ключа.

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

                                       Таблица 23

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

Вторичными ключами являются Шифр учебной группы, Дисциплина, Оценка. Построим индексы для этих ключей (таблицы 24 – 26):

Таблица 24                             Таблица 25                Таблица 26

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

Как видно из таблиц 24 – 26, каждый индекс содержит поле со всеми значениями соответствующего вторичного ключа из основного списка и поле (озаглавлено Ссылка), в котором указывается номер элемента основного списка, где впервые встречается соответствующее значение вторичного ключа.  Значения вторичных ключей в индексах упорядочены по возрастанию, так что с индексами можно работать как с упорядоченными линейными списками (в роли первичных ключей таких списков выступают вторичные ключи основных списков).

Модифицируем также и основной список. Для удобства поместим дополнительные поля  (они выделены заливкой) справа от соответствующего вторичного ключа. Получим таблицу 27:

       Таблица 27

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

Рассмотрим, например, как сформировано поле Ссылка для вторичного ключа Шифр учебной группы:

1. элемент с номером 1 имеет ссылку на элемент с номером 3: это следующий элемент основного списка со значением шифра группы 01-ИЭ;

1. элемент с номером 3 имеет ссылку на элемент с номером 5: это следующий элемент основного списка со значением шифра группы 01-ИЭ;

1. элемент с номером 5 – последний в основном списке со значением вторичного ключа Шифр учебной группы, равным 01-ИЭ. Поэтому он имеет пустую ссылку «-»;

1. элемент с номером 2  - единственный в основном списке со значением вторичного ключа 02-ВТ, поэтому он имеет пустую ссылку «-»;

1. элемент с номером 4  - единственный в основном списке со значением вторичного ключа 01-АС, поэтому он имеет пустую ссылку «-».

Аналогично можно проследить образование ссылок у остальных вторичных ключей.

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

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

1. по Индексу для ключа Дисциплина определяется элемент со значением поля Дисциплина, равным Информатика (поскольку индекс – это упорядоченный линейный список, к нему применяются рассмотренные ранее методы, например, метод последовательного сканирования, анализ работы которых в данном случае не приводится). Это первый элемент индекса;

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

1. в основном списке выбирается первый элемент. Выводится фамилия и инициалы студента – это Иванов И.И.;

1. в соответствии со значением поля Ссылка для поля Дисциплина  определяется номер следующего элемента основного списка с аналогичным значением вторичного ключа – это элемент № 3;

1. выбирается третий элемент. Выводится фамилия и инициалы студента – это Сидоров С.С.;

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

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

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

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

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

Поскольку процедуры добавления подробно рассматривались ранее, проследим, как в результате модифицировались основной список и три индекса (таблицы 28 – 31). Измененные значения ссылок выделены заливкой; новые элементы в основном списке и в таблице 31 выделены полужирным шрифтом:

         Таблица 28

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

Таблица 29                               Таблица 30                               Таблица 31

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