Калабухов Е.В. Курс лекций по дисциплине Базы данных, знаний и экспертные системы

Подождите немного. Документ загружается.

Физические модели данных в данном курсе рассмотрены со стороны

структур и методов хранения данных во вторичной памяти компьютера, т.к. эти

вопросы оказывают существенное влияние на физическое проектирование БД.

4.4.1. Основные понятия физического хранения данных

Под физическим хранением (структурой хранения) данных будем

понимать размещение данных на вторичных устройствах хранения (например,

на основных сегодня вторичных устройствах хранения - накопителях на

жестких магнитных дисках типа «винчестер»)

Не существует идеальной структуры хранения, которая была бы

оптимальной для всех задач, поэтому СУБД обычно поддерживает несколько

разных структур хранения данных. Основной критерий оптимальности

структуры хранения – число операций ввода-вывода данных.

СУБД

Диспетчер

файлов

Диспетчер

дисков

БД на диске

Запрос физической записи

Запрос физической страницы

Дисковая операция

ввода/вывода

Чтение данных с диска

Возврат физической страницы

Возврат физической записи

Рисунок 19. Компоненты доступа к данным БД.

Для организации доступа к данным в СУБД используются следующие

101

компоненты:

1) Диспетчер дисков – компонент операционной системы, с помощью

которого выполняются определение физического адреса данных и все дисковые

операции ввода-вывода данных. Диспетчер дисков рассматривает диск как

наборы страниц фиксированного размера. Каждая страница имеет свой

уникальный идентификатор – идентификационный номер страницы. Каждый

набор также имеет свой уникальный идентификационный номер набора, а

также наборы не имеют общих страниц. Существует специальный набор –

набор пустых страниц, в который входят все свободные от данных страницы.

Основные операции диспетчера дисков:

•

извлечь страницу s из набора страниц f;

•

заменить страницу s из набора страниц f;

•

добавить новую страницу в набор страниц f (данная страница извлекается

из набора пустых страниц, как правило добавление страниц идет

экстентами – блоками физически связанных страниц (например, страница

= 8 Кб, экстент = 8 страниц));

•

удалить страницу s из набора страниц f (данная страница возвращается в

набор пустых страниц);

2) Диспетчер файлов – компонент, с помощью которого СУБД получает

возможность выполнять операции над файлами. Файл – хранимый на диске

набор однотипных физических записей, которые в свою очередь состоят из

полей. БД организуется на диске в виде совокупности файлов. Каждый файл

имеет имя (или уникальный идентификатор). Каждая запись файла имеет

уникальный идентификационный номер записи. Обычно размер записи гораздо

меньше размера страницы, но не исключается и обратное – одна запись

занимает несколько страниц диска. Основные операции диспетчера файлов:

•

извлечь запись r из файла f;

•

изменить запись r в файле f;

•

добавить запись r в файл f;

•

удалить запись r из файла f;

102

• создать новый файл f;

•

удалить файл f;

Процесс доступа к данным в этой схеме следующий:

1) СУБД определяет искомую логическую запись, отображает

логическую запись на физическую запись и запрашивает для ее извлечения

диспетчер файлов.

2) Диспетчер файлов по описанию физической записи (имя файла, номер

записи) определяет страницу, на которой запись расположена. Для извлечения

этой страницы запрашивается диспетчер дисков.

3) Диспетчер дисков определяет физическое положение страницы на

диске и выполняет операции ввода-вывода данных. Для повышения

производительности работы с диском выполняется кэширование

запрашиваемых страниц данных в специальных буферах памяти, страница

может храниться в этом буфере пока не потребуется место для обработки

другой страницы данных. Диспетчер дисков уведомляет о проведенной

операции диспетчер файлов.

4) Диспетчер файлов извлекает искомую физическую запись из страницы

данных, переданной ему диспетчером дисков, и уведомляет об операции СУБД.

5) СУБД получает искомую запись от диспетчера файлов.

Порядок хранения записей и доступ к ним зависит от организации файла

– физического распределения данных файла по записям и страницам на диске.

Основные типы организации файлов:

•

последовательные неупорядоченные и упорядоченные файлы;

•

хешированные файлы.

Кроме указанных типов организации файлов также используются

специальные структуры хранения в виде совокупности файлов – индексы.

Для обращения к данным (определения местоположения записей)

используется соответствующий метод доступа.

103

4.4.2. Последовательные неупорядоченные и упорядоченные файлы

Неупорядоченные последовательные файлы (heap, pipe) – файлы, в

которых записи размещаются в том порядке, в котором они в этот файл

добавляются. Новая запись всегда помещается на последнюю страницу файла.

Если на данной странице нет места для размещения записи, то к файлу

добавляется новая страница.

Преимущество неупорядоченных последовательных файлов - операции

вставки записей выполняются очень эффективно, поэтому такие структуры

идеально подходят для пакетной загрузки данных.

Недостатками данных структур являются:

•

