Глава 4. Физическая организация баз данных
4.1. Физические модели данных
Исторически первыми стали использовать иерархические концептуальные модели. Простота организации, наличие заранее заданных связей между сущностями, сходство с внутренними (физическими) моделями данных позволяли добиваться приемлемой производительности иерархических СУБД на медленных ЭВМ с весьма ограниченными объемами памяти. Но если данные не имели древовидной структуры, то возникали сложности при построении иерархической модели, которые в значительной мере снимались в СУБД, основанных на сетевых моделях данных.
Сетевые модели по своей природе являлись инструментами, которые позволяли и позволяют построить системы с самой высокой производительностью. Это достаточно сложные структуры, состоящие из "наборов" – поименованных двухуровневых деревьев, максимально приближенных к физическим аспектам хранения. "Наборы" соединяются посредством "записей-связок", образуя цепочки с помощью встроенных физических указателей.
Практическое использование сетевых и иерархических СУБД, требовало от обычного пользователя знания нескольких внутренних языков СУБД, детально представлять логическую и физическую структуру базы данных для осуществления поиска необходимой информации среди различных экземпляров, наборов, записей и т.п., что существенно снижало их распространение. И самое главное отсутствие такого мощного формального средства взаимодействия с базой данных, как, например, языка SQL, переориентировало пользователей на СУБД, обеспечивающих взаимодействие с хранимой информацией на языках SQL или QBE, с помощью которых пользователь указывает, какие данные необходимо получить, не уточняя процедуру их получения.
Сегодня наиболее распространены реляционные модели, которые обладают достаточной простотой для пользователя.
Физические модели данных служат для отображения концептуальных моделей данных. Основными понятиями модели данных являются поле, логическая запись, логический файл. Слово "логический" введено, чтобы отличать понятия, относящиеся к логической модели данных, от понятий, относящихся к физической модели данных. Основными понятиями физической модели данных, используемыми для представления логической модели данных, являются поле, физическая запись, физический файл. В частности, логическая запись, состоящая из полей, может быть представлена в виде физической записи (из тех же полей), логический файл – в виде физического файла.
4.1.1. Cреды хранения и размещение хранимых данных
Информационная система (ИС) представляет собой программно-аппаратный комплекс, обеспечивающий выполнение следующих функций:
-
надежное хранение информации в памяти компьютера;
-
сбор и обработку хранимой информации в соответствии с спецификой объекта управления;
-
предоставление пользователям удобного и легко осваиваемого интерфейса.
Обычно такие системы имеют дело с большими объемами информации, имеющей достаточно сложную структуру. Классическими примерами ИС являются: банковские системы, автоматизированные системы управления предприятиями, системы резервирования авиационных или железнодорожных билетов, мест в гостиницах и т. д.
Условно, в истории вычислительной техники можно проследить развитие двух основных областей ее использования. Первая область — применение вычислительной техники для выполнения численных расчетов, которые нерентабельно производить вручную. Развитие этой области способствовало интенсификации методов численного решения сложных математических задач, появлению языков программирования, ориентированных на удобную запись численных алгоритмов, становлению обратной связи с разработчиками новых архитектур ЭВМ. Характерной особенностью данной области применения вычислительной техники является наличие сложных алгоритмов обработки, которые применяются к простым по структуре данным, объем которых сравнительно невелик.
Вторая область, которая непосредственно относится к базам, — это использование средств вычислительной техники в автоматических или автоматизированных информационных системах.
Вторая область использования вычислительной техники возникла несколько позже первой. Это связано с тем, что возможности компьютеров по хранению информации (на начальном этапе) были очень ограниченными. Говорить о надежном и долговременном хранении информации можно только при наличии запоминающих устройств (ЗУ), сохраняющих информацию после выключения электрического питания. В настоящее время к таким внешним ЗУ относятся магнитные и оптические диски.
Оперативная (основная) память компьютеров этим свойством обычно не обладает. В первых компьютерах использовались два вида устройств внешней памяти — магнитные ленты и барабаны. Емкость магнитных лент была достаточно велика, но по своей физической природе они обеспечивали последовательный доступ к данным. Магнитные же барабаны (они ближе всего к современным магнитным дискам с фиксированными головками) давали возможность произвольного доступа к данным, но имели ограниченный объем хранимой информации.
Эти ограничения не являлись слишком существенными для чисто численных расчетов. Даже если программа должна обработать (или произвести) большой объем информации, при программировании можно продумать расположение этой информации во внешней памяти (например, на последовательной магнитной ленте), обеспечивающее эффективное выполнение этой программы. Однако в ИС совокупность взаимосвязанных информационных объектов фактически отражает модель объектов реального мира, и потребность в информации, адекватно отражающей состояние реальных объектов, требует сравнительно быстрой реакции системы на запросы к хранимой информации. И в этом случае наличие сравнительно медленных устройств хранения данных, к которым относятся магнитные ленты и барабаны, становится недостаточным.
Фактически, именно требования нечисловых приложений вызвали появление съемных магнитных дисков с подвижными головками, что явилось революцией в истории вычислительной техники. Эти устройства внешней памяти обладали существенно большей емкостью, чем магнитные барабаны, обеспечивали удовлетворительную скорость доступа к данным в режиме произвольной выборки, а возможность смены дискового пакета на устройстве позволяла иметь практически неограниченный архив данных.
С появлением магнитных дисков началась история систем управления данными во внешней памяти. До этого каждая прикладная программа, которой требовалось хранить данные во внешней памяти, сама определяла расположение каждой порции данных на магнитной ленте или барабане и выполняла обмены между оперативной памятью и устройствами внешней памяти с помощью программно-аппаратных средств низкого уровня (машинных команд или вызовов соответствующих программ операционной системы).
Устройства хранения данных
В процессе работы СУБД для хранения данных используются два основных типа запоминающих устройств (ЗУ) хранения данных – первичные (оперативная память) и вторичные (магнитная лента, жесткий, оптический или компакт диск и т.д.).
В соответствии с методами управления доступом различают устройства внешней памяти с произвольной адресацией (магнитные и оптические диски) и устройства с последовательной адресацией (магнитофоны, стримеры).
На устройствах с произвольной адресацией теоретически возможна установка головок чтения-записи в произвольное место мгновенно. Практически существует время позиционирования головки, которое весьма мало по сравнению со временем считывания-записи.
В устройствах с последовательным доступом для получения доступа к некоторому элементу требуется "перемотать (пройти)" все предшествующие ему элементы информации. На устройствах с последовательным доступом вся память рассматривается как линейная последовательность информационных элементов (см. рис. 4.1).
Рис. 4.1. Модель хранения данных на устройстве последовательного доступа.
Файлы, расположенные на устройствах прямого доступа, являются файлами прямого доступа.
В этих файлах физический адрес расположения нужной записи может быть вычислен по номеру записи.
Каждая система управления файлами поддерживает некоторую иерархическую файловую структуру, включающую чаще всего неограниченное количество уровней иерархии в представлении внешней памяти (см. рис. 4.2).
Рис. 4.2. Иерархическая организация файловой структуры хранения.
Для каждого файла в системе хранится следующая информация:
-
имя файла;
-
тип файла (например, расширение или другие характеристики);
-
размер записи;
-
количество занятых физических блоков;
-
базовый начальный адрес;
-
ссылка на сегмент расширения;
-
способ доступа (код защиты).
Существуют принципиальные отличия в характеристиках данных устройств, влияющие на способы их использования при обработке данных [23, стр. 30, 24]:
а) скорость доступа: у первичных на несколько порядков выше;
б) скорость последовательного чтения/записи: у первичных на несколько порядков выше;
в) надежность и длительность хранения: у вторичных на несколько порядков выше;
г) стоимость хранения: у вторичных на несколько порядков ниже;
д) объем хранимых данных: у вторичных на несколько порядков больше.
Таким образом, первичные устройства предназначены для хранения наиболее интенсивно используемых в настоящий момент данных (высокая скорость доступа, чтения, записи для сравнительно малого объема данных), а вторичные устройства – для длительного и надежного хранения всего объема данных (большой объем данных сравнительно медленного доступа для дешевого и надежного хранения). В процессе работы одни и те же данные перемещаются из вторичных устройств в первичные (для быстрой обработки), затем – из первичных во вторичные (для длительного хранения).
Разница в характеристиках устройств и способах их применения для хранения данных приводит обычно к различным способам отображения данных в устройства хранения. Большинство СУБД при этом выполняют достаточно сложные операции преобразования с целью максимально эффективного использования и первичных и вторичных устройств.
Под информационной емкостью ЗУ понимают количество информации, измеряемое в байтах, килобайтах, мегабайтах или гигабайтах, которое может храниться в запоминающем устройстве. Обычно информационная емкость учитывает только полезный объем хранимой информации, не включающий объем памяти, расходуемый на служебную информацию, контрольные разряды или байты, резервные области, дорожки синхросигналов и пр.
Время обращения к ЗУ различных типов определяется по-разному. В качестве примера можно рассмотреть оперативные ЗУ и жесткие диски.
Основные свойства оперативной памяти:
-
единицей памяти является байт;
-
память прямоадресуема (каждый байт имеет адрес);
-
процессор выбирает для обработки нужные данные, непосредственно адресуясь к последовательности байтов, содержащих эти данные.
Р
ис. 4.3. Произвольный доступ к массиву элементов памяти
Оперативные ЗУ обычно реализуются как ЗУ с произвольным доступом. Это означает, что доступ к данным, физически организованным в виде двумерного массива (матрицы элементов памяти), производится с помощью схем дешифрации, выбирающих нужные строку и столбец массива по их номерам (адресам), как показано на рис. 4.3. Поэтому время обращения к ним определяется, временем срабатывания схем дешифрации адреса и собственно временами записи или считывания данных и находится в пределах наносекунд.
Основные свойства внешней памяти:
-
минимальной адресуемой единицей является физическая запись;
-
для последующей обработки (например, работы с полями) запись должна быть считана в оперативную память;
-
организация обмена осуществляется порциями, т.к. невозможно считать сразу всю базу данных.
Процесс обращения (чтения или записи) к жесткому диску показан на рис. 4.4. Он включает в себя 3 этапа: перемещение блока головок чтения/записи на нужную дорожку (а), ожидание подхода требуемого сектора под головки чтения/записи (б) и передача данных с диска или на него (в). Все этапы связаны с механическими перемещениями, поэтому их времена сравнительно велики и составляют величины порядка единиц миллисекунд.
О
бозначения на рис. 4.4:
1 – пластина диска, 2 – блок головок чтения/записи, 3 – дорожка (цилиндр),
4 – файл ;
а – поиск дорожки (перемещение блока головок чтения/записи, б – ожидание подхода файла под блок головок, в – передача данных
Рис. 4.4. Обращение к жесткому диску
Однако, для хранения данных и на тех, и на других устройствах используются одни и те же типовые схемы хранения данных, применительно к устройствам вторичной памяти. Знание типовых схем хранения позволит оптимизировать структуру БД на этапе физического проектирования и разработать более эффективные процедуры обработки данных на этапе создания приложения базы данных.
Принципы хранения данных на первичных и вторичных устройствах
База данных во вторичном устройстве хранения организована в виде одного или нескольких файлов, каждый из которых состоит из одной или нескольких физических записей, а каждая запись — из одного или нескольких полей.
Физическая запись является единицей обмена данными между вторичным и первичным устройствами хранения. Обычно физическая запись состоит из нескольких логических записей, хотя иногда, в зависимости от размера, одна логическая запись может соответствовать одной физической записи. Более того, одна логическая запись может даже соответствовать нескольким физическим записям. Иногда вместо понятия "физическая запись" используется термин блок или страница.
Порядок хранения записей в файле и доступа к ним зависит от структуры, или организации, файла.
Организация файла - физическое распределение данных файла по записям и страницам на вторичном устройстве хранения.
Логическая запись представляется в оперативной памяти в виде последовательности байтов. Длина этой последовательности определяется по описанию концептуальной модели, в которой указывается: тип поля и длина поля и не зависит. Указанное представление не делает различий для записей в сетевой, иерархической и реляционных моделях. В случае сетевой и иерархической моделей некоторые поля могут являться указателями, тогда последовательность байтов, используемая для хранения этих полей, содержит адрес начала последовательности байтов, соответствующей записи – члену отношения.
В большинстве современных СУБД используется формат записей фиксированной длины. В этом случае все записи имеют одинаковую длину, определяемую суммарной длиной полей, составляющих запись. В СУБД другие форматы записей (переменной длины, неопределенной длины) встречаются гораздо реже. Заметим, что поля записи, принимающие значения существенно разной длины в различных экземплярах записей, в предметной области встречаются достаточно часто. Примером может служить поле резюме в записи СОТРУДНИК. Резюме может составлять полстраницы текста, страницу и т.д. Возникает проблема – как эту информацию переменной длины представить в записи фиксированной длины. Возможным вариантом является установление размера соответствующего поля по максимальному значению. В этом случае у многих экземпляров записи указанное поле будет заполнено не полностью и, таким образом, память ЭВМ будет использоваться неэффективно. Более эффективный и часто используемый в СУБД прием организации таких записей состоит в следующем. Вместо поля (полей), принимающего значение существенно разной длины, в запись включается поле-указатель на область памяти, где будет размещаться значение исходного поля. Как правило, эта область является областью внешней памяти прямого доступа. В процессе ввода соответствующего значения в выделенной области занимается столько памяти, какова длина этого значения.
На рис. 4.5 представлен пример вышеуказанного представления экземпляров записей из N полей, причем поле N принимает значения соответственно разной длины у разных экземпляров записей.
Рис. 4.5. Представление полей переменной длины
Конкретной реализацией такой схемы является поле типа МЕМО в СУБД (Alaska++, FoxPro, Access и т.д.).
Как отмечалось выше единицей обмена данными между оперативной и внешней памятью является физическая запись. Физическая запись читается (записывается) за одно обращение к внешней памяти. В частности, физическая запись может соответствовать одному экземпляру логической записи. Число обращений к внешней памяти при работе с базой данных определяет время отклика системы. В связи с этим для уменьшения числа обращений к БД при работе с ней увеличивают длину физической записи (объединяют в одну физическую запись несколько экземпляров логических записей). В этом случае физическую запись называют также блоком, число k экземпляров логических записей, составляющих физическую запись, – коэффициентом блокировки.
В некоторых СУБД (например, MS SQL Server) единицей обмена между оперативной и внешней памятью является страница (вид физической записи, размер которой фиксирован и не зависит от длины логической записи).
Организация обмена между оперативной и внешней памятью в этом случае: физическая запись (блок) считывается в оперативную память и обрабатываются экземпляры логических записей внутри блока. Отличие здесь будет состоять в том, что экземпляры логических записей формируются в буфере, размером со страницу, если размер страницы не кратен длине логической записи, страница может быть заполнена неполностью, физическая запись на внешнем носителе, соответственно, будет заполнена не полностью.
4.1.2. Файлы и файловые системы
Важным шагом в развитии именно информационных систем явился переход к использованию централизованных систем управления файлами. С точки зрения прикладной программы, файл — это именованная область внешней памяти, в которую можно записывать и из которой можно считывать данные. Правила именования файлов, способ доступа к данным, хранящимся в файле, и структура этих данных зависят от конкретной системы управления файлами и, возможно, от типа файла. Система управления файлами берет на себя распределение внешней памяти, отображение имен файлов в соответствующие адреса во внешней памяти и обеспечение доступа к данным.
Конкретные модели файлов, используемые в системе управления файлами, рассматриваются далее, при описании физических способов организации баз данных, а на этом этапе нам достаточно знать, что пользователи видят файл как линейную последовательность записей и могут выполнить над ним ряд стандартных операций:
-
создать файл (требуемого типа и размера);
-
открыть ранее созданный файл;
-
прочитать из файла некоторую запись (текущую, следующую, предыдущую, первую, последнюю);
-
записать в файл на место текущей записи новую, добавить новую запись в конец файла.
В разных файловых системах эти операции могли несколько отличаться, но общий смысл их был именно таким. При этом, независимо от типа операционных систем, с каждым обрабатываемым файлом связывалось понятие идентификатора ресурса ОС, соответствующего этому файлу. В ранних ОС количество таких ресурсов было ограничено и находилось в пределах 16-255. Обычно сама ОС использовала 5-6 единиц из этого ресурса.
Главное, что следует отметить, это то, что структура записи файла была известна только программе, которая с ним работала, система управления файлами не знала ее. И поэтому для того, чтобы извлечь некоторую информацию из файла, необходимо было точно знать структуру записи файла с точностью до бита. Каждая программа, работающая с файлом, должна была иметь у себя внутри структуру данных, соответствующую структуре этого файла. Поэтому при изменении структуры файла требовалось изменять структуру программы, а это требовало новой компиляции, то есть процесса перевода программы в исполняемые машинные коды. Такая ситуации характеризовалась как зависимость программ от данных.
Для информационных систем характерным является наличие большого числа различных пользователей (программ), каждый из которых имеет свои специфические алгоритмы обработки информации, хранящейся в одних и тех же файлах. Изменение структуры файла, которое было необходимо для одной программы, требовало исправления и перекомпиляции и дополнительной отладки всех остальных программ, работающих с этим же файлом. Это было первым существенным недостатком файловых систем, который явился толчком к созданию новых систем хранения и управления информацией.
Далее, поскольку файловые системы являются общим хранилищем файлов, принадлежащих, вообще говоря, разным пользователям, системы управления файлами должны обеспечивать авторизацию доступа к файлам. В общем виде подход состоит в том, что по отношению к каждому зарегистрированному пользователю данной вычислительной системы для каждого существующего файла указываются действия, которые разрешены или запрещены данному пользователю. В большинстве современных систем управления файлами применяется подход к защите файлов, впервые реализованный в ОС UNIX. В этой ОС каждому зарегистрированному пользователю соответствует пара целочисленных идентификаторов: идентификатор группы, к которой относится этот пользователь, и его собственный идентификатор в группе. При каждом файле хранится полный идентификатор пользователя, который создал этот файл, и фиксируется, какие действия с файлом может производить его создатель, какие действия с файлом доступны для других пользователей той же группы и что могут делать с файлом пользователи других групп. Администрирование режимом доступа к файлу в основном выполняется его создателем-владельцем. Для множества файлов, отражающих информационную модель одной предметной области, такой децентрализованный принцип управления доступом вызывал дополнительные трудности. И отсутствие централизованных методов управления доступом к информации послужило еще одной причиной разработки СУБД.
Следующей причиной стала необходимость обеспечения эффективной параллельной работы многих пользователей с одними и теми же файлами. В общем случае системы управления файлами обеспечивали режим многопользовательского доступа. Если операционная система поддерживает многопользовательский режим, вполне реальна ситуация, когда два или более пользователя одновременно пытаются работать с одним и тем же файлом. Если все пользователи собираются только читать файл, ничего страшного не произойдет. Но если хотя бы один из них будет изменять файл, для корректной работы этих пользователей требуется взаимная синхронизация их действий по отношению к файлу.
В системах управления файлами обычно применялся следующий подход. В операции открытия файла (первой и обязательной операции, с которой должен начинаться сеанс работы с файлом) среди прочих параметров указывался режим работы (чтение или изменение). Если к моменту выполнения этой операции некоторым пользовательским процессом P1 файл был уже открыт другим процессом P2 в режиме изменения, то в зависимости от особенностей системы процессу P1 либо сообщалось о невозможности открытия файла, либо он блокировался до тех пор, пока в процессе P2 не выполнялась операция закрытия файла.
При подобном способе организации одновременная работа нескольких пользователей, связанная с модификацией данных в файле, реализовывалась очень медленно.
4.1.3. Основные характеристики баз данных, отличающие их от файловых систем
Рассмотренные в пункте 4.1.2 недостатки послужили толчком, который заставил разработчиков ИС предложить новый подход к управлению информацией. Этот подход был реализован в рамках новых программных систем, названных впоследствии Системами Управления Базами Данных (СУБД), а сами хранилища информации, которые работали под управлением данных систем, назывались базами данных (БД).
Ниже, коротко сформулированы критерии предпочтительности использования баз данных, по сравнению с традиционными файловыми системами:
-
.- повышение надежности, целостности и сохранности данных;
-
.- сохранение затрат интеллектуального труда;
-
.- простота и легкость использования данных, сложный доступ к данным осуществляет СУБД;
-
.- относительная независимость прикладных программ от изменений описаний данных и наоборот;
-
.- простота внесения изменений и обеспечение достоверности данных;
-
.- обеспечение требуемой скорости доступа;
-
.- стандартизация данных в пределах одной предметной области;
-
.- автоматизированная реорганизация данных;
-
.- защита от искажения и уничтожения;
-
.- сокращение дублирования информации за счет структурирования данных;
-
.- многократное использование данных;
-
.- создание предпосылок для распределенных баз данных.
|
