Атомарность значений атрибутов

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

 

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

В реляционной БД существуют следующие типы отношений:

- Один ко многим. Различают 2 разновидности таких отношений: с жестким требованием и где жесткое требование отсутствует. Жесткое требование – когда всякой записи в родительской таблице должна соответствовать запись в дочерней.

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

- Один к одному. Имеет место, когда одной записи в родительской таблице соответствует одна запись в дочерней таблице. Это отношение используется, чтобы не загромождать таблицы БД второстепенной информацией.

Реляционный БД не поддерживают отношения многие ко многим, но можно заменить связь на одну или несколько связей один ко многим.

К реляционным базам предъявляется требование нормализации. Целью нормализации является устранение избыточности данных и приведение БД к третьей нормальной форме.

1НФ: Требует, чтобы каждое поле таблицы БД было неделимым и не содержало повторяющихся групп. Неделимость поля означает, что содержащиеся в нем данные не должны делиться на более мелкие (например, ФИО). Повторяющиеся поля – это поля, содержащие одинаковые по смыслу значения (товар1, товар2).

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

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

Так же к реляционным БД применяется требование целостности.

Целостность сущностей – каждая запись каждой таблицы д.б. отличимой от каждой записи этой же таблицы.

Целостность ссылок – для каждого значения внешнего ключа таблицы должна находится запись с таким же значением первичного ключа другой таблицы, либо значение внешнего ключа д.б. полностью неопределенным (Null).

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

- Запрещается производить удаление записи, на которую существует ссылка. Сначала нужно удалить ссылающиеся записи или изменить значение внешнего ключа.

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

- Каскадное удаление – при удалении записи из таблицы, на которую ведется ссылка, автоматически удаляются все ссылающие записи.

 

Достоинства:

Широкое распространение РМД объясняется в первую очередь простотой представления и формирования БД, универсальностью и удобством обработки данных, которая осуществляется с помощью декларативного языка запросов SQL (Structured Query Language).

• Структурная независимость – изменения в структуре БД не влияют на доступ к данным;
• Концептуальная простота – возможность целиком сосредоточиться на логическом представлении данных;
• Простота проектирования, реализации, управления и использования – стало проще проектировать БД и управлять ее содержимым;
• Нерегламентированные запросы – SQL- стандартный язык запросов,язык четвертого поколения, дает возможность пользователям определить что необходимо сделать без указания того как надо сделать;
• Мощная система управления БД – решает сложные задачи.

· Обработка данных в отношениях осуществляется с помощью операций реляционной алгебры.

 

Недостатки:

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

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

В РМД нет понятий режима включения и класс членства, поэтому набор средств описания ограничений целостности очень мал.

• Существенные требования к оборудованию и системному программному обеспечению – РСУБД скрывает от пользователя всю сложность системы и требует значительных системных и программных ресурсов
• Возможность скороспелых проектов и реализаций – можно легко создать запросы и отчеты, не утруждая себя тщательным проектированием БД, по мере роста БД пробелы в проектировании могут привести к аномалиям в данных.

Существует широкий класс приложений, для которых технология реляционных систем БД не является вполне удовлетворительной:); технология программирования; системы, основанные на знаниях, и мультимедийные системы; системы автоматизации проектирования (САПР); геоинформационные системы (ГИС); издательские системы; системы дистанционного обучения; системы электронной коммерции и др. Это прежде всего связано с примитивностью структур данных, лежащих в основе реляционной модели данных. Плоские нормализованные отношения универсальны и теоретически достаточны для представления данных любой предметной области. Однако в нетрадиционных приложениях в базе данных появляются сотни, если не тысячи таблиц, над которыми постоянно выполняются дорогостоящие операции соединения, необходимые для воссоздания сложных структур данных, присущих предметной области.

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

 

4. Язык структурированных запросов SQL.

SQL был разработан в 1974 году фирмой IBM для экспериментальной реляционной СУБД System R. После появления на рынке двух пионерских СУБД этой фирмы - SQL/DS (1981 год) и DB2 (1983 год) - он приобрел статус стандарта де-факто для профессиональных реляционных СУБД. В 1989 году SQL стал международным стандартом языка баз данных, а в 1992 году вышла вторая версия этого стандарта.

