Принципы индексации данных

Лабораторная работа 9 — Разработка и анализ индексов

Варианты заданий

Содержание отчета

Содержание отчета:

— тексты триггеров;

— SQL операторы и наборы данных, иллюстрирующие работу триггеров.

Варианты заданий приведены в ПРИЛОЖЕНИИ.

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

В основе принципов индексации лежит тот факт, что в отсортированных массивах данных возможен двоичный поиск, который работает существенно быстрее, чем линейный. Предположим, что в таблице Студент 1024 записи, тогда линейный поиск заданного студента потребует в среднем выполнения 512 операций сравнения (сложность линейного поиска N/2). Если данные отсортированы, возможен двоичный поиск: берется средний элемент, сравнивается с ключом поиска, если ключ меньше — процедура поиска продолжается в верхней половине массива, иначе — в нижней. В случае двоичного поиска для нахождения записи о заданном студенте по уникальному ключу потребуется всего 10 операций сравнения (сложность двоичного поиска log₂(N)).

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

(i) СУБД хранят данные таблиц в виде цепочек страниц, типовые размеры которых соответствуют 2K, 4K, 8K или 16K (размер страницы задается при создании БД);

(ii) размер БД, как правило, не позволяет разместить ее в полном объеме в оперативной памяти;

(iii) обмен с внешней памятью (чаще всего БД располагается на жестком диске) является гораздо более медленной операцией, чем чтение/запись оперативной;

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

Решение об использовании индексов принимает оптимизатор запросов СУБД, таким образом:

(i) задача разработчика БД — предложить систему индексов исходя из потенциального множества запросов, которые к ней будут выполняться;

(ii) задача оптимизатора — построить как можно больше возможных планов выполнения запросов и выбрать план с минимальной стоимостью выполнения.

Создание индекса в простейшем случае обеспечивает оператор:

create index <имя индекса>

on <имя таблицы> (<имя столбца 1> [, <имя столбца 2> [, … ] ])

Например, если в таблице Студент используется поиск по ФИО, ускорить его поможет индекс:

create index Студент_ФИО

on Студент (ФИО)

go

Дата добавления: 2015-05-09