Файлы с неплотным индексом
Неплотный индекс строится для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов имеет следующий вид:
Значение ключа первой записи блока |
Номер блока с этой записью |
В индексной области мы теперь ищем нужный блок по заданному значению первичного ключа. Так как все записи упорядочены, то значение первой записи блока позволяет быстро определить, в каком блоке находится искомая запись. Все остальные действия происходят в основной области.
Пример заполнения основной и индексной областей, если первичным ключом являются целые числа.
Рисунок 13
Время сортировки больших файлов весьма значительно, но поскольку файлы поддерживаются сортированными с момента их создания, накладные расходы в процессе добавления новой информации будут гораздо меньше. Время доступа при использовании неплотного индекса уменьшается примерно в полтора раза. Рассмотрим процедуры добавления и удаления новой записи при неплотном индексе.
При включении новая запись должна заноситься сразу в требуемый блок на требуемое место. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить требуемую запись, а потом этот блок считывается в ОП, затем в ОП корректируется содержимое блока и он снова записывается на диск на старое место. Здесь, также как и в первом случае должен быть задан процент первоначального заполнения блоков, но только применительно к основной области. В MS SQL-Server этот процент называется Full-factor и используется при формировании кластеризованных индексов. Кластеризованными называют те индексы, в которых исходные записи физически упорядочены по значениям первичного ключа. При внесении новой записи индексная область не корректируется. Количество обращений к диску при добавлении новой записи равно количеству обращений, необходимых для поиска соответствующего блока плюс одно обращение, которое требуется для занесения измененного блока на старое место.
Tдобавления=log2N+1+1
Уничтожение записи происходит путем ее физического удаления на основной области, при этом индексная область обычно не корректируется, даже если удаляется первая запись блока. Поэтому количество обращений к диску такое же, как и при добавлении новой записи.
На практике для создания индекса для некоторой таблицы БД пользователь указывает поле таблицы, которое требует индексации. Ключевые поля таблицы во многих СУБД, как правило, индексируются автоматически. Индексные файлы, создаваемые по ключевым полям таблицы, часто называют файлами первичных индексов. Индексы, создаваемых для не ключевых полей, называют вторичными индексами. Введение таких индексов не изменяет физического расположения записей таблицы, но влияет на последовательность просмотра записей. В некоторых СУБД, например, Access деление на первичные и вторичные индексы не производится. В этом случае используются автоматически создаваемые индексы и индексы, определяемые пользователем.
Главная причина повышения скорости выполнения различных операций состоит в том, что основная часть работы производится с небольшими индексными файлами, а не с самими таблицами. Наибольший эффект повышения производительности работы с индексированными таблицами достигается для больших по объему таблиц. Индексирование требует незначительного дополнительного места на диске и незначительных затрат процессора для изменения индексов в процессе работы. Индексы в общем случае могут изменяться перед выполнением запросов к БД, после выполнения запросов к БД, по специальным командам пользователя или программным вызовам приложений. Варианты решения проблемы организации физического доступа к информации зависят в основном от следующих факторов:
вида содержимого в поле ключа записей индексного файла;
типа используемых ссылок (указателей) на запись основной таблицы;
метода поиска нужных записей.