3.4.1.2. Индексно-последовательная организация

Записи файла должны быть упорядочены по первичному ключу. Аналогично блочному методу доступа, файл делится на виртуальные блоки размером N. Затем ключевые поля последних записей блоков вместе с порядковыми номерами этих записей в файле включаются в дополнительные файлы, которые называются индексами. Видно, что данный способ использует дополнительные построения, - назовем тогда исходный файл основным.

Пусть основной файл соответствует реляционной модели для сущности кафедра из рассмотренного ранее примера и имеет вид (здесь и далее графа № п/п не входит в состав записей файла, а формируется операционной системой при создании файла):

кафедра

№ п/п	название	шифр в вузе
1	АПП	238
2	СУиВТ	239
3	ТАМ	145
4	Экономики	056

Для этого файла N = 4. Это значит, что индекс будет иметь вид (графа ссылки формируется как номера соответствующих записей основного файла):

название	ссылки
СУиВТ	2
Экономики	4

Доступ к записям вновь осуществляется по ключу К_доступ, который указывается пользователем в запросе. Однако алгоритм поиска начнет его не с основного файла, а с индекса, интерпретируя его как обычный файл с последовательной организацией записей, и применит к нему один из описанных ранее методов доступа, например, последовательное сканирование. Тогда ключевое поле К каждой записи индекса будет сравниваться с ключом К_доступ. Возможны варианты:

1. К_доступ=К – запись найдена, известен ее номер в основном файле, по этому номеру она считывается из него и предоставляется пользователю, алгоритм заканчивает работу;

2. К_доступ>К – считывается следующая запись индекса. Если индекс закончен, алгоритм заканчивает работу – запись не найдена. Иначе вновь ключевое поле К очередной записи индекса сравнивается с ключом К_доступ; возможные варианты исхода сравнения описаны выше, начиная с п.1);

3. К_доступ<К – обнаружен блок основного файла, который может содержать искомую запись. Выполняется переход к найденному блоку по полю индекса ссылки – к последней его записи. Все записи блока основного файла последовательно сканируются в поисках искомой записи в соответствии с рассмотренным ранее методом последовательного сканирования.

3.4.1.3. Индексно-произвольная организация

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

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

Пусть основной файл вновь соответствует реляционной модели для сущности кафедра из рассмотренного ранее примера и имеет вид:

кафедра

№ п/п	название	шифр в вузе
1	АПП	238
2	СУиВТ	239
3	ТАМ	145
4	Экономики	056

В данной модели, как отмечалось ранее, два первичных ключа – название и шифр в вузе. Пусть предполагается искать данные по обоим ключам, причем, в основном поиск будет вестись по ключу название. Тогда по этому ключу упорядочиваются записи в файле (что и сделано в таблице). Видно, что второй ключ имеет неупорядоченные значения.

Формируются два индекса: первый – для ключа название – аналогичен предыдущему примеру:

название	ссылки
СУиВТ	2
Экономики	4

Второй индекс имеет вид:

шифр в вузе	ссылки
056	4
145	3
238	1
239	2

Видно из второй таблицы, что значения ключа шифр в вузе упорядочены по возрастанию. Это позволяет данный индекс рассматривать как упорядоченный последовательный файл и применять к нему рассмотренные методы доступа в разделе «Последовательная организация».