Основные принципы организации баз данных

Размещено на http://www.allbest.ru/

Введение

доступ индексирование структуризация многоуровневый

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

Существуют две основные предпосылки создания таких систем:

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

2. Возможность собирать, хранить и обрабатывать большое количество данных о реальных объектах и явлениях, то есть оснащение этих систем "памятью". Массив данных общего пользования в подобных системах называется базой данных. Концепция баз данных стала определяющим фактором при создании эффективных автоматизированных СОД.

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

При проектировании программ выясняются запросы и пожелания клиента и определяется возможный подход к решению задачи. Задача анализируется. На основе этого анализа реализуется конкретная модель в конкретной программной среде. Результаты каждого этапа проектирования используются в качестве исходного материала следующего этапа.
Анализируется текущая организация предприятия, выделяются проблемы для решения, определяются объекты отношения между ними, составляется «эскиз» текущей организации предприятия, разрабатывается модель с учетом конкретных условий ее функционирования. База данных ориентирована на определенную предметную область и организована на основе некоторого подмножества данных. Возможности баз данных полезны в областях, связанных с долговременным управлением информацией, таких как электронные библиотеки и хранилища данных.

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

1. Механизмы размещения данных и доступа к данным

Механизмы среды хранения БД служат для управления двумя группами ресурсов - ресурсами хранимых данных и ресурсами пространства памяти. В задачу этого механизма входит отображение структуры хранимых данных в пространство памяти, позволяющее эффективно использовать память и определить место размещения данных при запоминании и при поиске данных.

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

Механизмы среды хранения выполняют следующие операции:

1. При запоминании нового объекта:

· определение места размещения нового объекта "физической" БД в пространстве памяти;

· выделение необходимого ресурса памяти;

· запоминание этого объекта;

· формирование связей с другими объектами.

2. При поиске объекта:

· поиск места размещения объекта в пространстве памяти по заданным атрибутам или "адресу";

· выборка объектов для обработки.

3. При удалении объекта:

· удаление объекта с освобождением памяти (физическое удаление) или без освобождения (логическое удаление);

· разрушение связей с другими объектами.

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

Страницы представляются в среде ОС блоками внешней памяти, кластерами или секторами, доступ к которым осуществляется за одно обращение. В системах, которые позволяют управлять размером страницы, приходится искать компромисс между производительностью системы и требуемым объёмом оперативной памяти.

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

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

Хранимая запись состоит из двух частей:

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

2. Информационная часть. Содержит значения элементов данных.

Элементы хранимой записи могут иметь фиксированную или переменную длину. При этом обычно элементы фиксированной длины хранятся в начале записи и размещаются в памяти с заранее определённых позиций, а за ними размещаются элементы переменной длины. Хранение элементов переменной длины осуществляется одним из двух способов: размещение через разделитель или хранение размера элемента данных. Наличие полей переменной длины позволяет не хранить незначащие символы и тем существенно снижает затраты памяти на хранение данных; но при этом увеличивается время на извлечение элементов записи.

Каждой записи БД система присваивает внутренний идентификатор, называемый (по стандарту CODASYL) ключом базы данных (КБД). Значение КБД формируется системой при размещении записи и содержит информацию, позволяющую однозначно определить место размещения записи (её адрес). В качестве КБД может выступать, например, последовательный номер записи в файле или совокупность адреса страницы и смещения от начала страницы.

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

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

· Доступ по ключу базы данных (КБД). КБД определяет местоположение записи в памяти ЭВМ. Зная его, система может извлечь нужную запись за одно обращение к памяти.

· Доступ по структуре. Эта разновидность доступа применяется для групповых отношений и позволяет перейти к предыдущему или следующему экземпляру группового отношения, к экземпляру-владельцу группового отношения или к списку подчинённых экземпляров.

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

2. Индексирование данных. виды индексов. составные и многоуровневые индексы

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

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

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

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

В том случае, если каждому значению индекса соответствует уникальное значение ключа, такой индекс называется первичным. Если же индекс строится по ключу, допускающему дубликаты значений, такой индекс называется вторичным. Для каждой БД можно одновременно поддерживать несколько первичных и вторичных индексов, что также относится к достоинствам индексирования.

Различают одиночные индексы и составные. Составной индекс включает два или более столбца одной таблицы (рис. 1). Последовательность вхождения столбцов в индекс определяется при создании индекса.

Таблица

Индекс

2.1 Способы организации индексов

Существует множество способов организации индексов:

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

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

3. Одноуровневый индекс представляет собой линейную совокупность значений одного или нескольких полей записи. На практике он используется только в простейших случаях, когда количество индексируемых записей невелико. В более сложных случаях индекс занимает много памяти (иногда - несколько страниц), и возникает задача минимизации доступа к нему. Тогда индекс разбивается на несколько иерархических уровней, что позволяет ускорить поиск требуемого значения. Особенно эффективной является организация многоуровневых индексов в виде сбалансированных деревьев (balance trees, B-деревьев), в которых все пути от корня к листьям имеют одинаковую длину.

2.2 Многоуровневые индексы на основе В-дерева

B-дерево строится динамически по мере заполнения базы данными. Оно растёт вверх, и корневая вершина может меняться. Параметрами B-дерева являются порядок n и количество уровней. Порядок - это количество ссылок из вершины i-го уровня на вершины (i+1)-го уровня. Каждое B-дерево должно удовлетворять следующим условиям:

1. Каждая вершина может содержать n адресных ссылок и (n-1) ключей. Ссылка влево от ключа обеспечивает переход к вершине дерева с меньшими по значению ключами, а вправо - к вершине с большими ключами.

2. Любая неконечная вершина имеет не менее n/2 подчинённых вершин.

