Физическая организация данных
 Скачать 487.44 Kb.
|
                   
Механизмы среды хранения БД служат для управления двумя группами ресурсов - ресурсамихранимых данных и ресурсами пространства памяти. В задачу этого механизма входит отображение структуры хранимых данных в пространство памяти, позволяющее эффективно использовать память и определить место размещения данных при запоминании и при поиске данных. С точки зрения пользователя работа с данными происходит на уровне записей концептуального уровня и заключается в добавлении, поиске, изменении и удалении записей. При этом механизмы среды хранения делают следующее:
о определение места размещения новой записи в пространстве памяти; о выделение необходимого ресурса памяти; о запоминание этой записи (сохранение в памяти); о формирование связей с другими записями (конкретный механизм зависит от модели данных). Примечание: в реляционных базах данных формирование связей осуществляется на логиче-ском уровне (т.е. по значениям атрибутов), а в иерархических и сетевых БД - на фи-зическом уровне (по адресам записей).
о поиск места размещения записи в пространстве памяти по заданным значениям атрибутов; о выборка записи для обработки в оперативную память (в буфер данных).
Запись помещается на прежнее место, если она не увеличилась в объёме или на прежнем месте достаточно памяти для неё. Если запись увеличи-лась в объёме и не помещается на прежнем месте, то она либо записывается на новое место, либо разбивается на части, и первая часть хранится на прежнем месте, а продолжение - на новом, на которое указывается ссылка из первой части. При удалении записи:
В случае логического удаления запись помечается как удаленная, но фактически она остаётся на прежнем месте. Фактическое удаление этой записи будет произведено либо при реорганизации БД, либо специальной сервисной программой, которую автоматически запускает СУБД или вручную АБД. При физическом удалении записи ранее занятый участок освобождается и становится доступным для повторного использования. Физическую организацию БД мы будем рассматривать только для РСУБД. Ознакомиться со способами организации СУБД, основанных на других моделях данных, можно в [1]. Все операции на физическом уровне выполняются по запросам механизмов концептуального уровня СУБД. На физическом уровне никаких операций непосредственного обновления пользовательских данных или преобразований представления хранимых данных не происходит, это задача более высоких архитектурных уровней. Управление памятью выполняется операционной системой по запросам СУБД или непосредственно самой СУБД. В трехуровневой модели архитектуры СУБД декларируется независи-мость архитектурных уровней. Но для достижения более высокой производительности на уровне организации среды хранения часто приходится учитывать специфику концептуальной модели. Аналогично организация файловой системы не может не оказывать влияния на среду хранения.
Единицей хранения данных в БД является хранимая запись. Она может представлять собой как полную запись концептуального уровня, так и некоторую её часть. Если запись разбивается на части, то эти части представляются экземплярами хранимых записей каких-либо типов. Все части записи связываются указателями (ссылками) или размещаются по специальному закону так, чтобы механизмы междууровневого отображения могли опознать все компоненты и осуществить сборку полной записи концептуальной БД по запросу механизмов концептуального уровня. Хранимые записи одного типа состоят из фиксированной совокупности полей и могут иметь формат фиксированной или переменной длины. Записи переменной длины возникают, если допускается использование повторяющихся групп полей (агрегатов) с переменным числом повторов или полей переменной длины. Работа с хранимыми записями переменной длины существенно усложняет управление пространством памяти, но может быть продиктована желанием уменьшить объём требуемой памяти или характером модели данных концептуального уровня. Хранимая запись состоит из двух частей:
Поля хранимой записи могут иметь фиксированную или переменную длину. При этом желательно поля фиксированной длины размещать в начале записи, а необязательные поля - в конце. Хранение полей переменной длины осуществляется одним из двух способов: размещение полей через разделитель или хранение размера значения поля. Наличие полей переменной длины позволяет не хранить незначащие символы и снижает затраты памяти на хранение данных; но при этом увеличивается время на из-влечение записи. Каждой хранимой записи БД система присваивает внутренний идентификатор, называемый (по стандарту CODASYL) ключом базы данных (КБД). (Иногда используется терминидентификатор строки, RowID). Значение КБД формируется системой при размещении записи и содержит информацию, позволяющую однозначно определить место размещения записи (преобразовать значение КБД в адрес записи). В качестве КБД может выступать, например, последовательный номер записи в файле или совокупность адреса страницы памяти и смещения от начала страницы. Конкретные составляющие КБД зависят от операционной системы и от СУБД, точнее, от вида используемой адресации и от структуризации памяти, принятой в данной СУБД.
Ресурсам пространства памяти соответствуют объекты внешней памяти ЭВМ, управляемые средствами операционной системы или СУБД. Для обеспечения естественной структуризации хранимых данных, более эффективного управления ресурсами и/или для технологического удобства всё пространство памяти БД обычно разделяется на части (области, сегменты и др.). (Во многих системах область соответствует файлу.) В каждой области памяти, как правило, хранятся данные одного объекта БД (одной таблицы). Сведения о месте расположения данных таблицы (ссылка на область хранения) СУБД хранит в словаре-справочнике данных (ССД). Области разбиваются на пронумерованныестраницы (блоки) фиксированного размера. В большинстве систем обработку данных на уровне страниц ведёт операционная система (ОС), а обработку записей внутри страницы обеспечивает только СУБД. Страницы представляются в среде ОС блоками внешней памяти или секторами, доступ к которым осуществляется за одно обращение [6]. Некоторые СУБД позволяют управлять размером страницы (блока) для базы данных. В таких системах размер страницы определяется на основе компромисса между производительностью системы и требуемым объёмом оперативной памяти. Страница имеет заголовок со служебной информацией, вслед за ко-торым располагаются собственно данные. В большинстве случаев в качестве единицы хранения данных принимается хранимая запись. На странице размещается, как правило, несколько хранимых записей, и есть свободный участок для размещения новых записей. Если запись не помещается на одной странице, она разбивается на фрагменты, которые хранятся на разных страницах и ссылаются друг на друга. Система автоматически управляет свободным пространством памяти на страницах. Как правило, это обеспечивается одним из двух способов:
При динамической реорганизации страниц записи БД плотно разме-щаются вслед за заголовком страницы, а после них расположен свободный участок (рис.
Достоинство такого подхода - отсутствие фрагментации. Недостатки:
Поиск места размещения новой записи может занять много времени. Система будет читать страницы одну за другой до тех пор, пока не найдёт странницу, на которой достаточно места для размещения новой записи. участковш реорганизация участков в воде страниц. I границе отдельных стоукгую ■Ш Рис. 4.1. Управление свободным простанством памяти на страницах Для того чтобы уменьшить время поиска места для размещения записей, при динамической реорганизации страниц могут создаваться так называемые инвентарные страницы, на которых хранятся размеры свободных участков для каждой страницы. Поиск свободного места для размещения новых записей осуществляется через инвентарные страницы, которые загружаются в оперативную память. При каждом удалении/размещении данных содержимое инвентарных страниц обновляется. Таким образом, обеспечение актуальности содержимого инвентарных страниц занимает дополнительное время, но оно меньше, чем время поиска свободного участка на страницах. Некоторые СУБД управляют памятью по-другому: они ведут список свободных участков. Здесь можно рассмотреть два варианта:
Ведение списков свободных участков не приводит к перемещению записи, и адрес записи можно определить с точностью до смещения на странице. Это ускоряет поиск данных, т.к. не нужно просматривать все записи на странице для поиска каждой конкретной записи. При запоминании новой записи система через инвентарные страницы ищет свободный участок, достаточный для размещения этой записи. (Обычно выбирается первый подходящий участок, размер которого не меньше требуемого.) Если выбранный участок больше, чем запись, то остаток оформляется в виде свободного участка. (При динамической реорганизации страниц запись просто размещается вслед за последней записью на данной странице.) После этого система корректирует содержимое инвентарных страниц (если они есть). При изменении записи, имеющей фиксированный формат, она просто перезаписывается на прежнее место. Если же запись имеет формат переменной длины, возможны ситуации, когда запись не помещается на прежнее место. Тогда запись разбивается на фрагменты, которые могут размещаться на разных страницах. Эти фрагменты связаны друг с другом ссылками, что позволяет системе "собирать" запись из отдельных фрагментов. Основным недостатком, возникающим при использовании списков сво-бодных участков, является фрагментация пространства памяти, т.е. появление разрозненных незаполненных участков памяти. Для того чтобы уменьшить фрагментацию, в подобных СУБД предусмотрены фоновые процедуры, которые периодически проводят слияние смежных свободных участков в один (например, участки 1 и 2 на рис. 4.1,в). Структура и представление хранимых данных, их размещение в про-странстве памяти и используемые методы доступа называются схемой хранения. Схема хранения оперирует в терминах типов объектов. В общем случае адреса записей БД нигде не хранятся. При поиске данных СУБД из словаря-справочника данных берёт информацию о том, в какой области памяти (например, в каком файле и/или на каких страницах памяти) расположены данные указанной таблицы. Но при этом для поиска конкретной записи (по значениям ключевых полей) система вынуждена будет прочитать всю таблицу. В РСУБД для ускорения поиска данных применяются индексы - специальные структуры, устанавливающие соответствие значений ключевых полей записи и "адреса" этой записи (КБД). Таким образом, вид адресации хранимых записей оказывает влияние на производительность, а также на переносимость БД с одного носителя на другой. Рассмотрим три вида адресации: прямую, косвенную и относительную. Прямая адресация предусматривает указание непосредственного местоположения записи в пространстве памяти. Прямая адресация используется, например, в системе ADABAS. Недостатком такой адресации является большой размер адреса, обусловленный большим размером пространства памяти. Кроме того, прямая адресация не позволяет перемещать записи в памяти без изменения КБД. Такие изменения привели бы к необходимости коррекции различных указателей на записи в среде хранения (например, в индексах, см. раздел 4.5.2), что было бы чрезвычайно трудоёмкой процедурой. Отсутствие возможности перемещать запись ведёт к фрагментации памяти. Указанные недостатки можно преодолеть, используя косвенную адресацию. Общий принцип косвенной адресации заключается в том, что в качестве КБД выступает не сам "адрес записи”, а адрес места хранения "адреса записи". Существует множество способов косвенной адресации. Один из них состоит в том, что часть адресного пространства страницы выделяется под индекс страницы (рис. 4.2). Число статей (слотов) в нём одинаково для всех страниц. В качестве КБД записи выступает совокупность номера нужной страницы и номера требуемого слота в индексе этой страницы (значения N, i на рис. 4.2). В i-м слоте на N-й странице хранится собственно адрес записи (смещение от начала страницы). Рис. 4.2. Косвенная адресация с использованием индексируемых страниц При перемещении записи она остаётся на той же странице, и слот по-прежнему указывает на неё (меняется его содержимое, но не сам слот). Если запись не вмещается на страницу, она помещается на специально отведённые в данной области страницы переполнения, и соответствующий слот продолжает указывать на место её размещения. |