В данной главе рассматриваются элементы языка SQL (Structured Query Language). Первый международный стандарт SQL был принят в 1989 г. (SQL/89 или SQL1). Стандарт был принят ANSI (Американский Национальный Институт Стандартов) и ISO (международная организация по стандартизации). Следующая версия стандарта языка SQL принята в 1992 г. (Официальное название стандарта - Международный стандарт языка баз данных SQL (1992) (International Standart Database Language SQL), неофициальное название - SQL/92, или SQL-92, или SQL2). Документ, описывающий стандарт, содержит более 600 страниц. Рассмотрим только некоторые основные понятия языка. Далее был разработан SQL/99 или SQL3, принятый стандарт объектно-реляционного расширения SQL. Подмножества этого стандарта уже реализованы в коммерческих продуктах, включая Oracle V8 компании Oracle и DB2 корпорации IBM.

Язык структурирован­ных запросов SQL предназначен для доступа к информации и управления реляционной БД. Он является общим при работе c различными базами данных, такими как Oracle, Microsoft SQL Server, Informix, DB2, Access, MySQL.

Все СУБД, претендующие на название «реляционные», реализуют тот или иной диалект SQL: SQL*Plus корпорации Oracle; Transact-SQL для СУБД Microsoft SQL Server и др. В диалектах язык может быть дополнен операторами процедурных языков программирования.

В настоящее время, ни одна система не реализует стандарт SQL в полном объеме. Кроме того, во всех диалектах языка имеются возможности, не являющиеся стандартными. Таким образом, можно сказать, что каждый диалект – это надмножество некоторого подмножества стандарта SQL.

Язык SQL определяет:

· операторы языка, называемые командами языка SQL;

· типы данных;

· набор встроенных функций.

Выделяют две разновидности языка SQL интерактивный и вложенный. Интерактивный SQL позволяет конечному пользователю в интерактивном режиме выполнять SQL-операторы. Все СУБД предоставляют инструментальные средства для работы с базой данных в интерактивном режиме. Вложенный SQL позволяет включать операторы SQL в код программы на другом языке программирования, например, С++.

В интерактивном языке SQL можно выделить три раздела:

1. DDL (Data Definition Language) – это язык определения данных, который включает операторы, управляющие объектами базы данных. К последним относятся таблицы, индексы, представления. Для каждой конкретной базы данных существует свой набор объектов базы данных, который может значительно расширять набор объектов, предусмотренный стандартом.

- CREATE DATABASE – создать базы данных;

- DROP DATABASE – удалить базу данных;

- CREATE TABLE – создать таблицу;

- ALTER TABLE – изменить таблицу;

- DROP TABLE – удалить таблицу;

- CREATE VIEW – создать представление;

- DROP VIEW – удалить представление.

2. DML (Data Manipulation Language) - язык манипулирования данными:

- SELECT – отобрать строки из таблиц;

- INSERT – добавить строки в таблицу;

- UPDATE – изменить строки в таблице;

- DELETE – удалить строки в таблице;

3. DCD (Data Control Language) – язык управления данными состоит из операторов контроля данных, защиты и управления данными:

- COMMIT – зафиксировать внесенные изменения;

- ROLLBACK – откатить внесенные изменения.

- GRANT – предоставить привилегии пользователю или приложению на манипулирование объектами;

- REVOKE – отменить привилегии пользователя или приложения.

Операторы SQL

· Создание таблиц. Таблицы (их структура) создаются командой CREATE TABLE (выражение).

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

CREATE TABLE Продавцы

(пном integer NOT NULL UNIQUE PRIMARY KEY,

пимя char (10),

город char (10) DEFAULT 'Москва',

комм decimal CHECK (комм < 1));

Пример Создать таблицу для сохранения данных о заказчиках:

CREATE TABLE Заказчики (зном integer NOT NULL PRIMARY KEY, зимя char (10) NOT NULL, город char (10) оценка integer, пном integer NOT NULL, UNIQUE (зном, пном));

Команда CREATE TABLE определяет имя таблицы, набор имен столбцов, указанных в определенном порядке, типы данных и размеры столбцов, ограничения столбцов, ограничения таблицы. В SQL возможно задание следующих типов данных: integer, character, numeric, decimal, smallint, float, real, double, precision, long, varchar, date, time. Ограничение столбца вставляется в конец имени столбца после типа данных и перед запятой. Ограничение таблицы помещается в конец описания таблицы после последнего имени столбца, но перед заключительной круглой скобкой.

Основные типы ограничений:

- Исключение пустых или неопределенных (NULL) указателей введением команды NOT NULL.

