Понятие о системных ресурсах.

Чтобы достичь высокой производительности системы необходимо решить каким образом 4-е основных компонента будут (ОЗУ, процессор, ВЗУ, сеть) взаимодействовать между собой и как это повлияет на достигнутый уровень производительности ОЗУ.

Доступ к данным в ОЗУ (определение память) осуществляется немного быстрее (в 100-1000 раз), чем к данным во вторичной памяти (ВЗУ). В общем случае, чем больше объём доступной СУБД оперативной памяти, тем быстрее будут работать приложения. Если в системе не хватает ОП для удовлетворения всех процессов, то ОС освобождает часть этой памяти, выталкивая отдельные страницы некоторых процессов на диск (ВЗУ).Эти страницы будут считаны с диска, как только вновь потребуется доступ к содержащимся в них данным. Установить наличие проблем с объёмом доступной ОП по высокому уровню страничного обмена в системе.

2. Процессор. Устанавливает задачи для системных ресурсов и выполняет пользовательские запросы (процессы). Важнейшим условием эффективной работы этого компонента является предотвращение конкуренции за право его использования, что обычно сопровождается переводом пользовательских процессов в режим ожидания. Процессор становится узким местом системы в тех случаях, если операционная система или программы пользователей выставляют слишком много требований для получения доступа к нему (программу), обычно эта ситуация приводит к резкому возрастанию страничного обмена.

3. Дисковый ввод-вывод. В любой, достаточно мощной СУБД, процессы сохранения и выдачи данных связаны с выполнением множества дисковых операций ввода-вывода.Как правило, изготовители ДУ(дисковых устройств) указывают количество операций ввода-вывода в секунду.Если реальный показатель превышает данное значение, то дисковая подсистема превращается в узкое место системы. На общую производительность системы оказывает влияние способ организации хранения данных. Рекомендуется равномерно распределять сохраняемые данные между всеми доступными устройствами в системе, что снижает вероятность появления проблем. Принцип распределения данных на дисковых устройствах показан на рис.6.4.1.

Рис 6.4.1. Типичная конфигурация дисковых файлов.

Желательно, чтобы файлы ОС, БД, индексов и файл журнала восстановления были отделены друг от друга.

4. Сеть. Сеть может стать узким местом системы при чрезмерном возрастании сетевого трафика или большом количестве сетевых коллизий (конкуренций за один ресурс).

В целом каждый из рассмотренных ресурсов способен оказывать влияние на остальные системные ресурсы.Поэтому улучшение состояния одного ресурса влечет за собой улучшение состояния всех остальных ресурсов.Например, увеличение объёма ОП, вызовёт снижение уровня страничного обмена и, как следствие, уменьшение количества дисковых операций.

Учитывая вышеуказанное, рассмотрим те действия (подэтапы), которые должны бать выполнены на 5-ом этапе разработки БД:

5.1. Анализ транзакций.

5.2. Выбор файловой структуры.

5.3. Определение вторичных индексов.

5.4. Анализ необходимости введения контролируемой избыточности данных

5.5. Определение требований к дисковой памяти.

Рассмотрим подробнее подэтапы 5.1 и 5.2.

 

 

Анализ транзакций.

Цель- определение функциональных характеристик, которые будут выполняться в проектируемой системе, и выделение наиболее важных из них.

Для каждой транзакции нужно знать:

1. Ожидаемую частоту выполнения.

2. Отношения (таблицы) и атрибуты, к которым потребуется иметь доступ при выполнении транзакций, а также тип этого доступа (выборка, вставка, обновление или удаление).

3. Атрибуты, используемые хотя бы в одном из предикатов (в языке SQL предикатами называются условия, задаваемые в предложениях WHERE)

4. Атрибуты, которые при выполнении запросов будут использоваться для соединения двух или больше отношений. Их нужно включать в структуры доступа.

5. Ограничения, установленные на время выполнения транзакций. (Например, может существовать требование, что некоторая транзакция всегда должна быть завершена в течение одной секунды)

6.

Выбор файловой структуры.

Цель-определение наиболее эффективного файлового представления каждой из таблиц Базы Данных.Рассмотрим возможности использования следующих типов файлов:

-последовательные файлы (heap);

-хешированные файлы(hash)

-индексно-последовательные файлы(ISAM);

-двоичные(бинарные) деревья(B+/- Tree);

 

Последовательные файлы.

