3.4.1.5. Цепь подобных записей

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

Пусть основной файл имеет вид:

сотрудник

№ п/п	ФИО	ученая степень	научное звание	контактные данные	название (кафедры)	название (должности)
1	Иванов И.И.	к.т.н.	доцент	234567	СУиВТ	доцент
2	Петров П.П.	к.т.н.	нет	456789	ТАМ	доцент
3	Сидоров С.С.	нет	нет	123456	СУиВТ	ассистент
4	Яковлев Я.Я.	д.т.н.	профессор	345678	ТАМ	профессор

Вторичными ключами являются ученая степень, научное звание, название (кафедры), название (должности). Построим индексы для этих ключей:

ученая степень	ссылки		научное звание	ссылки		название (кафедры)	ссылки		название (должности)	ссылки
д.т.н.	4		доцент	1		СУиВТ	1		ассистент	3
к.т.н.	1		нет	2		ТАМ	2		доцент	1
нет	3		профессор	4					профессор	4

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

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

сотрудник

№ п/п	ФИО	ученая степень	№ п/п	научное звание	№ п/п	контактные данные	название (кафедры)	№ п/п	название (должности)	№ п/п
1	Иванов И.И.	к.т.н.	2	доцент	-	234567	СУиВТ	3	доцент	2
2	Петров П.П.	к.т.н.	-	нет	3	456789	ТАМ	4	доцент	-
3	Сидоров С.С.	нет	-	нет	-	123456	СУиВТ	-	ассистент	-
4	Яковлев Я.Я.	д.т.н.	-	профессор	-	345678	ТАМ	-	профессор	-

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

Пусть надо найти фамилии и инициалы всех сотрудников, работающих в должности ассистента. Очевидно, К_доступ=<название (должности)=ассистент>. Поиск осуществляется последовательным выполнением шагов:

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

2. по полю ссылки выясняется номер записи основного файла с искомым ключом доступа – это запись с номером 3;

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

4. в соответствии со значением поля № п/п для поля название (должности) в основном файле определяется номер следующей записи основного файла с аналогичным значением вторичного ключа – поскольку данное поле не содержит ссылки, это означает, что цепочка записей закончилась, следовательно, список сотрудников сформирован; алгоритм заканчивает работу.

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

Например, основной список представлен таблицей:

сотрудник

№ п/п	ФИО	ученая степень	№ п/п	научное звание	№ п/п	контактные данные	название (кафедры)	№ п/п	название (должности)	№ п/п
1	Иванов И.И.	к.т.н.	2	доцент	-	234567	СУиВТ	3	доцент	2
2	Петров П.П.	к.т.н.	-	нет	3	456789	ТАМ	4	доцент	-
3	Сидоров С.С.	нет	-	нет	-	123456	СУиВТ	-	ассистент	-
4	Яковлев Я.Я.	д.т.н.	-	профессор	-	345678	ТАМ	-	профессор	-

Индексы модифицированы и показаны в таблицах (дополнительные поля показаны заливкой):

ученая степень	ссылки	длина цепочки		научное звание	ссылки	длина цепочки		название (кафедры)	ссылки	длина цепочки		название (должности)	ссылки	длина цепочки
д.т.н.	4	1		доцент	1	1		СУиВТ	1	2		ассистент	3	1
к.т.н.	1	2		нет	2	2		ТАМ	2	2		доцент	1	2
нет	3	1		профессор	4	1						профессор	4	1

Значения полей длина цепочки – это количество записей основного файла с соответствующим значением вторичного ключа.

Пусть надо определить, какие сотрудники работают в должности доцентов и не имеют ученой степени. Очевидно, К_доступ=<название (должности)=доцент, ученая степень=нет). Задача решается следующим образом:

1. в индексах для вторичных ключей название (должности) и ученая степень ищутся записи со значениями полей доцент и нет: это, соответственно, записи с номерами 2 и 3;

2. анализируется, для какого индекса поле длина цепочки имеет минимальное значение: очевидно, длина цепочки для ключа со значением нет короче, чем для ключа со значением доцент, поэтому для поиска в основном файле определяется ключ ученая степень со значением нет;

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

4. у выбранного элемента анализируется поле название (должности): его значение равно ассистент: данная запись не удовлетворяет условиям поиска, а потому никакого вывода данных пользователю не происходит;

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