ВНУТРЕННЯЯ ОРГАНИЗАЦИЯ РЕЛЯЦИОННЫХ СУБД

СТРУКТУРА ВНЕШНЕЙ ПАМЯТИ МЕТОДЫ ОРГАНИЗАЦИИ ИНДЕКСОВ

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

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

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

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

Соответственно возникают следующие разновидности объектов во внешней памяти БД:

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

Физическое хранение отношений

Существует два принципиальных подхода к физическому хранению отношений.

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

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

Индексы

Как бы ни были организованы индексы в конкретной СУБД, их основное назначение состоит в обеспечении эффективного прямого доступа к кортежу отношения по ключу. Обычно индекс определяется для одного отношения, и ключом является значение атрибута (возможно, составного). Если таковым является возможный ключ отношения, то индекс должен обладать свойством уникальности, т. е. не содержать дубликатов ключа. На практике ситуация выглядит обычно противоположно: при объявлении первичного ключа отношения автоматически заводится уникальный индекс, а единственным способом объявления возможного ключа, отличного от первичного, является явное создание уникального индекса. Это связано с тем, что для проверки сохранения свойства уникальности возможного ключа так или иначе требуется индексная поддержка.

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

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

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

Методы организации индексов

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

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

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

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

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

Журнальная информация

Структура журнала обычно является сугубо частным делом конкретной реализации. Мы отметим только общие свойства.

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

Служебная информация

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

— внутренние каталоги, описывающие физические свойства объектов БД, например, число атрибутов отношения, их размер и, возможно, типы данных; описание индексов, определенных для данного отношения и т. д.;
— описатели свободной и занятой памяти в страницах отношения. Такая информация требуется для нахождения свободного места при занесении кортежа. Отдельно приходится решать задачу поиска свободного места в случаях некластери- зованных и кластеризованных отношений (в последнем случае приходится дополнительно использовать кластеризованный индекс). Как мы уже отмечали, непростой является проблема освобождения страницы в условиях мультидоступа;
— связывание страниц одного отношения. Если в одном файле внешней памяти могут располагаться страницы нескольких отношений (обычно к этому стремятся), то нужно каким-то образом связать страницы одного отношения. Простой способ использования прямых ссылок между страницами часто приводит к затруднениям при синхронизации транзакций (например, особенно трудно освобождать и заводить новые страницы отношения). Поэтому стараются использовать косвенное связывание страниц с использованием служебных индексов. В частности, известен общий механизм для описания свободной памяти и связывания страниц на основе В-деревьев.
Ш вопросы для САМОКОНТРОЛЯ
1. Назовите особенности реляционной СУБД, которые влияют на организацию внешней памяти.
2. Назовите объекты, относящиеся к внешней памяти БД.
3. Назовите способы хранения отношений во внешней памяти. Укажите их достоинства и недостатки.
4. Для чего предназначены индексы в СУБД?
5. Опишите способы организации индексов в СУБД.
6. Для чего используется журнальная информация?
7. Что относится к служебной информации?