9. Индексные файлы. Индексно-прямые файлы. Индексно-последовательные файлы.

Индекс – это структура данных кот помогает СУБД обнаружить отдельные записи => ускоряет время выполнения запроса.

Индексные файлы состоят из 2-х частей, эти части не обязательно совмещены физически. 1) Индексная; 2) Содержит записи файла.

Индекс исключает последовательное сканирование файлов. В зависимости от организации индексной и основной части различают 2 типа файлов:

1)С плотным индексом (индексно-прямые);

2)С не плотным разделенным индексом (индексно-последовательные).

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

1) Файлы ОС должны быть отделены от файлов БД.

2) Основные файлы БД должны быть отделены от индексных файлов.

Значение в индексных файлах упорядочены по полю индексирования, кот обычно строится на базе одного атрибута. Если файл данных имеет последовательное упорядочивание, а поле индексирования является ключевым, то индекс назыв первичным индексом.

Если файл являясь упорядоченным, а поле индексирования не является ключевым, то индекс является вторичным или индексом кластеризации.

В индексном файле может быть один первичный и несколько вторичных индексов.

Индексно-прямые файлы (файлы с плотным индексом)

Состоят из записей одинаковой длины расположенных в произвольном порядке. Структура индексной части имеет вид: значение ключа, потом №записи. При последовательном просмотре БД 12500 обращений к диску. При индексно прямом – 12 обращений к диску. Операции добавления и удаления новых записей. Для добавления новых записей необходимо определить положение новой записи и найти место для всиавки. В индексной области необходимо занести информ в контекстное меню. Индексная обл разбивается на блоки и в каждом блоке оставляется свободная обл (% расширения). При вставке нужный блок модифицируется в памяти и в измененном виде записывается обратно на диск. Когда % расширения исчерпан возникает переполнение индексной обл. В этом случае поступают 2-мя способами: 1) Выполняется модификация всей индексной обл, выделяются заново блока, и заново выделяется % расширения («-» большой расход машинного времени). 2) Организовать обл переполнения для индексной обл («-» увеличивается время доступа к произвольной записи).

Обл переполнения – временный не отсортированный файл называемый файлом переполнения или файлом трансакции. При вставке записи, при нулевом % расширения записывается в файл трансакции кот. периодически сливается с основным отсортированным файлом. Таким образом операции вставки выполняются более эффективно, а операции извлечения данных дольше. При удалении записи выполн последовательность действий: 1)Запись основной обл. помечается как удаленная; 2) В индексном файле соответствующий индекс уничтожается физически; 3) Записи в индексном файле перемещаются заполняя пустое место, следовательно переписывается блок.

Индексно-последовательные файлы

Отсортированный файл данных с первичным индексом. Эта структура явл компромиссом м/д файлами с последовательной и произвольной организацией. В этих файлах данные могут обрабатываться как последовательным так и прямым доступом, который выполняется поиском по заданному ключевому значению с использованием индекса.

Индексно-последовательный файл имеет более сложную структуру, которая обычно включает: первичную область хранения, отдельный индекс или последовательность индексов, область переполнения.

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

После нахождения нужного блока, внутри блока выполняется последовательный просмотр записей поэтому и назыв файлы индексно-последовательными.

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

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