Механизмы среды хранения БД служат для управления двумя группами ресурсов - ресурсами хранимых данных и ресурсами пространства памяти. В задачу этого механизма входит отображение структуры хранимых данных в пространство памяти, позволяющее эффективно использовать память и определить место размещения данных при запоминании и при поиске данных.
В большинстве случаев в качестве единицы хранения принимается хранимая запись.
Механизмы среды хранения выполняют следующие операции:
1. При запоминании нового объекта:
определение места размещения нового объекта "физической" БД в пространстве памяти;
выделение необходимого ресурса памяти;
запоминание этого объекта;
формирование связей с другими объектами.
2. При поиске объекта:
поиск места размещения объекта в пространстве памяти по заданным атрибутам или "адресу";
выборка объектов для обработки.
3. При удалении объекта:
удаление объекта с освобождением памяти (физическое удаление) или без освобождения (логическое удаление);
разрушение связей с другими объектами.
Примечание: в реляционных СУБД формирование связей осуществляется на логическом уровне (т.е. по значениям атрибутов), а в иерархических и сетевых СУБД - на физическом уровне (по адресам записей).
Все операции выполняются по запросам механизмов концептуального уровня СУБД. На этом уровне никаких операций непосредственного обновления пользовательских данных или преобразований представления хранимых данных не происходит, это задача более высоких архитектурных уровней. Управление памятью выполняется операционной системой по запросам СУБД или непосредственно самой СУБД.
Несмотря на декларируемую независимость архитектурных уровней, для достижения более высокой производительности на уровне организации среды хранения часто приходится учитывать специфику концептуальной модели. Аналогично, организация файловой системы не может не оказывать влияния на среду хранения.
2. Пространство памяти и размещение хранимых данных
Ресурсам пространства памяти соответствуют объекты внешней памяти ЭВМ, управляемые средствами операционной системы или СУБД.
Для обеспечения естественной структуризации хранимых данных, более эффективного управления ресурсами и/или для технологического удобства всё пространство памяти БД обычно разделяется на части (области, разделы и др.). (Во многих системах область соответствует файлу.) Области памяти используются для размещения хранимых записей одного или нескольких типов и разбиваются на пронумерованные страницы фиксированного размера. В большинстве систем обработку данных на уровне страниц ведёт операционная система (ОС), а обработку записей внутри страницы обеспечивает только СУБД.
Страницы представляются в среде ОС блоками внешней памяти, кластерами или секторами, доступ к которым осуществляется за одно обращение. В системах, которые позволяют управлять размером страницы, приходится искать компромисс между производительностью системы и требуемым объёмом оперативной памяти.
Страница имеет заголовок, содержащий служебную информацию, вслед за которым располагаются собственно данные. На странице размещается, как правило, несколько записей, и есть свободный участок для размещения новых записей. Если запись не помещается на одной странице, она разбивается на фрагменты, которые хранятся на разных страницах и имеют ссылки друг на друга.
Существуют различные механизмы, позволяющие решать проблемы, которые возникают при модификации данных в БД. Рассмотрим их.
Удаление записей может быть логическим или физическим. В первом случае запись помечается как удаленная, но фактически она остаётся на прежнем месте. Фактическое удаление этой записи будет произведено либо при реорганизации БД, либо специальной сервисной программой, инициируемой администратором БД.
При физическом удалении ранее занятый участок освобождается и становится доступным для повторного использования. Система автоматически управляет свободным пространством памяти на страницах. Как правило, это обеспечивается либо ведением списков свободных участков, либо динамической реорганизацией страниц.
При динамической реорганизации страниц записи БД плотно размещаются вслед за заголовком страницы, а после них расположен свободный участок (рис. 5.1,а). Смещение начала свободного участка хранится в заголовке страницы. При удалении записи оставшиеся записи переписываются подряд в начало страницы и изменяется смещение начала свободного участка.
Рис. 5.1. Управление свободным простанством памяти на страницах
Если система ведёт список свободных участков, то возможны разные варианты. Ссылка на первый свободный участок на странице может храниться в заголовке страницы, и каждый свободный участок хранит ссылку на следующий (или признак конца списка) (рис. 5.1,б). Каждый освобождаемый участок включается в список свободных участков на странице.
Другой способ заключается в поддержке списков участков в виде отдельных структур (рис. 5.1,в). Список ведется как стек, очередь или упорядочённый список. В последнем случае упорядочение осуществляется по размеру свободного участка, что позволяет при размещении новой записи выбирать для неё наиболее подходящий по размеру участок.
Для учёта свободных участков в СУБД могут поддерживаться инвентарные страницы. Они создаются для области (или группы страниц) и содержат информацию о свободных участках в этой области. Это существенно ускоряет поиск свободного пространства для размещения новых записей.
При запоминании новой записи система через инвентарные страницы ищет свободный участок, достаточный для размещения этой записи. (Обычно выбирается первый подходящий, размер которого не меньше требуемого.) Если выбранный участок больше, чем запись, то остаток оформляется в виде свободного участка. (При динамической реорганизации страниц запись просто записывается вслед за последней на данной странице.) После этого система корректирует содержимое инвентарных страниц (если они есть).
При изменении записи, имеющей фиксированный формат, она просто перезаписывается на прежнее место. Если же запись имеет плавающий формат, возможны ситуации, когда запись не помещается на прежнее место. Тогда процедуры корректировки приводят либо к реорганизации страницы, либо к перемещению записи на другой участок памяти, что, в свою очередь, приведёт к обновлению нескольких страниц.
Использование списков свободных участков ведёт к фрагментации пространства памяти. Для того чтобы уменьшить фрагментацию, в подобных системах предусмотрены процедуры, которые периодически проводят слияние смежных свободных участков в один.
Структура и представление хранимых данных, их размещение в пространстве памяти и используемые методы доступа определяются схемой хранения. Схема хранения оперирует в терминах типов объектов.
3. Структура хранимых данных
Единицей хранения данных в БД является хранимая запись. Она может представлять как полную запись концептуального уровня, так и некоторую её часть. Если запись разбивается на части, то её фрагменты представляются экземплярами хранимых записей каких-либо типов. Все части записи связываются указателями (ссылками) или размещаются по специальному закону так, чтобы механизмы междууровневого отображения могли опознать все компоненты и осуществить сборку полной записи концептуальной БД по запросу механизмов концептуального уровня.
Хранимые записи одного типа состоят из фиксированной совокупности полей и могут иметь формат фиксированной или переменной длины.
Записи переменной длины возникают, если допускается использование повторяющихся групп полей (агрегатов) с переменным числом повторов или полей переменной длины. Работа с хранимыми записями переменной длины существенно усложняет управление пространством памяти, но может быть продиктована желанием уменьшить объём требуемой памяти или характером модели данных концептуального уровня. В последнем случае для повышения производительности системы записи могут разбиваться на фрагменты фиксированной длины, возможно, различных типов.
Хранимая запись состоит из двух частей:
1. Служебная часть. Используется для идентификации записи, задания её типа, хранения признака логического удаления, для кодирования значений элементов записи, для установления структурных ассоциаций между записями. Никакие пользовательские программы не имеют доступа к служебной части хранимой записи.
2. Информационная часть. Содержит значения элементов данных.
Элементы хранимой записи могут иметь фиксированную или переменную длину. При этом обычно элементы фиксированной длины хранятся в начале записи и размещаются в памяти с заранее определённых позиций, а за ними размещаются элементы переменной длины. Хранение элементов переменной длины осуществляется одним из двух способов: размещение через разделитель или хранение размера элемента данных. Наличие полей переменной длины позволяет не хранить незначащие символы и тем существенно снижает затраты памяти на хранение данных; но при этом увеличивается время на извлечение элементов записи.
Каждой записи БД система присваивает внутренний идентификатор, называемый (по стандарту CODASYL) ключом базы данных (КБД). Значение КБД формируется системой при размещении записи и содержит информацию, позволяющую однозначно определить место размещения записи (её адрес). В качестве КБД может выступать, например, последовательный номер записи в файле или совокупность адреса страницы и смещения от начала страницы.
Конкретные составляющие КБД зависят от операционной системы и от СУБД, точнее, от вида используемой адресации и от структуризации памяти, принятой в данной СУБД.
4. Виды адресации хранимых записей
Рассмотрим два вида адресации: прямую и косвенную.
Прямая адресация предусматривает указание непосредственного местоположения записи в пространстве памяти. Простейший вариант адресации используется в том случае, если в памяти хранится один вид записи фиксированной длины. Тогда в качестве адреса записи может использоваться её порядковый номер. (Прямая адресация используется, например, в системах ADABAS и dBaseIII PLUS).
Прямая адресация не позволяет перемещать записи в памяти без изменения ключа базы данных. Такие изменения привели бы к необходимости коррекции различных указателей на записи в среде хранения, что было бы чрезвычайно трудоемкой процедурой. В связи с отсутствием возможности перемещения при этом возникает явление фрагментации, т.е. появление разрозненных незаполненных участков памяти.
Указанные недостатки можно преодолеть, используя косвенную адресацию. Существует множество способов косвенной адресации. Один из них состоит в том, что часть адресного пространства страницы выделяется под индекс страницы (рис. 5.2). Число статей (слотов) в нем одинаково для всех страниц. Ключом БД по-прежнему служит номер этой записи в области. С помощью простых арифметических действий можно получить по номеру записи номер нужной страницы и номер требуемого слота в индексе этой страницы. Найденный слот укажет местоположение записи на этой странице, где N, n - это соответственно номер страницы памяти и номер слота на этой странице, в котором хранится адрес записи (смещение от начала страницы).
Рис.5.2. Косвенная адресация с использованием индексов
При перемещении записи она остаётся на той же странице, и слот по-прежнему указывает на неё (меняется его содержимое, но не сам слот). Если запись не вмещается на страницу, она помещается на специально отведённые в данной области страницы переполнения, и соответствующий слот продолжает указывать место её размещения.
Этот подход позволяет перемещать записи на странице, исключать фрагментацию, возвращать освободившееся пространство для повторного использования. При этом приложения БД остаются нечувствительными к таким операциям. Таким образом, косвенная адресация входит в группу методов, обеспечивающих физическую независимость данных.
Также с адресацией связана другая функция среды хранения - поддержка связей между хранимыми записями.
5. Организация связей между хранимыми записями
Для сетевой и иерархической моделей данных эти связи поддерживаются на физическом уровне. Способы представления связей определяются схемой хранения и чаще всего основаны на использовании указателей или на размещении данных в смежных областях памяти.
В сетевых и иерархических БД ассоциации между данными поддерживаются групповыми отношениями. Наиболее распространённый способ поддержания групповых отношений - создание цепного списка. Для этого запись-владелец в служебной части содержит адресную ссылку (ключ базы данных) на первую подчиненную запись, а каждая подчиненная запись содержит ссылку на следующую (рис. 5.3,б). Последняя подчиненная запись содержит либо признак конца списка (разомкнутый список), либо ссылку на владельца (замкнутый список).
Ссылки могут быть однонаправленными (только на следующую запись) или двунаправленными (на следующую и на предыдущую записи). В последнем случае запись владелец кроме ссылки на начало списка подчинённых записей также содержит ссылку на последнюю подчиненную запись (рис. 5.3,в).
Двунаправленный список удобен при удалении записи. Для корректности удаления подчиненной записи нужно, чтобы предыдущая запись содержала ссылку на последующую запись (по отношению к удаленной). Например, при удалении записи В2 (рис. 5.3,в) запись В1 должна ссылаться на запись В3. Имея ссылку на предыдущую запись, можно сразу выполнить шаг назад и изменить значение ссылки у записи В1, не проходя заново по всему списку.
Рис. 5.3. Реализация групповых отношений (а):
б) замкнутый цепной список; в) двунаправленный цепной список
Кроме ссылок внутри списка подчинённые записи могут содержать ссылку на запись-владельца. В сетевой модели данных обработку можно начать с любой записи, и наличие ссылки на владельца обеспечивает быстрое передвижение вверх по групповым отношениям.
Дополнительные ссылки увеличивают эффективность выполнения отдельных операций, но требуют соответствующих затрат внешней памяти и время на установление и разрыв связей.