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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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