- Уникальность данных UNIQUE. Это ограничение отклонит любую попытку ввода в это поле значения, которое уже представлено в другой строке. Это ограничение может применяться только к полям, которые были объявлены как непустые (NOT NULL).

- Первичный Ключ PRIMARY KEY. Первичные ключи не могут иметь значений NULL. Это означает, что, подобно полям в ограничении UNIQUE, любое поле, используемое в ограничении PRIMARY KEY, должно уже быть объявлено NOT NULL.

- Ограничения на значения полей CHEC необходимо, чтобы предотвратить ошибку неправильного ввода в поле.

- Установка значений по умолчанию DEFAULT.

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

· Удаление таблиц осуществляется (его владельцем) командой DROP Table <имя >.

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

· Создание представлений. Можно создавать представление (View) – таблицы, содержимое которых берется или выводится из других таблиц. Представление создается командой CREATE VIEW.

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

CREATE VIEW Москва1

AS SELECT пном, пимя

FROM Продавцы where город=’Москва’;

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

Имеются некоторые виды запросов, которые недопустимы в определениях модифицируемых представлений: одиночное представление должно основываться на одиночном запросе. Объединение (UNION), агрегатные функции, DISTINCT в определении, вычисляемые поля не разрешаются в работе с представлениями. Упорядочение (ORDER BY) никогда не используется в определении представлений.

· Удаление представлений осуществляется (его владельцем) командой DROP VIEW <имя >.

· Заполнение БД данными. Значения могут быть помещены в таблицу и удалены из нее командами языка DML INSERT (ВСТАВИТЬ), DELETE (УДАЛИТЬ).

Пример Ввести новую строку в таблицу Продавцы, используя следующую команду:

INSERT INTO Продавцы VALUES (1009, 'Галкин', 'Тверь', 0.12);

· Исключение строк проводится командой DELETE. Она может удалять только введенные строки, а не отдельные значения полей, так что параметр поля является необязательным или недоступным.

Пример У далить все содержание таблицы Продавцов:

DELETE FROM Продавцы;

· Изменение данных выполняется командой UPDATE.

Пример После ухода продавца Строкова на пенсию, переназначить его номер новому продавцу Норову:

UPDATE Продавцы SET пимя = 'Норов', город = 'Орел', комм =.10 WHERE пном = 1001;

Эта команда передаст новому продавцу Норову, всех текущих заказчиков бывшего продавца Строкова и их заказы.

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

Привилегии – это права, которые определяют, может ли указанный пользователь выполнить данную команду.

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

Имеется несколько типов привилегий, соответствующих нескольким типам операций. Привилегии даются и отменяются двумя командами SQL: GRANT (ДОПУСК) и REVOKE (ОТМЕНА).

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

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

Привилегии относятся к командам SELECT, INSERT, UPDATE, DELETE, ALL (все), REFERENCES (определение внешнего ключа, который использует один или более столбцов этой таблицы как родительский ключ).

Пример Пользователь И лья создал таблицу Заказчики и собирается позволить пользователю Петр выполнить запрос к ней:

GRANT SELECT ON Заказчики TO Петр;

Петр может выполнить запросы к таблице Заказчик и, но не может предоставить право SELECT другому пользователю, так как таблица принадлежит Илье.

Пример Задать групповые привилегии GRANT SELECT ON Заказы TO PUBLIC;

Иногда создателю таблицы необходимо, чтобы другие пользователи могли получить привилегии в его таблице. Обычно это делается в системах, где один человек или более создает несколько (или все) базовые таблицы в БД, а затем передает ответственность за них тем, кто будет фактически с ними работать. SQL позволяет делать это с помощью предложения WITH GRANT OPTION.

Пример Если Ольга хотела бы, чтобы Андрей имел право предоставлять привилегию SELECT в таблице Заказчики другим пользователям, она дала бы ему привилегию SELECT с использованием предложения WITH GRANT OPTION: GRANT SELECT ON Заказчики TO Андрей WITH GRANT OPTION;После выполнения этой команды Андрей получил право передавать привилегию SELECT третьим лицам.

Пример Привилегии отменяются командой REVOKE

REVOKE INSERT, DELETE ON Заказчики FROM Степан;

Возможно задание (или отмена) привилегий с помощью рассмотренных ранее представлений.

5. Технология индексирования данных.

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

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

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

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

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

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

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

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

Зачем создавать индекс для столбца или группы столбцов? Это важный вопрос, и мы на него можем ответить следующим образом:

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

Хорошими кандидатами для индексирования обычно являются:

• столбцы первичного ключа. По определению, столбцы первичного ключа должны иметь уникальный индекс;
• столбцы внешнего ключа. Они дают хороший индекс по двум причинам. Во-первых, они часто применяются для выполнения соединений с родительскими таблицами. Во-вторых, они могут быть использованы СУБД при поддержке ссылочной целостности в операциях удаления строк родительской и дочерних таблиц;
• любые столбцы, которые содержат уникальные значения;
• столбцы, запросы или соединения по которым захватывают от 5 до 10% строк таблицы;
• столбцы, которые часто входят как аргументы в функции агрегирования;
• столбцы, которые часто используются для проверки правильности ввода данных в программах ввода/редактирования.

Факторы, влияющие на низкую эффективность индексов:

• Таблицы маленького размера. Одним из общих эмпирических правил является правило "не создавать индексы для таблиц размером менее пяти физических страниц". Для таких страниц стоимость поддержки индекса больше, чем стоимость сканирования всей таблицы. Конечно, уникальный индекс требуется для первичного ключа и поддержки ссылочной целостности.
• Интенсивные обновления таблиц в пакетном режиме. Такие таблицы обычно имеют проблемы с переполнением индекса при интенсивной модификации таблицы. Если индекс необходим для такой таблицы, то целесообразнее его удалять перед обновлением и создавать после него.

Плохими кандидатами для индексирования обычно являются:

• столбец имеет много неопределенных значений (NULL-значения). В этом случае неопределенные значения могут дать значительную асимметрию распределения значений столбца, несмотря на то, что кардинальность колонки будет подходящей для использования индекса;
• столбцы с часто изменяемыми значениями. Индекс для таких столбцов часто обновляется, что приводит к его переполнению, поскольку в большинстве алгоритмов обработки B-Tree индексов физическая страница индекса становится доступной для распределения данных только после того, как из нее будут удалена последняя запись. В частности, это обстоятельство приводит к созданию дополнительных страниц индекса и уровней индекса;
• значительная длина индексных колонок. Составной индекс или индекс для одного столбца с длиной более чем 50 байт будет приводить к росту числа уровней индекса, несмотря на то, что строк в таблице может быть немного. Большое число уровней снижает производительность операций выборки строк через индекс, т.к. каждый уровень требует по крайней мере одной операции ввода/вывода.

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

• Должно быть в наличии ограничение PRIMARY KEY.
• Не следует создавать для таблицы несколько составных индексов, содержащих одни и те же колонки, но в другом порядке.

 

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

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

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

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

На практике чаще всего используются два метода поиска:
последовательный
бинарный (основан на делении интервала поиска пополам).

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

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

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

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

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

Индекс на основе сбалансированной иерархической структуры, или индекс B-Tree (Balanced Tree structured object), используется как индекс по умолчанию в СУБД Oracle. Эта структура напоминает дерево (если смотреть снизу вверх), в котором сначала считывается самый верхний блок - корневой узел (root), затем блок на следующем уровне - блок-ветвь (branch) и так до тех пор, пока не будет извлечен блок-лист (leaf) с идентификатором строки. Значения ключа сохраняются в индексе (рис.1). Такая структура позволяет сократить до минимума число операций ввода/вывода. Для получения идентификатора строки обычно требуется одно посещение блок-листа, т.е. физической страницы базы данных, отведенной под индекс.

Рис.1. Концептуальная организация B-Tree индекса

Индекс B-Tree характеризуется количеством уровней в индексе (height). Чем меньше уровней, тем выше производительность.

Индекс B-Tree - это физический объект реляционной базы данных, организованный по принципу сбалансированной иерархической структуры и обладающий набором свойств. Значения колонок NULL не индексируются. Если для таких колонок строится индекс, то СУБД будет отказываться примерять его в некоторых операциях, например ORDER BY.

Блоки В – дерева организованы в виде древовидного графа. В – дерево является сбалансированным т.к. длины всех путей от корневой вершины до любой из вершин листьев равны. Типичное В – дерево содержит три уровня: корневую вершину, промежуточную вершину и листья, хотя способно включать и промежуточное количество уровней. Каждый блок В – дерева обладает пространством достаточным для размещения n значений ключа и n+1 указателей.

В В – дереве ключевые значения, указанные в вершинах листьях, являются копиями ключей записей файла данных. Ключи распределены по вершинам листьям слева направо в порядке возрастания значений.

 

 

 

 

 

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

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