ПСФ(или куча) является наиболее удобной структурой для хранения данных в следующих случаях:

1. Данные загружаются в таблицу крупными блоками.

2. Весь файл таблицы занимает несколько страниц.В этом случае время поиска любой записи будет невелико даже при последовательном просмотре всех строк таблицы.

3. При каждом обращении к таблице выбора подлежат все её кортежи (в любом порядке).

4. Таблица имеет дополнительные структуры поиска, например, индекс по ключу.

!!!! Файлы последовательной организации неэффективны в случаях, если доступ необходим только к некоторым кортежам таблицы!!!!

 

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

Применение хешированного файла в качестве структуры организации памяти для таблицы целесообразно в тех случаях, когда выбор кортежей осуществляется по точному совпадению поля, использованного для хеширования (например, ключа). Этот формат файлов не подходит для выбора данных: 1) по шаблону с символами подстановки; 2)по диапазону значений ключа; 3) по неполному значению ключа; 4) по значению атрибута, отличного от ключа перемешивания.

6.4.2.3. Индексно-последовательные файлы (ISAM).

Представляют собой более гибкую структуры, чем хешированные файлы. Они эффективны по выборке данных: 1) по точному (заданному) значению ключа; 2) по шаблону с символами подстановки; 3) по диапазону значений ключа; 4)по части ключа. Однако индекс файлов - ISAM –статичен и создаётся непосредственно при создании самого файла. 1) В результате производительность выборки данных из ISAM-файла уменьшается по мере внесения изменений в его денные. 2) Обновление данных файла также вызывает нарушение правильной последовательности ключей, поэтому выборка данных в порядке главного ключа замедляется.Эти проблемы решаются при использовании файлов со структурой двоичного дерева, имеющих динамически формируемый индекс.

!!!Если уровень обновления данных в таблице относительно низок, а её размеры относительно невелики, индексно-последовательная организация будет для неё оптимальным решением, поскольку она имеет на один уровень индекса ниже чем файлы со структурой двоичных деревьев.

 

Двоичные деревья.

По сравнению с хешированными файлами, двоичные деревья также представляют собой значительно более гибкие структуры хранения данных. Они позволяют выполнять выборку данных 1) по точному совпадению ключевого значения;2)по шаблону подстановки; 3) по диапазону значений; 4) по частично заданному ключу.

Индекс двоичных деревьев является динамическим, увеличивающимся по мере роста файла таблицы. Благодаря этому эффективность доступа в двоичных деревьев не снижается по мере обновления данных таблицы.

Файлы со структурой двоичных деревьев постоянно сохраняют упорядоченность доступа к ключу, даже при обновлении данных. Поэтому скорость выборки строк в порядке значений ключа в данном случае выше, чем у ISAM-файлов и является постоянной.

Однако, если информация в таблице не подвергается постоянным изменениям, то использование структуры бинарного дерева может оказаться менее эффективным по сравнению с индексно-последовательными файлами.

 

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

База данных во вторичном устройстве (магнитные диски) хранения организована в

виде одного или нескольких файлов.Каждый файл состоит из одного или нескольких записей, а каждая запись – из одного или нескольких полей. Как правило, запись соответствует некой сущности, поле-атрибуту. Пусть есть таблица СТУДЕНТ:

Рис.6.5.1 Таблица отношения “студент”.

Каждый кортеж отображается на некоторую запись в файле операционной системы, содержащей отношение “студент”. Каждое поле записи хранит один атрибут отношения. Когда пользователь для извлечения кортежа из БД (например, кортежа с н.з. 2000102) обращается к СУБД, СУБД отображает логическую запись на физическую запись, а затем помещает эту физическую запись в буфер СУБД в первичном устройстве (ОЗУ) с помощью подпрограмм (методов) методов доступа к файлам операционной системы.

Физическая запись (или группа записей - страница) является единицей обмена между ОЗУ и ВЗУ.Ещё раз подчеркиваю: Физическая запись обычно состоит из нескольких логических записей, и вместо термина “физическая запись” используется термин – “страница” или “блок”.

Например, представленные на рис.1 кортежи отношения “Студент” могут храниться на двух страницах ВЗУ так, как показано в таблице 2.

Табл.2

 

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

Определение 1: Организация файла - это физическое распределение данных файла по записям и страницам во вторичной памяти (ВЗУ).

