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

Ключи отношения.

20 Первичным ключом (ключом отношения, ключевым атрибутом) на­зывается атрибут отношения, однозначно идентифицирующий каждый из его кортежей. Например, в отношении СОТРУДНИК(ФИО, Отдел, Долж­ность, Д_Рождения) ключевым является атрибут "ФИО". Первичный ключ называется простым, когда он состоит из одного атрибута, или составным (сложным), когда он состоит из нескольких атрибутов.

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

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

Ключи обычно используют для достижения следующих целей:1) исключения дублирования значений в ключевых атрибутах (осталь­ные атрибуты в расчет не принимаются);2) упорядочения кортежей. Возможно упорядочение по возрастанию или убыванию значений всех ключевых атрибутов, а также смешанное упо­рядочение (по одним — возрастание, а по другим — убывание);3)ускорения работы с кортежами отношения;4)организации связывания таблиц.

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

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

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

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

Индекс выполняет роль оглавления таблицы, просмотр которого пред­шествует обращению к записям таблицы.

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

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

При одноуровневой схеме в индексном файле хранятся короткие за­писи, имеющие два поля: поле содержимого старшего ключа (хеш-кода ключа) адресуемого блока и поле адреса начала этого блока (рис. 28). В каждом блоке записи располагаются в порядке возрастания значения ключа или свертки. Старшим ключом каждого блока является ключ его последней записи.

Блок – 3

Рис. 28. Одноуровневая схема индексации

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

1. Образование свертки значения ключевого поля искомой записи.

2. Поиск в индексном файле записи о блоке, значение первого поля кото­рого больше полученной свертки (это гарантирует нахождение иско­мой свертки в этом блоке).

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

Основным недостатком одноуровневой схемы является то, что ключи (свертки) записей хранятся вместе с записями. Это приводит к увеличению времени поиска записей из-за большой длины просмотра (значения дан­ных в записях приходится пропускать).

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

Рис. 29. Двухуровневая схема индексации

В этой схеме индекс основной таблицы распределен по совокупности фай­лов: одному файлу главного индекса и множеству файлов с блоками ключей.

На практике для создания индекса для некоторой таблицы БД пользова­тель указывает поле таблицы, которое требует индексации. Ключевые поля таблицы во многих СУБД, как правило, индексируются автоматически. Ин­дексные файлы, создаваемые по ключевым полям таблицы, часто называ­ются файлами первичных индексов.

Индексы, создаваемые пользователем для не ключевых полей, иногда называют вторичными (пользовательскими) индексами. Введение таких индексов не изменяет физического расположения записей таблицы, но вли­яет на последовательность просмотра записей. Индексные файлы, создава­емые для поддержания вторичных индексов таблицы, обычно называются файлами вторичных индексов.

Связь вторичного индекса с элементами данных базы может быть уста­новлена различными способами. Один из них — использование вторич­ного индекса как входа для получения первичного ключа, по которому затем с использованием первичного индекса производится поиск необхо­димых записей (рис. 30).

Рис. 30. Способ использования вторичных индексов

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

Дата добавления: 2015-05-09