Физическая организация данных
 Скачать 487.44 Kb.
|
|
Этот подход позволяет перемещать записи на странице, исключать фрагментацию, возвращать освободившуюся память для повторного использования. Третий способ адресации - относительная адресация. Простейший ва-риант относительной адресации может использоваться, например, в ситуации, когда данные одного объекта БД (таблицы) хранятся в отдельном файле и хранимая запись имеет формат фиксированной длины. Тогда в качестве значения КБД берётся порядковый номер записи, по которому можно вычислить смещение от начала файла. (Пример такой адресация - системы dBaseIII, dBaselV). Общий принцип относительной адресации заключается в том, что адрес отсчитывается от начала той области памяти, которую занимают данные объекта БД. Если память разбита на страницы (блоки), то адресом может выступать номер страницы (блока) и номер записи на странице (или смещение от начала страницы). В случае относительной адресации перемещение записи приведёт к изменению КБД и необходимости корректировки индексов, если они есть. Примечание: некоторые СУБД, использующие относительную адресацию, при необходимости перемещения отдельной записи оставляют КБД прежним. Т.е. физически запись хранится на новом месте, а по старому адресу хранится новый адрес записи. Это по-зволяет не менять КБД и не перестраивать индексы, но приводит к увеличению вре-мени доступа к записи (2 физических чтения вместо одного).
При создании новой записи во многих случаях существенно размещение этой записи в памяти, т.к. это оказывает огромное влияние на время выборки. Простейшая стратегия размещения данных заключается в том, что новая запись размещается на первом свободном участке (если ведется учёт свободного пространства) или вслед за последней из ранее размещённых записей. Среди более сложных методов размещения данных отметим хеширование и кластеризацию. Хеширование заключается в том, что специально подобранная хеш-функция преобразует значение ключа записи в адрес блока (страницы) памяти, в котором эта запись будет размещаться. Под ключом записи здесь подразумевается поле или набор полей, позволяющие классифицировать запись. Например, для таблицы СОТРУДНИКИ в качестве ключа записи может выступать полеНомер паспорта или набор полей (Фамилия, Имя, Дата рождения). Кластеризация - это способ хранения в одной области памяти таблиц, связанных внешними ключами (одна родительская таблица, одна или несколько подчинённых таблиц). Для размещения записей используется значение внешнего ключа таким образом, чтобы все данные, имеющие одинаковое значение внешнего ключа, размещались в одном блоке данных. Например, для таблицСО ТР УДНИКИ, ДЕТИ СО ТР УДНИКОВ, ТР УДОВАЯ КНИЖКА, ОТПУСКА в качестве внешнего ключа подчинённых таблиц выступает первичный ключ Идентификатор сотрудника таблицыСОТРУДНИКИ, и тогда при кластеризации все данные о каждом сотруднике будут храниться в одном блоке данных.
Рассмотрим основные способы доступа к данным: • Последовательная обработка области БД. Областью БД может быть файл или другое множество страниц (блоков) памяти. Последовательная обработка предполагает, что система последовательно просматриваетстраницы, пропускает пустые участки и выдаёт записи в физической последовательности их хранения.
Примечание: в иерархических и сетевых СУБД есть ещё доступ по структуре. Эта разно-видность доступа применяется для групповых отношений и позволяет перейти к пре-дыдущему или следующему экземпляру группового отношения, к экземпляру-владельцу группового отношения или к списку подчинённых экземпляров./р>
Определим индексирование как способ доступа к данным в реляци-онной таблице с помощью специальной структуры - индекса.
Индекс - это структура, которая определяет соответствие значения ключа записи (атрибута или группы атрибутов) и местоположения этой записи - КБД (рис. 4.3). Каждый индекс связан с определённой таблицей, но является внешним по отношению к таблице и обычно хранится отдельно от неё. Рис. 4.3. Пример индекса Индекс обычно хранится в отдельном файле или отдельной области па-мяти. Пустые значения атрибутов (NULL) не индексируются. Индексирование используется для ускорения доступа к записям по значению ключа и не влияет на размещение данных этой таблицы. Ускорение поиска данных через индекс обеспечивается за счёт:
Индексы поддерживаются динамически, т.е. после обновления таблицы - добавления или удаления записей, а также модификации индексируемых полей, - индекс приводится в соответствие с последней версией данных таблицы. Обновление индекса, естественно, занимает некоторое время (иногда, очень большое), поэтому существование многих индексов может замедлить работу БД. Примечание: в реальных СУБД существуют методы оптимизации переиндексации. Напри-мер, при выполнении пакетной операции модификации БД обновление индексов мо-жет происходить один раз после внесения всех изменений в данные. Обращение к записи таблицы через индексы осуществляется в два этапа: сначала СУБД считывает индекс в оперативную память (ОП) и находит в нём требуемое значение атрибута и соответствующий адрес записи (КБД), затем по этому адресу происходит обращение к внешнему запоминающему устройству. Индекс загружается в ОП целиком или хранится в ней постоянно во время работы с таблицей БД, если хватает объ-ёма ОП. Индекс называется первичным, если каждому значению индекса соответствует уникальное значение ключа. Индекс по ключу, допускающему дубликаты значений, называется вторичныгм. Большинство СУБД автоматически строят индекс по первичному ключу и по уникальным столбцам. Эти индексы используются для проверки ограничения целостности ишдие(уникальность). Для каждой таблицы можно одновременно иметь несколько первичных и вторичных индексов, что также относится к достоинствам индексирования. Различают индексы по одному полю и по нескольким (составные). Составной индекс включает два или более столбца одной таблицы (рис. 4.4). Последовательность вхождения столбцов в индекс определяется при его создании. Из примера на рис. 4.4 видно, что данные в индексе отсортированы по первому столбцу (ID), внутри группы с одинаковыми значениями ID - отсортированы по второму столбцу (EDATE), а внутри группы с одинаковыми значениями ID и EDATE - по третьему столбцу (CODE).
Рис. 4.4. Пример составного индекса
Существует множество способов организации индексов:
записи. Неплотные (разреженные) индексы строятся в предположении, что на каждой странице памяти хранятся записи, отсортированные по значениям индексируемого атрибута. Тогда для каждой страницы в индексе задаётся диапазон значений ключей хранимых в ней записей, и поиск записи осуществляется среди записей на указанной странице.
являются многоуровневые индексы в виде сбалансированных деревьев (B-деревьев, balance trees).
B-дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами B-дерева являются порядок n и количество уровней. Порядок - это количество ссылок из вершины i-го уровня на вершины (i+1)-ro уровня. Пример построения B-дерева порядка 3 приведён на рис. 4.5. lira is2 Шаг» 3*4,5 *4*6* *1*1» * Р*!3» Записи поступают в таком порядке шаг ключ * 4 * т *§#* Шаги 8Д10 • 4* т | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||