Мир InterBase. Архитектура, администрирование и разработка приложений баз данных в InterBase/FireBird/Yaffil - [14]

Индексы

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

Что же представляет собой индекс? Индекс - это упорядоченный указатель на записи в таблице. Указатель означает, что индекс содержит значения одного или нескольких полей в таблице и адреса страниц данных, на которых располагаются эти значения (про страницы данных см. главу "Структура базы данных InterBase") (ч 4). Другими словами, индекс состоит из пар значений "значение поля" - "физическое расположение этого поля". Таким образом, по значению поля (или полей), входящего в индекс, при помощи индекса можно быстро найти то место в таблице, где располагается запись, содержащая это значение.

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

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

Для чего нужны индексы?

Единственное, чему способствуют индексы, - это ускорению поиска записи по ее индексированному полю (индексированное - значит входящее в индекс).

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

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

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

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

Как устроены индексы

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

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

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

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

Применение индексов

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

* Ускорение выполнения запросов. Индексы создаются для полей, которые используются в условиях поиска SQL-запросов.

* Обеспечение уникальности значений в полях; Ограничение первичного ключа (о которых рассказывалось в главе "Таблицы. Первичные ключи") требует, чтобы во всей таблице не нашлось двух одинаковых значений полей, входящих в первичный ключ. Чтобы выполнить это условие, необходимо при каждой вставке новой записи производить поиск такого же значения, которые будет вставлено. Для поиска записи используется особая разновидность индекса - уникальный индекс (см. ниже).