Конспект лекций для специальности «Прикладная информатика в экономике» (стр. 5 )

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

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

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

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

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

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

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

сотрудник

ФИО	ученая степень	№ п/п	научное звание	№ п/п	контактные данные	название (кафедры)	№ п/п	название (должности)	№ п/п
	к. т.н.	2	доцент	-	234567	СУиВТ	3	доцент	2
	к. т.н.	-	нет	3	456789	ТАМ	4	доцент	-
	нет	-	нет	-	123456	СУиВТ	-	ассистент	-
	д. т.н.	-	профессор	-	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)  в соответствии со значением поля № п/п для поля ученая степень определяется номер следующей записи основного файла с аналогичным значением вторичного ключа. Поскольку это поле не содержит ссылки, это означает, что цепочка записей закончилась, следовательно, список сотрудников сформирован (он пуст); алгоритм заканчивает работу.

3.4.1.6. Инвертированные файлы

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

Пусть основной файл показан в таблице:

сотрудник

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

Соответствующие индексы показаны в таблицах:

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

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