17. Физическая организация данных в субд:

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

Индексирование

Основное назначение индексов состоит в обеспечении эффективного прямого доступа к записям таблицы по ключу.

Различают индексированный файл и индексный.

Индексированный – основной файл содержащий данные отношения для которого создан индексный файл.

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

Данные представляют поле, по которому производится индексирование.

Указатель – осуществляет связывание соответствующим кортежем индексированные файлы

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

Такой индекс обладает свойством уникальности, т.е. не содержит дубликатов ключей.

Преимущество: ускорение процессов выборки данных.

Недостаток: замедление процесса обновления данных.

Индексно-прямой файл

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

Индексная запись содержит значения первичного ключа и порядкового номера записи в основной области, которая имеет значение первичного ключа.

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

Наиболее эффективный алгоритм поиска на упорядоченном массиве является бинарный поиск.

Операция добавления новой записи осуществляет запись в конец основной области.

В индексной области производится занесение информации так, чтобы не нарушить упорядоченность, поэтому вся индексная область файла разбивается на блоки, и при начальном заполнении в каждом блоке остаётся свободная область (процент расширения).

Алгоритм удаление записи:

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

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

Если файл поддерживается в отсортированном состоянии с момента их создания, то для работы с ними используется другой подход. Принципы внутреннего упорядочения и блочности построения таких файлов позволяет уменьшить количество хранимых индексов за счёт того, что в индексном файле не содержатся указатели на все записи индексированного файла. Таким образом, индекс получается неплотным или разреженным.

Индексная запись для таких файлов должна содержать:

1. значение ключа первой записи блока

2. номер блока с этой записью.

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

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

При внесении новой записи индексная область не корректируется.

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

Замечание: с помощью одного индекса неплотного нельзя выполнить проверку наличия некоторого значения.

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