1. Теоретические сведения

1.1 Физическая организация данных. Основные понятия

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

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

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

Пример,

Отношение Сотрудник (табельный номер, номер отдела, имя):

record num: integer;

depNum: integer;

name: string [20];

end;

Часто при обсуждении физического хранения БД используется термин файл. В данном случае под файлом понимают набор записей одинакового формата. Под форматом записи понимают список полей с указанием их типов. То есть термин «файл» применяют для обозначения физического представления отношения БД. На самом деле БД может хранится в одном файле операционной системы (СУБД Interbase), во многих файлах, причем для каждого отношения существует свой файл (СУБД Paradox), или независимо от количества файлов, то есть БД может быть размещена в нескольких файлах, одновременно файл может включать несколько баз (СУБД MSSQL 6.5).

Рассмотрим организацию записи на диске.

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

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

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

3. Один бит может отводиться под информацию о том является ли запись удаленной или нет. В некоторых БД записи физически не удаляются, а соответствующий бит переводится в состояние «запись удалена». Такие записи продолжают храниться, но не рассматриваются при построении запросов. В этом случае СУБД должна иметь функцию сборки мусора. Этот процесс запускается в некоторый момент времени и перераспределяет записи, физически удаляя помеченные записи.

4. Бит использования. Он хранит информацию о наличии свободного места.

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

Если запись подразумевает такие типы данных как text, image, blob (двоичная информация), то такие данные не хранятся вместе с записью, а хранятся в отдельном блоке. В записи же хранится адрес.

Пример,

Пусть храним вышеописанную запись. В файле хранятся записи только одного формата. СУБД обеспечивает сборку мусора.

Отношение Сотрудник (табельный номер: integer, номер отдела: integer, фамилия: char(20), фото: image)

Рисунок 1 – Схема записи отношения сотрудник (в байтах)

1 - служебная информация;

2 - 5 – табел. номер;

6 - 9 – номер отдела;

10 - 29 – фамилия;

30 - 33 – ссылка на фото.

Если записи имеют переменную длину:

Сотрудник (табельный номер: integer, номер отдела integer, адрес varchar(100)) и СУБД имеет ограничение на длину строки с переменной длиной равной 255 символам (рисунок 2).

Рисунок 2 – Схема записи отношения сотрудник с переменной длинной (в байтах)

1 - служебная информация;

2-5 - табельный номер;

6-9 - номер отдела;

10 - фактическая длина фамилии;

11-109 – байты для хранения фамилии;

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

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

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

Рисунок 3 – Схема блока

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