медленный поиск записей, т.к. поиск выполняется последовательно путем

перебора записей файла от первой до последней, пока не встретиться

искомая запись;

•

медленное удаление записей, т.к. для поиска удаляемой записи также

используется последовательный поиск;

•

при удалении записей возникают «дырки» - пометки об удаленных

записях (с одной стороны это не требует немедленного физического

сжатия файла, с другой стороны – раздувается размер файла и

соответственно увеличивается время поиска). Физическое сжатие файла

для избавления от «дырок» («сборка мусора») требует определенных

временных затрат.

Упорядоченные последовательные файлы – файлы, в которых записи

располагаются упорядоченно (т.е. отсортированы по некоторому ключу). В

качестве ключа обычно выступает первичный ключ в структурах БД.

Главное преимущество подобной организации файлов – возможность

выполнения быстрого поиска записей по значению ключевого поля. Быстрый

поиск выполняется методом бинарного поиска (или делением пополам):

1) извлечение средней страницы в заданной зоне поиска (для первого

вхождения рассматривается весь файл целиком);

104

2) выполнения сравнения значения ключевого поля первой записи извлеченной

страницы с искомым значением ключа:

•

если значения совпадают, то искомая запись найдена, поиск завершен;

•

если осталась только одна страница в зоне поиска, то поиск проводится

среди записей этой страницы (методом перебора), поиск завершается

либо успешно, либо неудачно (нет совпадений значений ключа);

•

если извлеченное значение больше искомого, то поиск надо продолжить в

зоне поиска, начиная с извлеченной страницы, которая будет

рассматриваться как новая зона поиска, переход к шагу 1;

•

если извлеченное значение меньше искомого, то поиск надо продолжить

в зоне поиска перед извлеченной страницей, которая будет

рассматриваться как новая зона поиска, переход к шагу 1;

Также достоинством упорядоченных файлов является быстрое удаление

данных (влияние быстрого поиска, данные физически не удаляются, а только

помечаются, удаленные записи позволяют быстрее проводить вставку данных,

т.к. потребуется сдвиг записей для освобождения места только до места

удаленной записи, а не до конца файла).

При последовательном доступе к записям упорядоченного файла,

получаем отсортированный по ключу список, что выгодно использовать для

формирования отчетов.

Недостатком упорядоченных последовательных файлов:

усложнение операций вставки записей – необходимо соблюдать

упорядоченность записей, поэтому на поиск места расположения записи и

перемещение записей для освобождения свободного места приходится тратить

время; для повышения производительности в этом случае могут использоваться

файлы переполнения – последовательные неупорядоченные файлы, которые

выступают в роли буфера, куда помещаются данные пока выполняется вставка

записей, записи из буфера помещаются в упорядоченный файл либо когда есть

свободное время в системе, либо перед выполнением чтения записей из

упорядоченного файла.

105

Если в объекте данных БД определен первичный индекс, то для его

хранения оптимально использовать упорядоченный последовательный файл.

4.4.3. Хешированные файлы

Хеширование (hashing - перемешивание) – это технология быстрого

прямого доступа к физической записи на основе заданного значения поля

перемешивания (хеш-ключ).

Различают статическое и динамическое хеширование.

Для статического хеширования, размер хеш-файла задается один раз при

его создании и больше не изменяется (фиксируется пространство хеш-адресов).

Для вычисления адреса страницы, на которой должна храниться запись,

используется хеш-функция, аргументами которой являются значения одного

или нескольких полей записи (хеш-ключ). Хеш-функция выбирается таким

образом, чтобы записи внутри файла были размещены максимально

равномерно, но в статических хеш-файлах все равно остается чистое место

(чистые страницы разбросанные по всему файлу) под неиспользованные

значения хеш-ключа.

Методы хеширования основываются на:

•

свертке – арифметические действия над частями поя перемешивания;

•

использовании остатка от деления – хеш-ключ делится на некоторой

простое число;

Преимущество хеш-файлов – быстрый доступ к записям по известному

значению хеш-ключа, который осуществляется в два этапа:

•

вычисление адреса страницы с помощью хеш-функции и известного хеш-

ключа;

•

извлечение данной страницы и последовательный поиск в ней заданной

записи.

К недостаткам статических хеш-файлов относят следующие:

106

• физическая последовательность записей в файле почти всегда отличается

от логической последовательности, последовательный перебор записей

фактически не имеет смысла;

•

между записями в файле могут быть чистые промежутки – зависит от

выбора хеш-функции;

•

возникновение коллизий – ситуаций, когда записи имеют одинаковые

хеш-адреса и не вмешаются на адресуемую страницу.

Для разрешения коллизий используют следующие методы:

1) Открытая адресация – после нахождения хеш-адреса, запись

вставляется на ближайшее свободное место, которое находится

последовательным перебором начиная с данной страницы, поиск выполняется

аналогично. Этот метод используют при очень редких коллизиях.

2) Несвязанная область переполнения – все записи непомещающиеся на