Определение 2: Метод доступа – это действия, выполняемые при сохранении или извлечении записей из файла.

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

-последовательные файлы(ПСФ)(heap);

-хешированные файлы(ХФ)(hash);

-индексно-последовательные файлы (ИФ)(ISAM);

-двоичные деревья(разновидност и ИФ);

 

6.5.2. Последовательные файлы.

Последовательные файлы могут быть:

-неупорядоченные (НУПФ);

-упорядоченные(УПФ);

 

6.5.2.1. НУПФ – является простейшим типом структуры файла. Записи размещаются в файле в том порядке, в котором они добавляются. Каждая новая запись помещается на последнюю страницу файла, а если на последней странице ей не хватает места, то в файл добавляется новая страница. Это позволяет эффективно выполнять операцию вставки (добавляется запись в конец файла, НО поскольку файл подобного типа не обладает никаким упорядочением по отношению к значениям полей (атрибутов отношения), то для доступа к его записям потребуется выполнять линейный поиск (Метод доступа).

При линейном поиске последовательно считываются все страницы файла до тех пор, пока не будет найдена нужная запись. Операция извлечения данных из НУПФ, имеющих несколько страниц, выполняется относительно медленно, за исключением тех случаев, когда извлекаемые записи составляют существенную долю от всех записей файла.

Для удаления записи сначала потребуется извлечь нужную страницу, потом удалить нужную запись, а после этого снова сохранить эту страницу на диске. Причём пространство удалённых записей повторно не используется. Следовательно производительность работы системы с таким файлом будет постепенно уменьшаться. Это значит, что НУПФ требует периодической реорганизации, которая должна выполняться администратором БД.

НУПСФ лучше всех остальных файлов подходят для выполнения пакетной загрузки данных в таблицы, что делает ненужными действия по вычислению страницы, в которую следует поместить ту или иную запись.

 

6.5.2.2. УПСФ. Записи в таком файле сортируются по значению одного или нескольких полей и таким образом создаётся набор (файл) данных, упорядоченный по некоторому ключу. Поле, по которому сортируется файл называется полем упорядочения.(Например: номер зач.книжки – поле упорядочения)(Табл.2).

Если кортежи упорядочены по полю “ номер зач.книжки “, то при определённых условиях, при обработке запросов, можно применять бинарный поиск.Это для тех случаев, когда запрос содержит условия поиска с использованием “ номер зач.книжки “.

Пример SQL-запроса:

SELECT *

FROM Студент

WHERE [ Номер зачётной книжки ]=2000109

Для примера рассмотрим файл с кортежами частично представленными в таблице (рис.6.5.1.).

Рис. 6.5.2. Бинарный поиск в УПСФ.

Причём для простоты предположим, что в каждой странице находится по 1-ой записи. Тогда УПСФ будет выглядеть так, как показано на рис. 6.5.2.

В таком случае процедура бинарного поиска будет включать следующие этапы:

1. Извлечение средней страницы (4) для оставшейся на данный момент части файла. Проверка наличия искомой записи на этой странице (т.е. между 1-ой и последней на этой странице, если бы записей было бы на этой странице несколько). Если это так, то извлечение страниц прекращается.

2. Если значение ключевого поля в первой записи на этой странице больше, чем искомое значение, то это значит, что искомая запись, (если она существует) находится на одной из предыдущих страниц. Дальше приведённая выше процедура повторится для левой половины обрабатываемой части файла. Если значение ключевого поля (в данном случае она же и первая) записи страницы меньше, чем искомое значение, то искомая запись находится на правой половине обрабатываемой части файла (как показано на рис.6.5.2.).

В нашем случае средней страницей всего файла является страница 4, но запись на этой странице не является искомой (2000109).Значение ключевого поля на странице 3 меньше требуемого значения, поэтому вся левая половина файла и исключается из области поиска. Теперь следует извлечь среднюю страницу из правой части файла, т.е. страницу 6 (2000112). На этот раз значение ключевого поля больше искомого значения (2000109), поэтому исключается из текущей области поиска её правая половина. После извлечения правой страницы из оставшейся части файла (стр.5), убеждаемся, что именно она является искомой.

В общем случае бинарный поиск эффективнее линейного.Однако!!! Операции вставки и удаления записей в УПСФ усложняются необходимостью поддерживать установленный порядок записей.

Для вставки новой записи нужно: 1) найти её месторасположение в заданном упорядочении, а потом 2)найти пространство для вставки.!!! Если на нужной странице достаточно места для размещения, то тогда потребуется лишь переупорядочить только эту страницу, после чего вывести её на диск.

