 |
Физическая организация данных
|
|
|
|
Общие положения
Вопросы физической организации данных в вычислительных системах возникли одновременно с появлением первых ЭВМ. При проектировании систем, ориентированных на хранение информации и поиск требуемых данных в общем массиве, вопросы физической организации становятся одними из центральных. Увеличение емкости запоминающих устройств и уменьшение стоимости хранения информации не снимают остроту вопросов, так как потребности пользователей растут с не меньшей скоростью. Эти потребности касаются не только объемов информации и скорости доступа к ней. Пользователь требует, чтобы система была надежна, обеспечивала секретность и безопасность хранимых в ней данных, автоматически проводила при необходимости реорганизацию данных. Основным фактором, влияющим на выбор физической организации, является минимизация объема памяти, требуемого для хранения данных, и времени доступа к данным, т.е. среднего времени, необходимого для поиска данных, относящихся к запросу.
Ряд требований к системе как к целому должен учитываться при выборе или разработке физической организации данных. К числу таких требований можно отнести:
· надежность - возможность автоматического восстановления испорченных в результате сбоя данных;
· секретность - обеспечение исключительно санкционированного доступа к данным;
· физическую независимость данных - возможность замены технического обеспечения (запоминающих устройств) без изменения способа адресации и программного обеспечения;
· контролируемую избыточность - дублирование данных, которое должно происходить только по экономическим или техническим причинам;
· возможность настройки - реконструкции данных в соответствии с изменением требований пользователя с целью улучшения производительности системы;
|
|
|
· автоматическую реорганизацию - преобразование размещения данных в памяти, ставшего в результате неэффективным, в более эффективное;
· простоту модификации - возможность внесения изменений в данные без изменения способа использования;
· разделение данных и связей, позволяющее уменьшить время поиска и в некоторых случаях объем памяти.
Под физической организацией понимается совокупность методов и средств размещения данных во внешней памяти и созданная на их основе внутренняя (физическая) модель данных. Внутренняя модель является средством отображения логической модели в физическую среду хранения.
В отличие от логической модели, физическая модель данных связана со способами организации данных на носителях методами доступа к данным. Она указывает, каким образом данные размещаются в БД, как они упорядочиваются, как организуются связи, каким путём можно локализовать запись и осуществить их выборку. Внутренняя модель разрабатывается средствами СУБД.
Очевидно, что любая логическая модель может быть отражена подобно тому, как один и тот же алгоритм может быть представлен множеством эквивалентных программ, составленным на одном или разных языках программирования.
Одна из внутренних моделей будет оптимальна. В качестве критериев оптимальности используются минимальное время ответа системы, минимальный объём, минимальные затраты на БД и др. Основными средствами физического моделирования в БД являются:
· структура хранения данных;
· поисковая структура;
· язык описания данных.
В простейшем случае структуру хранения данных можно представить в виде структуры записей файла БД, выключающей поля записей, порядок их размещения, типы и длины полей. Если структура хранения данных в основном предназначена для указания способа размещения записей и полей, то поисковые структуры определяют способ быстрого нахождения этих записей, поэтому различают 2 принципа физической организации БД:
|
|
|
1) Организация на основе структуры хранения данных;
2) Организация, сочетающая структуру хранения данных с одной или несколькими поисковыми структурами.
Конечным итого разработки физической организации БД являются файлы данных – файлы БД и файлы поисковых структур. Из множества типов поисковых структур СУБД на ПК чаще всего используются линейные и цепные списки, инвертирующие и индексные файлы.
Структуры данных
Структуризация данных основывается на двух понятиях: "агрегация" и "обобщение".
Агрегация данных. Агрегированное данное СТУДЕНТ является агрегацией данных: фамилия, имя, отчество, год рождения, специальность. Словесное описание связи между указанными данными: лицо по фамилии Петров, по имени Сергей, по отчеству Сергеевич, 1977 года рождения, обучающийся по специальности САПР, является студентом института. Запись типа СТУДЕНТ является агрегированным данным.
Лица:
Петров Сергей Сергеевич 1977 года рождения, обучающийся по специальности САПР,
Волков Алексей Николаевич, 1978 года рождения, обучающийся по специальности Криогенная техника,
являются студентами института.
Обобщение всех экземпляров записей типа СТУДЕНТ можно выполнить по следующей схеме.
Существует ряд терминов, используемых для обозначения разных типов структур данных. Самые распространенные из них следующие:
Элемент данных - наименьшая поименованная единица данных, к которой СУБД может адресоваться непосредственно и с помощью которой выполняется построение всех остальных структур. Элементы данных используются для представления отдельных элементарных свойств объектов, например, фамилия, табельный номер. Имя элемента данных используется для его идентификации в схеме структуры данного более высокого уровня. Значение элемента данных может быть числового и нечислового (символьного, логического) типа.
Агрегат данных - поименованная совокупность элементов данных внутри записи, которую можно рассматривать как единое целое. Имя агрегата используется для его идентификации в схеме структуры данного более высокого уровня. Агрегат данных может быть простым, если состоит только из элементов данных, и составным, если включает в свой состав другие агрегаты.
|
|
|
Запись - поименованная совокупность элементов данных или элементов данных и агрегатов. Имя записи используется для идентификации типа записи в схемах типов структур более высокого уровня. Запись - это агрегат, не входящий в состав никакого другого агрегата. Запись может иметь сложную иерархическую структуру, поскольку допускается многократное применение агрегации.
Набор - поименованная совокупность записей, образующих двухуровневую иерархическую структуру. Каждый тип набора представляет собой отношение (связь) между двумя или несколькими типами записей. Основное назначение набора - представление связей между записями.
База данных - поименованная совокупность экземпляров записей различного типа, содержащая ссылки между записями. Структура базы данных задается ее схемой.
Линейный список
В системах обработки данных при описании фактов и понятий предметной области между данными конструируются логические структурные отношения. В качестве логических структур используются либо таблицы, либо древовидные, либо сетевые структуры.
Форма представления структур данных в памяти ЭВМ зависит от того, как адресуются элементы структуры данных - по месту или по содержимому.
Наиболее простой формой хранения данных в памяти ЭВМ является одномерный линейный список. В отличие от остальных способов, он не требует создания дополнительных файлов. В соответствии с этим способом, файл БД рассматривается как последовательность невзаимосвязанных записей.
Линейный список - это множествo n объектов (узлов) Х[1], Х[2],..., Х[n ], структурные свойства которого связаны линейным (одномерным) относительным расположением узлов.
Если n>0, то Х[1 ] является первым узлом, для 1<i узел X[i-l] предшествует узлу X[i], a узел X[i+l] следует за ним, Х[n] является последним узлом, т.е. линейный список реализует структуру, которую можно определить как линейное упорядочение элементов данных. Линейный список Х рассматривают как последовательность Х[1], X[2],..., X[i],...., Х[n], компоненты которой идентифицированы порядковым номером, указывающим их относительное расположение в X.
|
|
|
Одномерный линейный список, используемый для хранения данных в памяти машины, называется вектором данных или физической структурой хранения данных. Отображение логической структуры данных на физическую структуру хранения в памяти ЭВМ называется адресной функцией. При реализации адресной функции используют два основных метода: последовательное распределение памяти и связанное распределение памяти.
Последовательное распределение памяти
Последовательное распределение - это простейший способ хранения линейного списка в памяти ЭВМ. В этом случае узлы списка размещаются в последовательных элементах памяти. Для представления двоичного дерева используется вектор памяти от элемента i до элемента j включительно, корень дерева размещается в элементе памяти с адресом y = (i + j)/2 - дробная часть.
Если m - размер записи, например, в байтах, то корень двоичного дерева размещается в середине вектора памяти, левое поддерево размещается в элементах памяти от i -го до (m-1) -го, а правое поддерево размещается в элементах памяти от (i+1)- го до j - го.
Адрес каждой записи вычисляется с помощью адресной функции, которая преобразует логический индекс записи в структуре в адрес физической памяти и вычисляет адрес каждого следующего элемента.
При последовательном распределении вектор данных логически отделен от описания структуры хранимых данных. Например, если структура данных представляет собой линейный список (файл записей фиксированной длины), то описание структуры хранится в отдельной записи и содержит:
а) N – размер вектора данных, т.е. количество элементов списка записей;
б) т – размер элемента списка, т.е. размер записи, например, в байтах;
в) β – адрес базы, указывающий на начало вектора данных в памяти.
Пример последовательного распределения памяти
для представления линейного списка
В этом случае адрес каждой записи можно вычислить с помощью адресной функции, отображающей логический индекс, идентифицирующий запись в структуре, в адрес физической памяти
В случае линейного списка адресная функция состоит из операций смещения и масштабирования. Любые отношения, которые можно выразить на языке целых чисел, можно истолковать как отношения между элементами памяти, получая при этом всевозможные варианты структур.
|
|
|
С помощью последовательного распределения можно организовать в памяти ЭВМ и некоторые сетевые структуры. Для представления сложных сетевых структур используется связанное распределение памяти.
Связанное распределение памяти
Для реализации сложных сетевых или древовидных структур используются связанные списки.
При связанном распределении для построения структуры необходимо задать отношения следования и предшествования элементов с помощью указателей. Указателями служат адреса, хранимые в записях данных.
Связанное распределение - более сложный, но и более гибкий способ хранения линейного списка. Каждый узел содержит указатель на следующий узел списка, т.е. адрес следующего узла списка. При связанном распределении не требуется, чтобы список хранился в последовательных элементах памяти. Наличие адресов связи позволяет размещать узлы списка произвольно в любом свободном участке памяти, а линейная структура списка обеспечивается указателями.
Структура линейного списка, представленная с помощью связанного распределения, называется цепной структурой.
Для достижения большей гибкости при работе с линейными списками в каждый узел X[i] вводится два указателя. Один реализует связь узла X[i] с узлом X[i+l], a другой - с узлом X[i-1].
В связанных списках любое изменение порядка записей, сокращение или расширение вектора данных в какой-либо записи не требует перемещения записей в памяти ЭВМ. Для выполнения этих операций достаточно изменить значения полей связи. Однако доступ к конкретному узлу может оказаться намного длительнее, чем при последовательном распределении памяти.
Важной разновидностью представления в памяти линейного списка является циклический список. В таком списке связь от последнего узла идет к первому узлу списка. В таких списках создается специальный узел - голова списка, который хранится в специальной ячейке памяти со специальным адресом. Существуют однонаправленные и двунаправленные циклические списки.
Основой построения связанных списковых структур являются указатели (адреса записей). В практике используются три типа указателей: действительный (машинный), относительный, символический (идентификатор).
Действительный адрес используется, когда необходимо получить наибольшую скорость обработки данных, организованных в связанные списковые структуры. Их недостаток - жесткая привязка записей к конкретному месту расположения в памяти. При необходимости переместить список на новое место в памяти ЭВМ, следует изменить указатели во всех записях.
Относительный адрес (указатель) позволяет размещать записи в любом месте памяти, при этом относительное расположение в памяти узлов списка между собой не должно изменяться. Относительные адреса в качестве указателей применяются при страничной организации памяти.
Символический адрес (указатель) позволяет перемещать отдельные записи относительно друг друга, включать или удалять записи в список без изменения указателей во всех остальных записях списка. При работе с такими указателями скорость доступа меньше, чем при работе с машинными или относительными адресами. Их удобно использовать в интенсивно изменяющихся файлах.
С точки зрения организации структуры данных различают два типа указателей: встроенные указатели и справочник указателей. Встроенные указатели представляют собой часть записи. Если указатели хранятся отдельно от записей, то они образуют справочник. Назначение указателей следующее:
- определение направления доступа (можно двигаться только в тех направлениях, которые заданы указателями),
- соединение связанных по смыслу данных, организация цепочки дисковых страниц, связывание памяти на дисках.
Методы доступа к базе данных
Доступ к базе данных можно рассматривать как последовательность обращений к хранимым записям. В зависимости от способа хранения записей можно рассматривать разные методы доступа к ним. Все методы доступа можно разделить на следующие группы:
- последовательные методы,
- индексные методы,
- адресные методы,
- мультисписковые методы.
Выбор того или иного метода зависит от планируемых запросов, требований по эффективности хранения и доступа к данным, используемой операционной системы и других причин. Существует два основных критерия оценки методов организации данных:
1. Эффективность доступа – величина, обратная среднему числу физических обращений, необходимых для осуществления логического доступа, т.е. запроса конкретной записи базы данных.
2. Эффективность хранения - величина, зависящая от числа байтов памяти, требуемой для хранения данных.
При последовательной обработке больших объемов данных наиболее эффективной является физически последовательная структура, которая представляет собой наиболее простой вид физической организации.
Последовательный метод доступа предполагает хранение физических записей в логической последовательности. Если носителем является память прямого доступа, система связывает физические записи таким образом, что они образуют логическую последовательность. Между записями организуются связи, обеспечивающие возможность логически последовательной выборки. При таком методе доступа для выборки нужной записи необходимо просмотреть все предшествующие записи базы данных. Чтобы добавить новую запись ее нужно поместить в последний блок. Таким образом, эффективность доступа последовательного метода довольно низка.
Хранение физических записей в логической последовательности можно использовать для ускорения доступа, если до обращения к собственно записям базы данных проверять значения ключей, которые хранятся в индексе. На этом принципе основаны индексные методы. В основе индексных методов доступа лежит принцип создания отдельного файла или списка из статей значений действительного ключа. Статья действительного ключа называется статьей индекса, а весь файл действительных ключей - индексом. Индексный файл значительно меньше собственно базы данных, скорость поиска в нем гораздо выше. Индексный файл упорядочивается по первичному ключу. Первичный ключ - главный атрибут физической записи. По его значению идентифицируется физическая запись. Индекс содержит ссылки не на каждую запись базы данных по ключу, а на группу записей в физическом блоке по диапазону ключей. Записи индекса группируются в блоки, которые также могут индексироваться, что позволяет улучшить характеристики доступа. Для очень больших файлов строят несколько индексных файлов, т.е. иерархию индексных файлов. При этом каждый индексный файл следующего уровня содержит указатели на индексный файл предыдущего уровня.
По мере расширения базы данных индекс приобретает все большее число элементов. Увеличение размера индексного файла, а также увеличение числа уровней индексации снижают эффективность доступа.
Работа с данными
Операции над данными
Выделение данных
Реализация любой операции над данными начинается с выделения из всей совокупности данных именно тех, над которыми должна быть выполнена требуемая операция. Это выделение может быть выполнено с использованием:
· логической позиции данного;
· значений данных;
· связей данных.
Использование логической позиции. Основано на определенной упорядоченности данных в памяти ЭВМ. Можно произвести выделение данного, находящегося на известной позиции, на следующей за ней или предыдущей. В этом случае применяются так называемые индикаторы текущего состояния. При выполнении прикладной программы СУБД автоматически поддерживает ее индикаторы текущего состояния.
Выделение по значениям данных. Производится по критериям выделения, которые могут определять простые или булевы условия отбора данных. Простые условия задаются на одном атрибуте и одном значении атрибута, вида:
< имя атрибута_ оператор условия _ значение атрибута >
Пример
Возраст < 20. Это означает выделение описаний студентов, у которых значение атрибута ВОЗРАСТ меньше 20 лет.
Булевы условия строятся на основе простых условий.
Простой оператор условия: =, <, >. Используя их, строят булевы условия с использованием операторов И, ИЛИ, НЕ.
Пример
ОБРАЗОВАНИЕ = ВЫСШЕЕ _ И _ СТАЖ > 1 - выбираются описания сотрудников, имеющих высшее образование и стаж работы более 1 года.
|
|
|
