ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ.
Пространство памяти и размещение хранимых данных
При табличном хранении данные на одной странице являются однородными, т. е. страница может содержать только данные или только индексы.
Заголовок страницы содержит системную информацию: идентификатор объекта данных, которому принадлежит страница; логический номер страницы; логические номера следующей и предыдущей страниц в цепочке; номер следующей свободной строки на странице. В конце страницы располагается таблица смещения строк.
Местоположение строки на странице определяется таблицей смещения строк (Row offset table). Таблица располагается в самом конце страницы и забирает дополнительно по 2 байта на каждую строку данных. Чтобы найти строку с заданным номером, SQL Server считывает из соответствующей ячейки смещение, которое и является адресом требуемой строки. Ячейка таблицы однозначно связана с определенным номером строки.
Страницы данных, относящиеся к одной таблице, объединяются в двунаправленный список и организуют цепочки.
Данные хранятся на страницах в виде строк (кортежей). Каждая строка данных кроме собственно данных хранит дополнительную форматирующую информацию. Длина строки зависит от определения полей таблицы и конкретных данных в ней.
51
ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ.
Пространство памяти и размещение хранимых данных
Существуют различные механизмы, позволяющие решать проблемы, которые возникают при модификации данных в БД, например:
Удаление записей может быть логическим или физическим. В первом случае запись помечается как удаленная, но фактически она остаётся на прежнем месте. Фактическое удаление этой записи будет произведено либо при реорганизации БД, либо специальной сервисной программой, инициируемой администратором БД.
При физическом удалении ранее занятый участок освобождается и становится доступным для повторного использования. Система автоматически управляет свободным пространством памяти на страницах. Как правило, это обеспечивается либо ведением списков свободных участков, либо динамической реорганизацией страниц.
При динамической реорганизации страниц записи БД плотно размещаются вслед за заголовком страницы, а после них расположен свободный участок. Смещение начала свободного участка хранится в заголовке страницы. При удалении записи оставшиеся записи переписываются подряд в начало страницы и изменяется смещение начала свободного участка.
52
ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ.
Пространство памяти и размещение хранимых данных
Структура хранимых данных
Единицей хранения данных в БД является хранимая запись. Она может представлять как полную запись концептуального уровня, так и некоторую её часть. Если запись разбивается на части, то её фрагменты представляются экземплярами хранимых записей каких-либо типов. Все части записи связываются указателями (ссылками).
Хранимые записи одного типа состоят из фиксированной совокупности полей и могут иметь формат фиксированной или переменной длины.
Хранимая запись состоит из двух частей:
1. Служебная часть. Используется для идентификации записи, задания её типа, хранения признака логического удаления, для кодирования значений элементов записи, для установления структурных ассоциаций между записями. Никакие пользовательские программы не имеют доступа к служебной части хранимой записи.
2. Информационная часть. Содержит значения элементов данных.
Каждой записи БД система присваивает внутренний идентификатор, называемый (по стандарту CODASYL) ключом базы данных (КБД). Значение КБД формируется системой при размещении записи и содержит информацию, позволяющую однозначно определить место размещения записи (её адрес). В качестве КБД может выступать, например, последовательный номер записи в файле или совокупность адреса страницы и смещения от начала страницы.
53
ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ.
Пространство памяти и размещение хранимых данных
Этапы доступа к БД
Опишем последовательность действий при доступе к БД (см. рис):
1.Сначала в СУБД определяется искомая запись, а затем для ее извлечения запрашивается диспетчер файлов (ДФ).
2.Диспетчер файлов одним из рассмотренных способов адресации определяет страницу, на которой находится искомая запись, а затем для ее извлечения запрашивается диспетчер дисков (ДД).
3.Диспетчер дисков определяет физическое положение искомой страницы на диске и посылает запрос на ввод – вывод данных (страница уже может находиться в ОЗУ).
С точки зрения СУБД база данных выглядит как набор записей, которые могут просматриваться с помощью ДФ. С точки зрения ДФ БД выглядит как набор страниц, которые могут просматриваться с помощью ДД.
ДД часто бывает компонентом ОС, с помощью которого выполняются все операции ввода/вывода, используя физические адреса записей. Однако ДФ не обязательно знать физические адреса записей, достаточно рассматривать диск как набор страниц фиксированного размера с уникальным идентификатором набора страниц.
54
СУБД
запрос хранимых записей
ДФ
запрос хранимых страниц
ДД
дисковые операции ввода/
вывода
БД
ДФ - диспетчер файлов дисков
Возврат хранимых записей
возврат хранимых страниц
ДД – диспетчер
Схема доступа к БД |
55 |
ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ.
Пространство памяти и размещение хранимых данных
Страница внутри набора обладает уникальным идентификационным номером страницы. Соответствие физических адресов на диске и номера станицы достигается с помощью ДД.
Преимущества страничной организации - все компоненты высокого уровня не зависят от конкретного диска.
Диск – это набор хранимых файлов. Файл – хранимый набор однотипных записей. В общем случае хранимый файл может храниться в памяти различными способами:
на одном томе памяти (диске);
на нескольких томах;
физически упорядоченным в соответствии со значением некоторого хранимого поля;
упорядоченным с помощью одного или нескольких индексов;
упорядоченным с помощью цепочек указателей;
к нему может быть обеспечен доступ методом хэш-адресации;
хранимые записи могут быть объединены в блоки (несколько логических записей в одной физической записи).
Набор страниц может содержать несколько хранимых файлов. Каждый хранимый файл имеет имя или идентификационный номер (file ID), уникальный в данном наборе страниц. А каждая хранимая (логическая) запись обладает идентификационным номером (record ID).
56
ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ.
Пространство памяти и размещение хранимых данных
ДФ выполняет следующие операции с файлами:
1.извлечь хранимую запись r из хранимого файла f;
2.заменить хранимую запись r в хранимом файле f;
3.удалить хранимую запись r из хранимого файла f;
4.добавить новую хранимую запись r в хранимый файл f;
5.создать новый хранимый файл f;
6.удалить хранимый файл f.
В одних СУБД ДФ – компонент ОС, а в других – СУБД.
Все страницы диска делятся на несвязанные наборы. Один из наборов, набор пустых страниц, - свободное пространство на диске.
Операции, выполняемые ДД с наборами страниц:
1.извлечь страницу P из набора S;
2.заменить страницу P в наборе S;
3.добавить новую страницу в набор S (извлечь ее из набора пустых страниц и добавить в набор S);
4.удалить страницу P из набора S (поместить ее в набор пустых страниц).
57
Пример 1 Рассмотрим БД «Заказы деталей», которая содержит таблицы ПОСТАВЩИКИ (Р1, Р2, Р3, Р4, Р5); ДЕТАЛИ (Д1, Д2, Д3, Д4, Д5, Д6); ПОСТАВКИ (РД1, РД2, РД3, РД4, РД5, РД6). Для размещения БД будет создан набор страниц:
0 |
1 |
2 |
Р2 |
3 |
Р3 |
4 |
Р4 |
5 Р5 |
|
|
Р1 |
|
|
|
|
|
|
6 |
7 |
8 |
9 |
10 |
11 |
Д1 |
Д2 |
Д3 |
Д4 |
Д5 |
Д6 |
12 |
13 |
14 |
15 |
16 |
17 |
РД1 |
РД2 |
РД3 |
РД4 |
РД5 |
РД6 |
18 |
19 |
пустые станицы на диске |
58
ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ.
Пространство памяти и размещение хранимых данных
На странице с номером 0 хранится информация о структуре БД:
количестве записей в таблицах;
их распределении по страницам;
о номерах и количестве пустых страниц. Выполним действия по модификации БД.
Добавить запись о поставщике Р6.
Для этого ДФ вставляет новую хранимую запись,
а ДД ищет первую пустую страницу (18),
а затем добавляет ее к набору страниц поставщиков.
Удалить запись о поставщике Р2.
ДФ удаляет запись,
а ДД возвращает страницу 2 в набор пустых страниц.
Добавить новую запись о детали Д7.
Для этого ДФ вставляет новую хранимую запись,
а ДД ищет первую пустую страницу (2),
а затем добавляет ее к набору страниц о деталях.
59
ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ.
Пространство памяти и размещение хранимых данных
После выполнения действий по модификации нельзя гарантировать, что логически близкие записи будут физически располагаться рядом.
Поэтому логическую последовательность страниц в данном наборе следует задавать с помощью указателей.
Для некоторого хранимого файла всегда можно осуществить последовательный доступ ко всем хранимым записям обычно в порядке возрастания RID (под термином «последовательный» понимаем доступ согласно последовательности записей внутри страницы и последовательности страниц внутри набора страниц). Такая последовательность называется физической, хотя она не всегда соответствует физическому расположению данных на диске. Это наиболее простой способ доступа к данным - последовательное сканирование.
Для ускорения поиска используются технологии хеширования, индексирования, поиска с использованием В-деревьев.
60