Индексные файлы
Несмотря на высокую эффективность хеш-адресации, в файловых структурах не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. Индексные файлы можно представить как файлы, состоящие из двух частей. Это не обязательно совмещение двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл, а основная область образует файл, для которого создается индекс.
Сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой расположены все записи файла.
В зависимости от организации индексной и основной областей различают 2 типа фалов: с плотным и неплотным индексом. Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются индексно-последовательными файлами.
Файлы с плотным индексом
В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи имеет следующий вид:
Здесь значение ключа – это значение первичного ключа, а номер записи – это порядковый номер записи в основной области, которая имеет данное значение первичного ключа.
В индексных файлах с плотным индексом для каждой записи в основной области существует одна запись из индексной области. Все записи в индексной области упорядочены по значению ключа, поэтому можно применить более эффективные способы поиска в упорядоченном массиве. Наиболее эффективным из всех является бинарный поиск. Максимальное число шагов поиска определяется двоичным логарифмом от общего числа элементов (N).
Tn=log2N
Однако в нашем случае существенным является только число обращений к диску при поиске записи по заданному значению первичного ключа, так как обращение к диску является наиболее длительной операцией по сравнению со всеми обработками в ОП. Поиск происходит в индексной области, где применяется двоичный алгоритм поиска индексной записи, а затем путем прямой адресации мы обращаемся к основной области уже по конкретному номеру записи. Для того чтобы оценить максимальное время доступа, нам надо определить количество обращений к диску для поиска произвольной записи. На диске записи хранятся в блоках. Размер блока определяется физическими особенностями дискового контроллера и ОС. В одном блоке могут размещаться несколько записей. Поэтому нам надо определить количество индексных блоков, которое потребуется для размещения всех требуемых индексных записей, а потому максимальное число обращений к диску будет равно двоичному логарифму от этого числа блоков плюс 1 (после поиска номера записи в индексной области надо будет обратиться к основной области файла).
Рассмотрим, как осуществляются операции добавления новых записей. При операции добавления осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченности. Поэтому вся индексная область разделяется на блоки и при первоначальном заполнении в каждом блоке остается свободная область (процент расширения). После определения блока, в который должен быть занесен индекс, этот блок копируется в оперативную память, там он модифицируется путем вставки в нужное место новой записи и, уже измененный, копируется на диск.
Рисунок 12
Рисунок 12
Основ
ная
об
ласть
В процессе добавления новых записей процент расширения постоянно уменьшается. Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны 2 решения: перестроить индексную область или организовать область переполнения для индексной области, в которой будут храниться не поместившиеся в основную индексную область записи. Для того чтобы избежать подобных проблем, важно как можно точнее определить объем хранимой информации, спрогнозировать ее рост и предусмотреть соответствующее расширение области хранения.
При удалении записи возникает следующая последовательность действий: запись в основной области помечается как удаленная (отсутствующая), в индексной области соответствующий индекс уничтожается физически, то есть записи, следующие за удаленной записью, перемещаются на ее место, и блок, в котором хранился данный индекс, заново записывается на диск. При этом количество обращений к диску для этой операции такое же, как и при добавлении новой записи.