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

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

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

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

кафедра

№ п/п	название	шифр в вузе
	АПП
	СУиВТ
	ТАМ
	Экономики

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

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

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

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

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

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

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

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

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

кафедра

№ п/п	название	шифр в вузе
	АПП
	СУиВТ
	ТАМ
	Экономики

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

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

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

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

шифр в вузе	ссылки

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

Дата добавления: 2014-01-15