Индексированные файлы

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

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

Для ускорения доступа к данным применяют несколько типов индексов:

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

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

· Вторичный индекс, который определен на поле данных, отличном от поля, по которому выполняется упорядочение.

Файл может иметь не больше одного первичного индекса или одного индекса кластеризации, но дополнительно к ним может иметь несколько вторичных индексов.

Индекс может быть:

· Разреженным то есть содержать индексные записи только для некоторых значений ключа поиска.

· Плотным то есть содержать индексные записи для всех значений ключа поиска.

Файлы на основе индексов можно разделить на следующие группы: индексно-последовательные файлы, файлы с использованием вторичного индекса, файлы с использованием многоуровневых индексов и файлы с использованием индекса кластеризации.

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

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

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

Во многих СУБД используется структура данных, называемая деревом. Дерево состоит из иерархии узлов, в котором каждый узел, за исключением корня, имеет родительский узел, а также один, несколько или ни одного дочернего узла. Если узел не имеет дочернего, его называют листом. Глубина дерева – минимальное количество уровней между корнем и листом. Глубина дерева может быть различной для разных путей доступа к листам. Если глубина одинакова для всех листов, то дерево называют сбалансированным или В-деревом. Степенью или порядком дерева называют максимально допустимое количество дочерних узлов для каждого родительского узла. Бинарным деревом называют дерево порядка 2.

Усовершенствованные сбалансированные древовидные индексы (В+-деревом) определяются по следующим правилам:

· если корень не является лист-узлом, то он должен иметь хотя бы два дочерних узла;

· в дереве порядка n каждый узел (за исключением корня и листов) должны иметь от n/2 до n указателей и дочерних узлов. Если число n/2 не является целым, то оно округляется до ближайшего большего целого;

· в дереве порядка n количество значений ключа в листе должно находиться в пределах от (n-1)/2 до (n-1). Если число (n-1)/2 не является целым, то оно округляется до ближайшего большего целого;

· количество значений ключа в нелистовом узле на единицу меньше количества указателей;

· дерево всегда должно быть сбалансированным;

· листы дерева связаны в порядке возрастания значений ключа.

Файлы с использованием индекса кластеризации.

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

Рисунок 21 - Таблицы Сотрудники и Должность, кластеризованные по значению Код должности

Использование кластеров позволяет повысить производительность выборки данных, но степень такого повышения зависит от распределения данных и типовых запросов.

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