Если же свободного места недостаточно, то в таком случае потребуется переместить одну (или несколько) записей в следующую страницу. Аналогично в следующей странице может не оказаться свободного места, и из неё также потребуется переместить некоторые записи в следующую страницу и т.д.

Таким образом, вставка записи в начало большого файла(УПСФ) может оказаться длительной процедурой.

Для удаления записи нужно:

1) Найти её месторасположение;

2) Удалить требуемую запись;

3) Реорганизовать записи, чтобы удалить пустующие места.

В связи с вышеуказанным УПСФ довольно редко используется для хранения информации БД, за исключением тех случаев, когда для файла организуется первичный индекс (см. параграф 6.5.4.).

 

Хешированные файлы (ХФ).

В ХФ записи необязательно должны записываться в файл последовательно. Вместо этого для вычисления адреса страницы, в которой должна находиться та или иная запись, используется Хэш-функция (hash-function), аргументами которой являются значения одного (или нескольких) полей этой записи. Подобное поле называется полем перемешивания, а, если это поле также является ключевым полем файла, то оно называется ХЭШ-ключом (hash key). Записи в ХФ произвольным образом распределяются по всему доступному для файла пространству. По этой причине ХФ иногда называют файлами с произвольной структурой (random file) или файлами прямого доступа (direct file). Хэш-функция выбирается таким образом, чтобы записи внутри файла были распределены максимально равномерно. Один из методов построения Хэш-функции (свёртка) основан на выполнении определённых арифметических операций над различными частями (или над всеми) поля перемешивания. Например, в качестве Хэш-функции используется функция MOD, на вход которой передаётся значение поля (ХЭШ-ключа). Функция делит полученные значения на некоторое предопределённое число, после чего остаток от деления используется в качестве адреса.

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

!!!Каждый вычисляемый Хеш-функцией адрес соответствует некоторой странице с несколькими ячейками (слотами), предназначенными для отдельных записей. В пределах одной страницы записи размещаются в слотах (ячейках) в порядке поступления.

Тот случай, когда один и тот же адрес генерируется для 2-ух и более записей, называется конфликтом (collision), а подобные записи – синонимами.

В этом случае новую запись необходимо вставить в другое место, т.к. место с вычисленным для него ХЭШ-адресом уже занято. Разрешение конфликтов усложняет работу с ХФ и снижает общую производительность системы.

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

-открытую адресацию;

-несвязанную область переполнения;

-связанную область переполнения;

-многократное хеширование;

(Здесь можно раскрыть один из методов Хеширования или сослаться на параграф 6.3.2.)

 

Индексные файлы.

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

Индекс в БД аналогичен предметному указателю, приведенному в предметной книге. Это структура, связанная с файлом данных (основной файл) и предназначенная для поиска информации по тому же принципу, что и предметный указатель. Т.е. имеют место два файла: 1) Основной с данными; 2) Индексный;

Индекс позволяет избежать последовательного сканирования файла данных в поисках нужных данных (нужного объекта).Объект – это несколько записей данных. Как и предметный указатель индекс БД упорядочен, и каждый элемент индекса содержит название искомого объекта (записи в файле данных), а также один или несколько указателей на место его расположения.

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

Значение ключа

Номер записи

 

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

Ещё раз подчёркиваю.

1. Файл, содержащий логические записи (экземпляры) соответствующие кортежам отношения, называются файлом данных (или основным файлом)(ФД).

2. Файл, содержащий индексные записи называют индексом (или индексным файлом, или таблицей индексов) (ИФ).

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

Определение 1: Если файл данных имеет последовательное упорядочение, а поле индексирования является ключевым полем этого файла данных, то есть гарантировано содержит уникальные значения для всех записей в ФД, то такой индекс называется первичным индексом.

Определение 2: Индекс, который определён на поле файла данных, отличном от ключевого поля (по которому ФД упорядочен), называется вторичным индексом.

Файл может иметь один первичный индекс (или индекс кластеризации) и несколько вторичных индексов.

<<Если поле индексирования, являющееся одновременно полем упорядочивания, не является ключевым полем файла и по этой причине одному индексному значению может соответствовать несколько записей файла, то такой индекс называется индексом кластеризации.