8.2 Индексированные файлы
Индекс в базе данных аналогичен предметному указателю в книге. Индекс – это вспомогательная структура, связанная с файлом и предназначенная для поиска информации по тому же принципу, что и в книге предметным указателем. Индекс позволяет избежать проведения последовательного или пошагового просмотра файла в поисках необходимых данных.
Индекс – структура данных, которая помогает СУБД быстрее обнаружить отдельные записи в файле и сократить время выполнения запросов пользователей. Структура индекса связана с определенным ключом поиска и содержит записи, состоящие из ключевого значения и адреса логической записи в файле, содержащей это ключевое значение. Файл, содержащий логические записи, называется файлом данных, а файл, содержащий индексные записи, - индексным файлом. Значения в индексном файле упорядочены по полю индексирования, которое обычно строится на базе одного атрибута.
Для ускорения доступа к данным применяют несколько типов индексов:
Первичный индекс. Файл данных последовательно упорядочивается по полю ключа упорядочения, а на основе ключа упорядочения создается поле индексации, которое гарантированно имеет уникальное значение в каждой записи.
Индекс кластеризации. Файл данных последовательно упорядочивается по неключевому полю, а на основе этого неключевого поля формируется поле индексации, поэтому в файле может быть несколько записей, соответствующих значению этого поля индексации. Неключевое поле называется атрибутом кластеризации.
Вторичный индекс, который определен на поле данных, отличном от поля, по которому выполняется упорядочение.
Файл может иметь не больше одного первичного индекса или одного индекса кластеризации, но дополнительно к ним может иметь несколько вторичных индексов.
Индекс может быть:
Разреженным то есть содержать индексные записи только для некоторых значений ключа поиска.
Плотным то есть содержать индексные записи для всех значений ключа поиска.
Файлы на основе индексов можно разделить на следующие группы: индексно-последовательные файлы, файлы с использованием вторичного индекса, файлы с использованием многоуровневых индексов и файлы с использованием индекса кластеризации.
Индексно-последовательные файлы – отсортированные файлы с первичным индексом. В таком файле записи могут обрабатываться как последовательно, так и выборочно с произвольным доступом, осуществляемым на основе поиска по заданному значению ключа с использованием индекса.
Файлы с использованием вторичного индекса являются упорядоченными файлами. Файл данных, связанный с вторичным индексом, не всегда отсортирован по ключу индексации. Ключ вторичного индекса может содержать повторяющиеся значения. При запросах, в которых для поиска используются атрибуты, отличные от атрибутов первичного ключа, вторичные индексы повышают производительность обработки запросов.
Файлы с использованием многоуровневых индексов. Поиск в такого рода файлах начинается с поиска индекса самого низкого уровня, при нахождении нужной страницы (с атрибутом, равным условию или большим) идет ссылка на следующий уровень индекса с более подробной индексацией записей и т.д.
Во многих СУБД используется структура данных, называемая деревом. Дерево состоит из иерархии узлов, в котором каждый узел, за исключением корня, имеет родительский узел, а также один, несколько или ни одного дочернего узла. Если узел не имеет дочернего, его называют листом. Глубина дерева – минимальное количество уровней между корнем и листом. Глубина дерева может быть различной для разных путей доступа к листам. Если глубина одинакова для всех листов, то дерево называют сбалансированным или В-деревом. Степенью или порядком дерева называют максимально допустимое количество дочерних узлов для каждого родительского узла. Бинарным деревом называют дерево порядка 2.
Усовершенствованные сбалансированные древовидные индексы (В+-деревом) определяются по следующим правилам:
если корень не является лист-узлом, то он должен иметь хотя бы два дочерних узла;
в дереве порядка n каждый узел (за исключением корня и листов) должны иметь от n/2 до n указателей и дочерних узлов. Если число n/2 не является целым, то оно округляется до ближайшего большего целого;
в дереве порядка n количество значений ключа в листе должно находиться в пределах от (n-1)/2 до (n-1). Если число (n-1)/2 не является целым, то оно округляется до ближайшего большего целого;
количество значений ключа в нелистовом узле на единицу меньше количества указателей;
дерево всегда должно быть сбалансированным;
листы дерева связаны в порядке возрастания значений ключа.
Файлы с использованием индекса кластеризации.
Кластерами называют группы из одной или нескольких таблиц, которые физически хранятся вместе, поскольку в них совместно используются общие столбцы и доступ к ним часто осуществляется одновременно. Пример кластеризованного хранения данных приведен на рисунке 21.
Рисунок 21 - Таблицы Сотрудники и Должность, кластеризованные по значению Код должности
Использование кластеров позволяет повысить производительность выборки данных, но степень такого повышения зависит от распределения данных и типовых запросов.
В кластеризованных таблицах используют индексированные и хешированные кластеры. В индексированном кластере хранятся вместе записи, имеющие одинаковый ключ кластера. В хешированный кластер запись вносится с учетом применения хеш-функции к значению ключа кластера этой записи.