14. Физическая организация данных

Определяет способ размещения БД на носителях. Используется два основных подхода:

1. Раздельное размещение объектов БД. Характерно для простых персональных СУБД. Каждый объект БД (таблица, индекс, представление и т.д.) хранится в отдельном файле. Размещение файлов на носителе, управление размерностью файлов осуществляется средствами файловой системы. Достоинством данного подхода является простота форматов данных, упрощение СУБД за счет передачи функций распределения памяти БД системному ПО. Недостаток – малая связность объектов БД, что затрудняет контроль данных и управление ими.

2. Совместное размещение объектов БД. Характерно для серверных СУБД. Под хранение БД отводится отдельный файл. Размещением объектов БД в отведенном пространстве управляют специальные средства СУБД. При этом для вновь созданного объекта отводится некоторая область памяти, которая по мере появления информации постепенно заполняется. При исчерпании отведенного под объект места СУБД выделяет объекту дополнительный участок памяти в свободном пространстве файла. При использовании всего свободного пространства файла СУБД создает дополнительный файл, пространство которого является логическим продолжением пространства основного файла. Кроме информационных объектов в пространстве файла БД размещаются вспомогательные и служебные объекты, содержащие дополнительную и метаинформацию, области для оперативной обработки данных и т.д. Для работы с памятью такие СУБД используют, как правило, страничную организацию, при которой вся область распределяемой памяти делится на дискретные единицы (страницы) и все распределение памяти осуществляется в данных единицах. Самостоятельное управление распределением памяти обеспечивает для СУБД полную управляемость данными, но «утяжеляет» СУБД.

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

1. Последовательная организация.

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

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

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

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

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

2. Списковая организация.

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

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

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

3. Индексная организация.

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

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