Лекции и практики (1). Курс лекций и материалы для практических занятий

• Название: Курс лекций и материалы для практических занятий
• Дата: 17.03.2023
• Размер: 1.01 Mb.
• Имя файла: Лекции и практики (1).docx
• Тип: Курс лекций; #996812
• страница: 22 из 75

Структура хранимых данных

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

Хранимые записи одного типа состоят из фиксированной совокупности полей и могут иметь формат фиксированной или переменной длины.

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

Хранимая запись состоит из двух частей:

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

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

Каждой хранимой записи БД система присваивает внутренний идентифи- катор, называемый (по стандарту CODASYL) ключом базы данных (КБД). (Иногда используется термин идентификатор строки, RowID). Значение КБД формируется системой при размещении записи и содержит информацию, поз- воляющую однозначно определить место размещения записи (преобразовать значение КБД в адрес записи). В качестве КБД может выступать, например, по- следовательный номер записи в файле или совокупность адреса страницы па- мяти и смещения от начала страницы.

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

3. Управление пространством памяти и размещением данных

Ресурсам пространства памяти соответствуют объекты внешней памяти ЭВМ, управляемые средствами операционной системы или СУБД.

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

Страницы представляются в среде ОС блоками внешней памяти или сек- торами, доступ к которым осуществляется за одно обращение [5]. Некоторые СУБД позволяют управлять размером страницы (блока) для базы данных. В та- ких системах размер страницы определяется на основе компромисса между производительностью системы и требуемым объёмом оперативной памяти.

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

Система автоматически управляет свободным пространством памяти на страницах. Как правило, это обеспечивается одним из двух способов:

• 
  ведение списков свободных участков;
  
• 
  динамическая реорганизация страниц.
  

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

Достоинство такого подхода – отсутствие фрагментации. Недостатки:

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

а) динамическая реорганизация страниц

б) списки свободных участков на странице

в) списки свободных участков в виде отдельных структур

Рис. 5.1. Управление свободным простанством памяти на страницах

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

Некоторые СУБД управляют памятью по-другому: они ведут список свободных участков. Здесь можно рассмотреть два варианта:

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

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

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

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

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

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

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

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