Формат и размещение физических (хранимых) записей

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

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

Существует несколько способов размещения элементов данных в хранимой записи, или иначе видов формата хранимой записи. Например, рассмотрим следующие виды организации хранимых записей или виды форматов хранимых записей: позиционный, с разделителями, индексный и с описателями. На рисунке 3.1 приведен пример структуры логической записи таблицы «Студент».

FIO	PREDMET	DATA	SROC	OCENKA
50, С	10, С	8 D	1 L	2, N
Смирнов Сергей Дмитриевич	Математика	3.01.95	.Y.

Рисунок 3.1 – Пример структуры логической записи отношения «Студент»

Виды форматов хранимых записей:

а) позиционный способ организации хранимых записей

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

б) способ хранения записей с разделителем

Запись имеет поля переменной длины и соответственно сама хранимая запись имеет переменную длину. Выбирается некоторый символ разделителя, который нигде больше при организации файлов базы данных не используется. Например, символ #. Тогда хранимая запись из примера будет выглядеть следующим образом:

Смирнов Сергей Петрович#47.5#07.02.94#Y#5

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

в) индексный способорганизации хранимых записей

При данном способе для определения начала значений элементов записей используется массив указателей, размещенный в служебной части записи. На рисунке 3.2 показан пример организации такой записи.

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

г) способ хранения с описателями

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

Например, известна фамилия студента и его средний балл, зато неизвестна оценка и признак сдачи (в срок или нет). Для этого примера введем такие описатели:

Описатель F вместо fio = фамилия имя отчество

Описатель P вместо predmet = средний балл

Описатель D вместо data= дата

Описатель R вместо Sroc = срок сдачи

Описатель O вместо Ocenka = оценка.

Тогда хранимая запись имеет вид: F Смирнов Сергей Петрович S47.5

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

Кроме формата организации хранимых записей важным является и способ кодирования конкретных значений данных. Каждый из символов элементов данных записи кодируется согласно выбранной системе кодирования в последовательность бит. Системы кодирования могут быть разными: ASCII (американская) система, международная, полевой код и другие. Для сокращения объема памяти при размещении хранимой записи используются различные способы сжатия (например, использование аббревиатуры, подавление нулей, то есть в записи вместо шести пробелов будет цифра 6 и знак «пробел» и другие способы кодирования). Кроме того для хранения записи могут объединяться в участки памяти фиксированного размера в физические экстенты – это кластеризация записей.

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

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

Обмен данных внешней памяти с оперативной памятью осуществляется блоками. Запись и чтение блоков осуществляется через буферную память оперативной памяти. Для организации каждого файла базы данных в зависимости от его размера во внешней памяти выделяется от одного до N блоков, где размещаются записи (в одном блоке могут, разместится все записи или в нескольких блоках – одна запись, либо в одном блоке – одна запись; от этого будет зависеть время считывания и записи элементов файла). Каждый байт в блоке имеет свой номер: 0, 1, 2, …, х. Номер байта блока, с которого начинается запись, определяет относительный адрес записи в блоке, то есть адрес записи равен номеру блока, плюс относительный адрес в блоке (последовательный доступ), либо номер блока и значение ключа (здесь сочетание последовательного и прямого методов доступа). Записи в блоках размещаются плотно, без промежутков, последовательно одна за другой. В блоке часть памяти отводится под служебную информацию: относительный адрес свободных участков памяти, указатели на следующий блок и так далее.

Для хранения поступающих данных, которые должны размещаться в одном блоке, заполненном уже полностью, выделяется дополнительный блок памяти в области переполнения записи, организованной в виде одного блока, где записи связываются указателями в одну цепь. Обычно стремятся область переполнения ограничить, так как время поиска информации в области переполнения сильно увеличивается. Поэтому, как только достигается предел области переполнения, проводят реорганизацию файла базы данных. Файлу добавляется нужное количество блоков в основной памяти и выполняется нужная перекомпоновка записей. При этом исходят из расчета, чтобы можно было освободить область переполнения, а все записи разместить в блоках часть незаполненной (пустой или резервной для возможного добавления записей). Для каждого файла блоки пронумерованы: 1, 2, …, N и система определяет требуемый файл по имени файла и по номеру блока. Таким образом, на скорость поиска влияют: объем блока в байтах, объем файла, количество записей в блоке файла, количество записей в блоке индекса, количество блоков в файле, доля резервной части блока, число полей в записи, размер записи в байтах, длина ключевого поля в записи.