Файл: Базы данных - уч. пособие.pdf

Глава 6

ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ БАЗ

ДАННЫХ

6.1 Структуры внешней памяти, методы
организации индексов

6.1.1 Организация внешней памяти

Знание физической структуры данных позволяет обеспечить качественное вы-

полнение физического проектирования БД.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

Реляционные СУБД обладают рядом особенностей, влияющих на организацию

внешней памяти. К наиболее важным особенностям можно отнести следующие [1]:

1) наличие двух уровней системы: уровня непосредственного управления дан-

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

2) поддержание отношений-каталогов. Информация, связанная с именовани-

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

6.1 Структуры внешней памяти, методы организации индексов

117

С точки зрения структур внешней памяти отношение-каталог ничем не от-
личается от обычного отношения базы данных;

3) регулярность структур данных. Поскольку основным объектом реляцион-

ной модели данных является плоская таблица, главный набор объектов
внешней памяти может иметь очень простую регулярную структуру. При
этом необходимо обеспечить возможность эффективного выполнения опе-
раторов языкового уровня как над одним отношением (простые селекция
и проекция), так и над несколькими отношениями (наиболее распростране-
но и трудоемко соединение нескольких отношений). Для этого во внешней
памяти должны поддерживаться дополнительные «управляющие» структу-
ры — индексы;

4) избыточность хранения данных для выполнения требования надежного хра-

нения баз данных, что обычно реализуется в виде журнала изменений базы
данных.

Соответственно возникают следующие разновидности объектов баз данных:

• таблицы — основные объекты базы данных, большей частью непосред-

ственно видимые пользователям;

• последовательности — объекты БД, используемые для формирования уни-

кальных числовых величин;

• индексы — управляющие структуры, создаваемые по инициативе разработ-

чика (администратора) баз данных или верхнего уровня системы в целях
повышения эффективности выполнения запросов и обычно автоматически
поддерживаемые нижним уровнем системы;

• представления (views) — хранимые предложения SQL (запросы на выбор-

ку), которые можно запросить как таблицу;

• триггеры (triggers) — хранимые процедуры, запускаемые при выполнении

определенных действий с таблицей;

• хранимая процедура — выполняемый объект, реализованный с помощью

процедурного расширения SQL, которому можно передать аргументы и по-
лучить от него сформированные результаты;

• хранимая функция отличается от хранимой процедуры тем, что возвра-

щаемым результатом выполнения функции является некоторое единичное
значение;

• хранимые пакеты представляют собой совокупность процедур, перемен-

ных и функций, объединенных для выполнения некоторой задачи;

• журнальная информация, поддерживаемая для удовлетворения потребно-

сти в надежном хранении данных;

• служебная информация, поддерживаемая для удовлетворения внутренних

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

Любая СУБД основывается на конкретном комплексном решении задач, свя-

занных с организацией хранения и управления данными. Рассмотрим лишь неко-
торые варианты таких решений.

118

Глава 6. Физическая организация баз данных

6.1.2 Хранение таблиц в базе данных

Существуют разные способы физического хранения отношений, и от того, как

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

При организации хранения отношения по столбцам единицей хранения явля-

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

В настоящее время в каждой конкретной СУБД существует свой формат хране-

ния таблиц и других объектов баз данных. Наиболее открытым с точки зрения ви-
зуального представления является формат DBF, используемый в СУБД семейства
dBase (dBase III, IV, V, FoxPro 2.x), в котором применяется обычное покортежное
хранение отношений. Dbf-файл организован таким образом, что в одном файле
хранится одна таблица базы данных (отметим, что dbf-файл носит при этом назва-
ние «база данных»). Структура dbf-файла представлена следующим образом [18]:

• файл базы данных состоит из записи заголовка и записей с данными;

• в записи заголовка определяется структура базы данных и содержится дру-

гая информация, относящаяся к базе данных;

• непосредственно записи с данными следуют за заголовком (байты распо-

лагаются последовательно) и включают в себя фактическое содержимое
полей;

• длина записи (в байтах) определяется суммированием указанных длин всех

полей;

• запись — это строка символов, состоящая из частей (полей) строго опреде-

ленного размера. Эти размеры указаны в структуре описания.

В таблице 6.1 представлена структура dbf-файла.

Таблица 6.1 – Структура dbf-файла

Количество байт

Наименование

32

Заголовок DBF-файла

32

Описание первого поля

32

Описание второго поля

. . .

. . .

32

Описание n-го поля

1

Завершающий символ 0x0D (13)

RecordSize

Первая запись из n-полей

продолжение на следующей странице

6.1 Структуры внешней памяти, методы организации индексов

119

Таблица 6.1 — Продолжение

Количество байт

Наименование

RecordSize

Вторая запись из n-полей

. . .

. . .

RecordSize

m-я запись из n-полей, где m=RecordsCount

1

Завершающий символ 0x1A (26)

RecordSize (размер записи в байтах) и RecordsCount (количество записей), зна-

чения которых берутся из заголовка DBF-файла.

В зависимости от СУБД физически все таблицы могут храниться в одном фай-

ле (MS Access, Mysql и др.) или для каждой таблицы может быть выделен отдель-
ный файл (dBase). Кроме этого, также могут быть выделены файлы отдельных
форматов для хранения других объектов БД.

6.1.3 Организация индексов, методы хранения и доступа
к данным

Во всех существующих на рынке СУБД имеется в наличии средство, оптими-

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

Понятие «указатель» означает, что индекс представляется как совокупность

значений одного или нескольких полей таблицы БД и адресов страниц данных,
где физически располагаются эти значения. То есть индекс состоит из пар значе-
ний «значение поля» — «физическое расположение этого поля». При этом индекс
не является частью таблицы — это отдельный, взаимосвязанный с таблицей (или
таблицами) объект БД. В целом индекс можно описать как специальную структуру
данных, создаваемую автоматически или по запросу пользователя.

. . . . . . . . . . . . . . . . . . . . . .

Пример 6.1

. . . . . . . . . . . . . . . . . . . . .

Индексы принято сравнивать с библиотечным каталогом, в котором информа-

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

120

Глава 6. Физическая организация баз данных

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

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

Фактически, индекс описывает отношения упорядочивания и однозначности

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

Общей идеей любой организации индекса, поддерживающего прямой доступ

по ключу и последовательный просмотр в порядке возрастания или убывания зна-
чений ключа, является хранение упорядоченного списка значений ключа с при-
вязкой к каждому значению ключа списка идентификаторов кортежей. Один вид
организации индекса отличается от другого главным образом по способу поиска
ключа с заданным значением [1].

Различают следующие методы хранения и доступа к данным: физический по-

следовательный, индексно-последовательный, индексно-произвольный, инвертиро-
ванный, метод хеширования и др. Рассмотрим некоторые из них, основываясь,
в том числе, на сведениях из [9].

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

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

Инвертированные индексы, также называемые словарными файлами, представ-

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

Инвертированные списки формируются системой для поисковых атрибутов,

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

Записи с одним и тем же значением поля группируются, а общее для всей

группы значение используется в качестве указателя этой группы. Тогда при поиске
записей по значениям поисковых атрибутов системе достаточно отыскать списки,
соответствующие требуемым значениям, и выбрать номер записи согласно задан-
ной «схеме» пересечения или объединения условий на значениях поисковых ат-
рибутов, а также отрицания некоторого условия. На рисунке 6.1 приведен пример
поиска записей инвертированным методом доступа.