Физическая организация БД.

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

К внутренним моделям данных предъявляется ряд требо­ваний, основными из которых являются:

· сохранение семантики логической организации дан­ных;

· максимальная экономия внешней памяти;

· минимальные затраты на ведение БД;

· максимальное быстродействие при поиске и выборке данных (минимальное время ответа системы на запрос).

Любая логическая модель может быть отражена множест­вом внутренних моделей данных. Задача разработчика банка данных — найти оптимальный вариант внутренней модели.

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

· организация на основе структуры хранения данных;

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

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

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

Линейный список — наиболее простой способ физической организации БД. В отличие от остальных трех способов он не требует создания дополнительных файлов. В соответствии с этим способом файл БД рассматривается как последователь­ность невзаимосвязанных записей. Поиск любой из них вы­полняется путем вычисления адреса записи по некоторому алгоритму. По критерию «минимум памяти» это самый эко­номичный способ. Однако по быстродействию он проигрывает остальным, поскольку необходимо затрачивать определенное машинное время на вычисление адресов.

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

Поле, выделяемое для хранения указателя, называется ад­ресом связи (АС). Чтобы войти в список, необходимо указать точку входа, т. е. адрес начала списка (АНС). Такой адрес хра­нится, как правило, в отдельной записи — фиксаторе (заго­ловке) списка (ФС) (рис. 16).

АНС

ФС АС АС АС

Рис. 16. Цепной список в графическом виде.

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

Цепные списки наиболее удобны для представления во внешней памяти ЭВМ сетевых моделей данных.

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

Пример БД в составе основного файла, записи которого упорядочены по ключевому полю ФАМИЛИЯ, и инвертиро­ванного файла ИФ_ГОД, записи которого упорядочены по неключевому полю ГОД основного файла:

Основной файл

Фамилия	Год	……
Борисов А. А.
Иванов И. Р.
Сейфуллин Р. С.

Инвертированный файл

Фамилия	Год	……
Иванов И. Р.
Сейфуллин Р. С.
Борисов А. А.

При вводе, например, запроса «найти сотрудников с годом рождения, меньшим 1970», поиск данных необходимо вести не в основном файле, где потребуется полный перебор запи­сей, а в инвертированном файле, в котором для нашего приме­ра достаточно прочитать две первые записи.

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

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

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

Пример физической организации базы данных в составе файла БД и индексного файла И1:

Основной файл

№	Фамилия	Год
	Борисов А. А.
	Иванов И. Р.
	Сейфуллин Р. С.
	Яшин Л. З.

Индексный файл

Год	Адреса
	002 003

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

БД={ФБД, [ИФ1, ИФ2, ….ИФn]},

где ФБД — основной файл БД;

ИФ_j — индексный файл; j = 1,2, …n;

n — количество индексных файлов, равное количеству ат­рибутов в ФБД или меньшее его.