страницу размещаются в специальной области (например, в последовательном

неупорядоченном файле), поиск проводится по странице, а в случае неудачи

продолжается в области переполнения. Этот метод также используется при

очень редких коллизиях.

3) Связанная область переполнения – для каждой страницы с коллизиями,

формируется специальная область (связный список страниц), с которой данная

страница связана через указатель. Этот метод можно использовать при частых

коллизиях.

4) Многократное хеширование – применение нескольких хеш-функций,

если первая хеш-функция приводит к коллизии.

5) Смена хеш-функции – при этом придется сформировать новый хеш-

файл и скопировать в него данные, используя новую хеш-функцию.

Динамическое хеширование позволяет динамическое изменение размера

хеш-файла при добавлении в него записей. Кроме того, динамическое

хеширование исключает коллизии. Основной принцип динамического

хеширования заключается в рассмотрении хеш-адреса, как битовой

последовательности и распределение записей на страницах на основе

107

прогрессивной оцифровки этой последовательности.

Один из типов динамического хеширования называется расширяемое

хеширование. Основные принципы расширяемого хеширования:

1) В результате вычисления хеш-функции h для поля k записи r будет

получен псевдоключ s. Псевдоключ используется не как адрес, а как косвенный

указатель на место хранения записей.

2) Хеш-файл имеет каталог, имеющий глубину каталога d и содержащий

указателей на страницы данных.

3) Если старшие d бит псевдоключа рассматривать как двоичное число b,

то i-ый указатель в каталоге (

i 21

≤

) будет относиться к странице, на которой

хранятся записи с .

1−= ib

4) Каждая страница данных имеет заголовок с указанием локальной

глубины p (

≤

) этой страницы (локальная глубина показывает, сколько

указателей каталога могут на нее ссылаться - указателей).

pd −

Чтобы найти искомую запись в динамическом хеш-файле, необходимо

выполнить следующие действия:

1) найти значение псевдоключа s;

2) по первым d битам псевдоключа s определить значение указателя

каталога (первое обращение к диску – считывание каталога);

3) по этому указателю считать с диска страницу, содержащую исходную

запись (второе обращение к диску).

Записи добавляются в хеш-файл следующим образом:

1) выполняется поиск страницы для вычисленного псевдоключа s

вставляемой записи (аналогично процессу чтения записи);

2) если место на найденной странице для записи есть, то производится

запись данных на указанную страницу;

3) если найденная страница заполнена полностью, то необходимо

расширение хеш-файла:

•

если локальная глубина страницы меньше локальной глубины каталога

(рисунок 20, 2 < 3), то указанная страница делится на две части,

108

локальная глубина полученных страниц будет на 1 больше исходной (2 +

1 = 3); на первой странице будут размещены все записи с b = 000…, а на

второй странице – c b = 001…; указатели каталога будут соответственным

образом скорректированы;

•

если локальная глубина страницы равна глубине каталога, то требуется

перед разделением страницы выполнить дублирование каталога – эта

операция увеличивает глубину каталога на 1, а каждый указатель

каталога заменяется парой смежных указателей (например, указатель 000

разделится на 0000 и 0001), значения которых будут хранить ссылку на

страницу данных, которая хранилась в старом указателе; дублирование

каталога производится быстро и без обращения к страницам данных.

0001

0000

010

000

001

010

011

100

101

110

111

d=3

011

000

001

Рисунок 20. Расширяемое хеширование.

109

Удаление записей является обратной операцией к записи данных в хеш-

файл и приводит к его уменьшению.

Главный недостаток любого варианта хеширования – поиск записей

возможен только по хеш-ключу.

4.4.4. Индексы

Индекс – структура данных определенного вида, которая предназначена

для ускорения поиска записей файла данных.

В простейшем варианте, индекс представляет собой файл, записи

которого содержат ключ (поле, содержащее одно или несколько атрибутов

записи файла данных и предназначенное для осуществления поиска записей по

этому критерию) и указатель (поле, содержащее адрес записи в файле данных).

Поле адреса заполняется СУБД. Записи индекса упорядочиваются по

ключевому полю. Файл данных, для которого существует индекс, называется

индексированным, а поле индексированного файла, значения которого

используется в индексе, называется индексным полем. Индекс можно создать

как по одному полю, так и по нескольким полям, причем не обязательно

относящимся к первичному ключу.

ФАМИЛИЯ АДРЕС ФАМИЛИЯ ИМЯ ОТЧЕСТВО ДАТА

Иванов Петров Петр Петрович 10.10.01

Михайлов Иванов Иван Иванович 11.10.01

Петров Сидоров Сидор Сидорович 15.10.01

Сидоров Михайлов Михаил Михайлович 01.11.01

… …

Индексный

айл Файл данных

Рисунок 21. Структура простого индекса.

Основное преимущество использования индексов – значительное

ускорение выборки данных. Вместо поиска записи в файле данных (обычно

110