Достоинства и недостатки основных методов доступа

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

Такой индекс имеет один существенный недостаток — он может быть использован только в запросах по ведущим столбцам. Это означает, что если используется составной индекс, то поиск по всем атрибутам, входящим в индекс, начиная со второго, будет медленным. Допустим, определен индекс index1(id1, id2); в этом случае поиск значений, удовлетворяющих условию id2=1, будет медленным (не исключено, что оптимизатор вообще не будет использовать этот индекс для обработки данного условия и будет принято решение о полном сканировании данных), а поиск значений, удовлетворяющих условию id1=1 and id2=1, будет быстрым. Несмотря на этот недостаток, индексы B-деревьев наиболее распространены.

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

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

Битовые индексы обладают очень важным свойством: если производится запрос, включающий сложное условие выборки, которое составлено из предикатов OR, AND, NOT и «=», то оптимизатор может использовать имеющиеся по конкретным столбцам битовые индексы, объединяя их. B-деревья этого делать не позволяют (для этого потребовалось бы построить составной индекс по этим столбцам, специально для ускорения данного запроса).

Битовые карты полезны в хранилищах, где преобладают длинные транзакции и данные читаются чаще чем записываются, однако они неэффективны в приложениях с короткими транзакциями,

Данные особенности следует учитывать при определении индексов в схеме базы данных, а именно:

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

· наличие индекса обязательно, если для атрибута или набора атрибутов указано ограничение unique. Такие индексы СУБД создает автоматически, если в описании таблицы указаны ограничения unique;

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

· атрибуты, входящие во внешний ключ, также следует индексировать, если СУБД не делает эту операцию автоматически при декларации внешнего ключа;

· в некоторых СУБД поддерживаются bitmap-индексы, которые очень эффективны при поиске на равенство, но для поиска на этот тип индексов не годится;

· в некоторых СУБД поддерживаются хеш-индексы, например для кластеров. Такие индексы эффективно используются при поиске на равенство.

Для того чтобы выбрать тот или иной тип индекса, требуется внимательно изучить руководство администратора СУБД. Оптимизатор SQL использует различные типы доступа к данным при обработке запросов, и индексирование существенно влияет на выбор оптимизатора.

Бесфайловая организация внешней памяти

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

Причины передачи управления пространством внешней памяти от ОС к СУБД были названы в начале главы; еще раз отметим, что при бесфайловой организации внешней памяти операционная среда не получает непосредственного доступа к этому пространству.

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

Замечание 2. Следует отметить, что некоторые механизмы, описываемые ниже, используются и при файловом управлении.

Особенности реляционных СУБД

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

Наличие двух уровней системы:

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

языкового уровня (например уровня, реализующего язык SQL).

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

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

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

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

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

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

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

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

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

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

· описание индексов, определенных для данного отношения;

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

Базовые структуры памяти

Структура и типы страниц

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

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

Выделяют четыре типа страниц:

· страницы данных,

· страницы индексов,

· страницы blob-объектов,

· битовые страницы.

Страница данных. Основная единица осуществления операций обмена. Структура страницы данных представлена на рис. 32.

 

Заголовок страницы

Содержание

Слоты

 

Рис. 32. Структура страницы данных

 

Заголовок страницы включает внутрисистемную информацию, используемую СУБД в механизме управления страницами.

Данные на странице представляются в виде строк. Каждая строка соответствует некоторому кортежу отображаемого отношения.

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

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

Страница blob. Страницы blob (B inary L arge Ob ject) предназначены для хранения слабоструктурированной информации, содержащей тексты большого объема, графическую информацию, двоичные коды. Эти данные рассматриваются как потоки байтов произвольного размера, а в страницах данных формируются ссылки на эти страницы. Данные таких типов в ранних СУБД относились к типу MEMO.

Битовая страница. Битовые страницы содержат описатели других типов страниц. Описатель страницы включает две составляющих – тип страницы и ее состояние (свободна / занята).

Табличные пространства

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

 

Рис.33. Физическое размещение данных по устройствам

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

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

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

Пусть, например, для таблицы Person создаются два раздела part1 и part2, каждый из которых размещен в своем табличном пространстве (tblspace1 и tblspace2). Записи со значением поля Num от 1 до 499 будут располагаться в первом разделе, а записи с номерами от 500 до 1000 — во втором (рис. 34.).

Тогда при запросе:

SELECT FIO FROM person WHERE Num BETWEEN 10 AND 40

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

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

 

Рис. 34. Пример кластеризации записей