Физические структуры данных

Общий принцип организации внутренней схемы базы данных

Физические структуры организации файлов данных подразделяются на линейные и нелинейные.

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

Удаление записей в линейных структурах может производиться двумя способами. В первом способе при удалении записи сразу же осуществляется автоматическое перезаписывание на новых позициях всех строк-записей, лежащих за удаляемой, с целью уплотнения и ликвидации появляющихся пустых мест. Подобный подход обеспечивает максимальную эффективность использования дискового пространства, но вызывает существенные накладные расходы при любых операциях по удалению записей. Поэтому другим, достаточно распространенным способом является простое «вычеркивание» удаляемой записи без перезаписывания всех записей, лежащих за удаляемой, с соответствующим появлением пустых мест в страницах файла данных — razgovorodele.ru. Ведение базы данных в этом случае может быть организовано так, чтобы при превышении общего объема пустых мест в странице выше определенного значения (скажем, больше 30%) специальный компонент СУБД автоматически производил дефрагментацию страниц, устраняя пустые места по ранее удаленным записям. В некоторых СУБД запуск данной процедуры предоставляется непосредственно самому пользователю (администратору) для периодического уплотнения (сжатия) файла базы данных.

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

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

Линейная структура текстового файла

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

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

Такой подход применяется в широко используемых для создания «настольных информационных систем» (системы «рабочего стола») СУБД куста dBASE (dBase, FoxPro, Clipper), которые создают и оперируют базами данных в формате так называемых dbf-файлов. Структура dbf-файла состоит из трех частей* — заголовка, блока описания структуры базы и информационной части (см. схему ниже).

 Линейная структура dbf-файла

В заголовке последовательно представлены поля, которые определяют тип файла базы данных (с memo-полями или без них), дату последнего изменения, номер последней записи, смещение, с которого начинается информационная часть (записи), размер каждой записи. Блок описания структуры размещается после заголовка до информационной части и состоит из последовательности элементов, каждый из которых описывает определенное поле логической структуры (схемы) базы данных — razgovorodele.ru. Структура описания поля содержит последовательное описание имени поля, типа поля (числовое, текстовое, дата и т. д.), длины поля и заканчивается специальным символом для отделения описания одного поля от другого. Информационная часть состоит из последовательности групп байтов одинаковой длины без специальных разделителей, каждая из которых собственно и выражает содержимое конкретной физической записи.

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

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

Нелинейная структура данных ни примере односвязного списка (поля указателей выделены жирными рамками)

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

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

Образование страниц физических записей файлов данных осуществляется на основе той или иной стратегии минимизации расходов на доступ к записям и расходов на операции их добавления, удаления и корректировки, и существенным образом зависит от типа конкретной нелинейной структуры — razgovorodele.ru. Одной из таких стратегий является минимизация расходов на доступ к записям, связанным на логическом уровне отношением «Один-ко-многим», что обусловлено широкой распространенностью таких отношений в огромном количестве предметных областей АИС. Данная стратегия основывается на использовании иерархических древовидных структур.

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

Пример нелинейной древовидной иерархической структуры данных

Если в процессе ведения базы данных какая-либо страница переполняется, то для нее образуется связанная страница-продолжение на основе техники односвязного списка.*

* В конце каждой страницы выделяется специальное поле-указатель на возможное продолжение страницы (т.н. цепной список) помимо того, что каждая запись страницы сама содержит поле-указатель на страницу подчиненных записей.

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

Однако во многих предметных областях АИС отношения между информационными объектами могут порождать ситуации наличия у определенных записей на стороне «Многие» сразу нескольких разных предков на стороне «Один», что не вписывается в рамки подобных древовидных иерархических структур. Решение таких проблем обычно осуществляется через введение избыточности (дублирования) данных по связанным записям или другими способами.

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

Условное изображение средствами теории графов нелинейной древовидной иерархической структуры

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

Еще одним важным параметром деревьев является максимально возможное количество потомков у одного предка. Данный параметр называется степенью дерева. Деревья степени больше двух называются сильноветвистыми — razgovorodele.ru. И наконец, важным в практическом плане для нелинейных структур данных является понятие сбалансированности дерева. Различают сбалансированность по степени вершин, когда каждая внутренняя вершина может иметь количество потомков, ограниченное определенной и одинаковой для всех вершин величиной {арность дерева) и сбалансированность по высоте, когда путь (количество вершин) от корня до любого листа дерева одинаков или различается не более чем на единицу.

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