Под физической организацией понимается совокупность методов и средств размещения данных во внешней памяти и созданная на их основе внутренняя (физическая) модель данных. Внутренняя модель является средством отображения логической модели в физическую среду хранения.
В отличие от логической модели, физическая модель данных связана со способами организации данных на носителях методами доступа к данным. Она указывает, каким обазом данные размещаются в БД, как они упорядочиваются, как организуются связи, каким путём можно локализовать запись и осуществить их выборку. Внутренняя модель разрабатывается средствами СУБД.
Очевидно, что любая логическая модель может быть отражена подобно тому, как один и тот же алгоритм может быть представлен множеством эквивалентных программ, составленным на одном или разных языках программирования.
Одна из внутренних моделей будет оптимальна. В качестве критериев оптимальности используются минимальное время ответа системы, минимальный объём, минимальные затраты на БД и др. Основными средствами физического моделирования в БД являются:
§ структура хранения данных;
§ поисковая структура;
§ язык описания данных.
В простейшем случае структуру хранения данных можно представить в виде структуры записей файла БД, выключающей поля записей, порядок их размещения, типы и длины полей. Если структура хранения данных в основном предназначена для указания способа размещения записей и полей, то поисковые структуры определяют способ быстрого нахождения этих записей, поэтому различают 2 принципа физической организации БД:
1) Организация на основе структуры хранения данных;
2) Организация, сочетающая структуру хранения данных с одной или несколькими поисковыми структурами.
Конечным итого разработки физической организации БД являются файлы данных – файлы БД и файлы поисковых структур. Из множества типов поисковых структур СУБД на ПК чаще всего используются линейные и цепные списки, инвертирующие и индексные файлы.
Линейный список – самый простой способ файловой организации БД. В отличие от остальных способов, он не требует создания дополнительных файлов. В соответствии с этим способом, файл БД рассматривается как последовательность невзаимосвязанных записей. Поиск новой из них выполняется путём вычисления адреса записи по некоторому алгоритму: по критерию минимальности памяти (самый канонический способ), но он проигрывает в быстродействии остальным методам.
Цепной список представляет собой файл, записи в котором имеют ссылки другие записи, образуя связанный (ассоциативный) список организации данных. Средствами связи (ссылками) элементов являются указатели, встраиваемые в записи в виде дополнительных полей. С помощью указателей устанавливается любой требуемый порядок выбора записи.
Поле, выделяемое для хранения указателя, называется адресом связи.
Чтобы войти в список, надо указать точку входа, то есть адрес начала списка. Такой адрес, как правило, хранится в отдельной записи, которая называется заголовком или фиксатором списка.
Рис. 19. Графическое представление цепного списка.
АНС – адрес начала списка
АС – адрес списка
КС – конец списка
ФС – фиксатор списка
4 – кол-во элементов.
Рис. 20. Табличное представление цепного списка.
В этом примере элементы списка размещены в памяти последовательно, в порядке: Иванов, Петров, Сидоров, Ясин, а выборка элементов, заданная указателем, записанным в АИС и адресе списка (АС), осуществляется в порядке: Петров, Иванов, Ясин, Сидоров.
В поле АС последнего читаемого элемента списка указан признак конца списка (КС). Если вместо КС поместить адрес фиксатора списка (ФС), то цепной список станет кольцевым. Добавление в список ещё одного указателя, то есть второго поля АС, позволяет сделать список двунаправленным.
В записи можно предусмотреть любое требуемое количество указателей k, и, следовательно, иметь k вариантов выборки записей в файле. Цепные списки наиболее удобны для представления во внешней памяти сетевой модели данных.
В БД, как правило, записи упорядочены по одному из полей (основному ключу), что позволяет сократить перебор записей при чтении файла БД. Для уменьшения времени поиска данных по не ключевым полям создаются инвертированные файлы.
Инвертированным называется файл, записи которого упорядочены по не ключевому полю. Процесс создания инвертированного файла состоит в переупорядочении по значению не ключевого поля, то есть в получении копии исходного файла иным порядком следования записей. Инвертирование основного файла будет полным, если созданы инвертированные файлы для каждого из его не ключевых полей, и частично, если они созданы только для части не ключевых полей.
Рис. 21. Процесс инвертирования файла.
Здесь приведена БД в составе основного файла, где записи упорядочены по ключевому полю «Фамилия», и инвертированного файла, записи которого упорядочены по не ключевому полю «Год» основного файла. При вводе запроса «Найти сотрудника с годом рождения меньше 1970» поиск данных необходимо вести не в основном порядке, где потребуется полный перебор записей, а в инвертированном файле, в котором для этого примера достаточно прочитать первые 2 записи.
Инвертированный файл обеспечивает быстрый поиск данных по не ключевому полю. По отношению к основному фалу БД, он является поисковой структурой. Однако появление инвертированного файла приводит к чрезмерно большому дублированию информации, то есть к перерасходу памяти. В связи с этим, целесообразно создавать не инвертированные файлы, а инвертированные файлы адресов записей основного файла, содержащего вместо записей БД их адреса. Такие файлы называются индексными файлами или просто индексами.
Они занимают малый объём памяти, каждая запись индекса содержит значение одного не ключевого файла, в которых встречается указанное значение не ключевого поля.
Файл БД, для обработки которого используется хотя бы один индекс, называется индексированным файлом. Построение индекса выполняется автоматически самой СУБД.
Рис. 22. Процесс построения индекса.
Поиска записей в БД с помощью индексов заключается в выборе индекса, поиске в индексе строки с заданным значением признака, выборки из этой строки списка адресов искомых записей и чтения этих записей в основном файле по указанным адресам методом прямого доступа.
Таким образом, БД может включать один основной и несколько вспомогательных файлов.
