Физические модели организации баз данных

Физические модели определяет способ размещения данных в среде хранения и способы доступа к этим данным, которые поддерживаются на физическом уровне. Среди самых важных характеристик любой базы данных следует назвать производительность, надежность и простоту администрирования. Знание того, как большинство СУБД физически хранят данные во внешней памяти, представление о параметрах этого хранения и соответствующих методах доступа может очень помочь при проектировании баз данных, обладающих заданной производительностью. Любая логическая структура данных представляется на физическом уровне в виде последовательности битов.

Можно выделить следующие аспекты проблемы физического представления данных:

1. Как найти нужную запись? Необходимо установить соответствие между логической записью и адресом физической записи. Под физической зап и сью будем понимать последовательность битов, которые можно прочесть с помощью одной машинной инструкции. Логические записи находят по ключу или совокупности ключей.
2. Каким образом организовать данные, чтобы их поиск был эффективным, а выборку можно было осуществить по совокупности ключей?
3. Как можно добавить новую запись к данным, уничтожить старые записи и при этом не нарушить системы адресации и поиска, а также сами структуры данных.

Укажем основные факторы, влияющие на физическую организацию данных для конкретных БД:

1. произвольная или последовательная обработка данных. Для определения вид обработки используют коэффициент активности файла (k)

k=z1/z,

где z1 – число записей, считанных за 1 прогон; z - число записей, просмотренных за 1 прогон. Если k высок, то используют последовательную обработку, например при расчете заработной платы;

1. частота обращения к определенным записям;
2. время ответа (важно для систем реального времени);
3. способность к расширению (особенно, если добавляется записей больше, чем уничтожается);
4. возможность организации поиска по нескольким ключам.

Можно выделить следующие способы адресации (поиска нужной записи):

1. Последовательное сканирование файла с проверкой ключа каждой записи. Такой метод используется, если выбран последовательный метод обработки данных или используется файл последовательного доступа. Требует много времени.
2. Блочный поиск. Если записи упорядочены по ключу, то при сканировании не требуется чтение каждой записи. Считывается первая запись блока и ее ключ сравнивается с ключом искомой записи. А далее или просматриваются все записи данного блока или выбирается первая запись следующего блока.
3. Преобразование ключа в адрес - самая быстрая организация поиска. Сейчас применяется технология хэширования – технология быстрого доступа к хранимой записи на основе вычисления специальной функции от заданного значения некоторого поля. Это значение и является адресом для записи.
4. Поиск по индексу. Первичный индекс – индекс, использующий в качестве входной информации первичный ключ. В индексном файле запись состоит из индекса и указателя. Сначала проводится поиск в индексе, а потом по указателю обращаемся к основному файлу с записями. Эффективно, быстро, но требуется память для хранения индекса.
5. Бинарный (двоичный) поиск для записей, упорядоченных по ключу.
6. Поиск по В-дереву.

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

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

Структуры хранения информации в БД