Часть 2. Индексирование

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

Для реализации этих функций в СУБД применяют индексирование.

Термин «индекс» тесно связан с понятием «ключ», хотя между ними есть и некоторое отличие.

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

Таблицу, для которой используется индекс, называют индексированной.

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

В некоторых системах, например, Paradox, индексы хранятся в индексных файлах, хранимых отдельно от таб­личных файлов.

Варианты решения проблемы организации физического доступа к инфор­мации зависят в основном от следующих факторов:

• вида содержимого в поле ключа записей индексного файла;

• типа используемых ссылок (указателей) на запись основной таблицы;

• метода поиска нужных записей.

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

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

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

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

На практике чаще всего используются два метода поиска: последователь­ный и бинарный (основан на делении интервала поиска пополам).

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

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

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

В каждом блоке записи располагаются в порядке возрастания значения ключа или свертки. Старшим ключом каждого блока является ключ его последней записи.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Часть 3. Связывание таблиц

При проектировании реальных БД информацию обычно размещают в не­скольких таблицах. Таблицы при этом связаны семантикой информации. В реляционных СУБД для указания связей таблиц производят операцию их связывания.

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

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

Основные виды связей между таблицами

Между таблицами могут устанавливаться бинарные (между двумя табли­цами), тернарные (между тремя таблицами) и, в общем случае, n-арные свя­зи. Рассмотрим наиболее часто встречающиеся бинарные связи.

При связывании двух таблиц выделяют основную и дополнительную (под­чиненную) таблицы. Логическое связывание таблиц производится с помо­щью ключа связи.

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

Суть связывания состоит в установлении соответствия полей связи основ­ной и дополнительной таблиц. Поля связи основной таблицы могут быть обычными и ключевыми. В качестве полей связи подчиненной таблицы чаще всего используют ключевые поля.

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

1. один - один (1:1);

2. один - много (1:М);

3. много - один (М:1);

4. много - много (М:М или M:N).

­Характеристика видов связей таблиц приведена в табл. 2.

Таблица 2.

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

Связь вида 1:1

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

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

Связь вида 1:М

Связь 1:М имеет место в случае, когда одной записи основной таблицы соответствует несколько записей вспомогательной таблицы.

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

Связь вида М:1

Связь М:1 имеет место в случае, когда одной или нескольким записям основ­ной таблицы ставится в соответствие одна запись дополнительной таблицы.

Пример. Рассмотрим связь таблиц А и B.

В основной таблице А содержит­ся информация о названиях деталей (Название), видах материалов, из ко­торого детали можно изготовить (Материал), и марках материала (Марка).

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

Таблица А

+

Название	Материал	Марка
деталь 1	чугун	марка1
деталь 1	чугун	марка2
деталь2	сталь	марка1
деталь2	сталь	марка2
деталь2	сталь	маркаЗ
детальЗ	алюминий	-
деталь4	чугун	марка2

Таблица B

* +

Название	Срок_изготовления	Стоимость_заказа
деталь 1	4.03.98
деталь2	3.01.98
детальЗ	17.02.98
деталь4	6.05.98

В таком случае, поменяв таблицы местами, можно получить связь вида 1:М.

Отсюда сле­дует, что вид связи (1: М или М: 1) зависит от того, какая таблица является глав­ной, а какая дополнительной.

Связь вида М:М

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

Дата добавления: 2014-11-29