Файловые структуры Баз данных

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

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

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

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

Индексы поддерживаются динамически, т.е. после обновления БД – добавлении или удалении записей, а также при модификации полей записи, входящих в ключ, индекс приводится в соответствие с обновленной версией БД. Обновление индекса занимает некоторое время, поэтому существование многих индексов может замедлить работу БД. В реальных СУБД существуют методы оптимизации переиндексации .

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

Обращение к записи через индексы осуществляется в два этапа: сначала в индексной структуре находится требуемое значение атрибута и соответствующий адрес записи, затем по этому адресу происходит обращение к внешнему запоминающему устройству. Индекс загружается в оперативную память целиком (или хранится в ней постоянно во время работы с БД).

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

Различают одиночные индексы и составные.   Составной индекс  включает два или более столбца одной таблицы (Рисунок 1). Последовательность вхождения столбцов в индекс определяется при создании индекса.

Таблица

Рисунок 1 - Пример составного индекса

Способы организации индексов

Существует множество способов организации индексов:

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

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

3. Одноуровневый индекс   представляет собой линейную совокупность значений одного или нескольких полей записи.

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

Дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами дерева являются порядок  n  и количество уровней