3. Если неконечная вершина содержит k (kЈ n) ключей, то ей подчинена (k+1) вершина на следующем уровне иерархии.

4. Все конечные вершины расположены на одном уровне.

Алгоритм формирования B-дерева порядка n предполагает, что сначала заполняется корневая вершина. Затем при появлении новой записи корневая вершина делится, образуются подчинённые ей вершины. При запоминании каждой новой записи поиск места для неё начинается с корневой вершины. Если в существующем на данный момент B-дереве нет места для размещения нового ключа, происходит сдвиг ключей вправо или влево, если это невозможно - осуществляется перестройка дерева. Пример построения B-дерева порядка 3 приведён на рис. 2

Рис. 2 Пример построения B-дерева порядка 3

Индексирование в виде B-дерева используется, например, в СУБД Oracle (рис. 3).

Рис. 3 Пример индексного блока СУБД Oracle

Организация индексов в СУБД Oracle несколько отличается от рассмотренной выше классической организации B-дерева, но принцип остаётся тот же: одинаковое количество уровней на любом пути и автоматическая сбалансированность. Верхние блоки содержат данные индекса, которые ссылаются на блоки индекса нижних уровней. Самый нижний n-й уровень содержит блоки индекса (блоки-листья), которые содержат непосредственно данные индекса (ключи) и соответствующие идентификаторы строк ROWID (row identification, КБД), используемые для нахождения самих строк. Блоки-листья связаны между собой указателями.

Поиск по ключу осуществляется следующим образом. Блок верхнего уровня (уровень 1) содержит некоторое значение X и указатели на верхнюю и нижнюю части индекса. Если значение искомого ключа больше X, то происходит переход к верхней части индекса (по левому указателю), иначе - к нижней части. Блоки второго и последующих уровней (кроме двух последних) хранят начальное X0 и конечное значения Xк ключа, а также три указателя. Если значение искомого ключа больше, чем X0, то происходит обращение по левому указателю; если оно меньше, чем Xк, то происходит обращение по правому указателю; если оно попадает в диапазон X0ёXк - по среднему указателю.

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

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

Индекс в виде B-дерева автоматически поддерживается в сбалансированном виде. Это означает, что при переполнении какого-либо из блоков индекса происходит перераспределение значений ключей индекса (без физического перемещения записей данных). Например, если при добавлении новой записи с ключом "Горин" возникает переполнение соответствующего блока индекса (рис. 3), система может перераспределить значения ключей так, как показано на рис. 4.

Если все блоки-листья индекса заполнены приблизительно на три четверти, то при добавлении новой записи осуществляется полная перестройка B-дерева путём введения дополнительного уровня. Всё это скрыто от пользователя и происходит автоматически.

Рис. 4. Пример перераспределения данных индексного блока СУБД Oracle

Структура B-дерева имеет следующие преимущества:

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

· B-дерево автоматически поддерживается в сбалансированном виде.

· B-деревья обеспечивают хорошую производительность для широкого спектра запросов, включая поиск по конкретному значению и в заданном интервале.

· Добавление, обновление и удаление строк выполняется достаточно эффективно.

· Производительность B-дерева одинаково хороша для маленьких и больших таблиц, и не меняется существенно при росте таблицы.

2.3 Использование индексов

В системах, поддерживающих язык SQL, индекс создаётся командой CREATE INDEX. Индексы повышают производительность запросов, которые выбирают относительно небольшое число строк из таблицы. Для определения целесообразности создания индекса нужно проанализировать запросы, обращённые к таблице, и распределение данных в индексируемых столбцах.

Система может воспользоваться индексом по определённому полю, если в запросе на значение этого поля накладывается условие, например:

SELECT * FROM emp WHERE name = 'Даль';

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

Обращение к составному индексу возможно только в том случае, если в условиях выбора участвуют столбцы, представляющие собой лидирующую часть составного индекса. Например, если индекс строится по столбцам (X, Y, Z), то обращение к индексу будет происходить в тех случаях, когда в условии запроса участвуют столбцы XYZ, XY или X.

При создании индекса большое значение имеет понятие селективности. Селективность определяется процентом строк, имеющих одинаковое значение индексируемого столбца: чем выше этот процент, тем меньше селективность.

Выбор индексируемых столбцов определяется следующими соображениями:

· В первую очередь выбираются столбцы, которые часто встречаются в критериях поиска.

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

· Нецелесообразно индексировать столбцы с низкой селективностью. Если селективность столбца низкая, то индексирование проводится только в том случае, если выборка чаще производится по редко встречающимся значениям.

· Не индексируются столбцы, которые часто обновляются, т.к. команды обновления ведут к потере времени на обновление индекса.

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

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

· Несколько столбцов с низкой селективностью в комбинации с друг с другом могут дать гораздо более высокую селективность.

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

Примечание: многие СУБД автоматически строят индекс по первичному ключу и по уникальным столбцам.

Список литературы

1. Дейт К. Введение в системы баз данных: Пер. с англ. - 6-е изд. - Киев: Диалектика, 1998. - 784 с.

2. Ревунков Г.И., Самохвалов Э.Н., Чистов В.В. Базы и банки данных и знаний: Учеб. для вузов / Под ред. Четверикова В.Н. - М.: Высш. шк., 1999. - 367 с.

3. Тиори Т., Фрай Дж. Проектирование структур баз данных: В 2-х кн. / Пер. с англ. - М.: Мир, 2005.

4. Грабер М. Введение в SQL. - М.: 1998.

5. Изучение языка SQL: Метод. указания к лабораторным работам по курсу "Базы данных" / Московский государственный институт электроники и математики; Сост.: И. П. Карпова. М., 2008. - 32 с.

Размещено на Allbest.ru