Индексы
Концепция, положенная в основу индексов, проста и наглядна и является одной из важнейших основ проектирования баз данных. На основе индексов базируются многие основополагающие объекты базы данных, к тому же правильное использование индексов является ключом к улучшению производительности приложений баз данных.
Что же представляет собой индекс? Индекс - это упорядоченный указатель на записи в таблице. Указатель означает, что индекс содержит значения одного или нескольких полей в таблице и адреса страниц данных, на которых располагаются эти значения (про страницы данных см. главу "Структура базы данных InterBase") (ч 4). Другими словами, индекс состоит из пар значений "значение поля" - "физическое расположение этого поля". Таким образом, по значению поля (или полей), входящего в индекс, при помощи индекса можно быстро найти то место в таблице, где располагается запись, содержащая это значение.
Упорядоченный - означает, что значения полей, хранящихся в индексе, упорядочены.
Очень часто индекс сравнивают с библиотечным каталогом, в котором все книги записаны на карточки и упорядочены каким-то образом: по алфавиту или по темам, а в каждой карточке написано, где именно в хранилище располагается данная книга.
Для чего нужны индексы?
Единственное, чему способствуют индексы, - это ускорению поиска записи по ее индексированному полю (индексированное - значит входящее в индекс).
Итак, основная функция индексов - обеспечивать быстрый поиск записи в таблице. Любое использование индексов сводится именно к этому.
Как реализована эта функция поиска? На входе функции мы имеем значение индексированного поля (или нескольких полей). В результате поиска мы должны получить всю запись, в которой индексированное поле имеет заданное значение. Сначала в индексе (точнее, в упорядоченном массиве значений индексированного поля) ищется нужное значение, затем берется адрес страницы данных, на которой лежит искомая запись, сервер перемещается на эту страницу и читает найденную запись. Выглядит довольно громоздко, однако поиск с помощью индекса происходит во много раз быстрее, чем при последовательном переборе всех значений из таблицы.
Если продолжить аналогию индекса с библиотечным каталогом, то поиск записи с помощью индекса очень похож на поиск книги с помощью карточки. Сюит нам найти книгу в относительно небольшом по объему каталоге (по сравнению со всем библиотечным хранилищем), как сразу получаем информацию о точном местонахождении книги и можем направиться прямиком туда. Поиск же без использования индекса можно сравнить с последовательным перебором всех книг в библиотеке!
Перебор всех записей в таблице называется прямым или естественным (NATURAL). Надо сказать, что, несмотря на мощности современных компьютеров, при достаточно большом количестве записей в таблице естественный перебор можег быть очень долгим процессом.
Как устроены индексы
Индекс не является частью таблицы - это отдельный объект, связанный с таблицей и другими объектами базы данных. Это очень важный момент реализации СУБД, который позволяет отделить хранение информации от ее представления.
InterBase, как и всякая другая реляционная база данных, хранит записи в таблицах в неупорядоченном виде, т. е. совершенно не заботится о том, как физически располагаются записи в таблице. Неупорядоченность хранения означает, что две записи, добавляемые в таблицу одна за другой, совсем не обязательно окажутся "рядом". Более того, данные, извлекаемые из таблицы, также не имеют какого-либо порядка, кроме того, который явно должен быть указан пользователем, составляющим запрос на выборку.
Однако без упорядочения хранящихся данных обойтись невозможно: конечные пользователи приложений хотят видеть свои данные в определенном порядке - например, фамилии людей по алфавиту. Задачу представления данных в упорядоченном виде решают индексы. Значения полей, входящих в индекс упорядочены и представлены в особом виде, оптимизированном для поиска нужных значений (а именно это и нужно для построения упорядоченных последовательностей). Отделение хранения данных от их представления дает дополнительные преимущества по сравнению с непосредственной сортировкой - исходную таблицу может потребоваться отсортировать по-разному. Тогда на помощь приходят индексы - их может быть до 64 на каждую таблицу!
Если говорить о реализации индексов на физическом уровне, то они представляют двоичное дерево, узлы которого представляют собой пары "значение поля в индексе" - "расположение данных в таблице". Поиск нужной записи в индексе идет с помощью механизма хеш-поиска - одною из самых быстрых алгоритмов поиска.
Применение индексов
Теперь, когда ясно, что можно требовать от индексов, настало время разобраться с тем, какую роль они играют в базе данных. Индексы используются в трех основных случаях:
* Ускорение выполнения запросов. Индексы создаются для полей, которые используются в условиях поиска SQL-запросов.
* Обеспечение уникальности значений в полях; Ограничение первичного ключа (о которых рассказывалось в главе "Таблицы. Первичные ключи") требует, чтобы во всей таблице не нашлось двух одинаковых значений полей, входящих в первичный ключ. Чтобы выполнить это условие, необходимо при каждой вставке новой записи производить поиск такого же значения, которые будет вставлено. Для поиска записи используется особая разновидность индекса - уникальный индекс (см. ниже).
* Обеспечение ссылочной целостности. Ограничения внешних ключей Foreign key (которые рассмотрены в главе "Ограничения базы данных") используются для проверки того, чтобы вставляемые в таблицу значения обязательно существовали в другой таблице. При создании внешнего ключа автоматически создается индекс, который применяется как для ускорения запросов, использующих соединение таблиц, так и для проверки условий внешнего ключа.
Вот вкратце и все возможные применения индексов. Теперь мы рассмотрим особенности каждого случая более подробно и ответим на ряд часто возникающих вопросов, связанных с применением индексов.
Ускорение выполнения запросов с помощью индексов
Выше описано, что применение индексов может значительно ускорить выполнение запросов. Это действительно так для большинства случаев, но есть и определенные оговорки. Сначала ответим на вопрос, часто возникающий у тех, кто познакомился с индексами. Раз индексы ускоряют выборку из базы данных, почему бы не проиндексировать все поля в таблице? Есть два момента, препятствующих всеобщей индексации, - это дисковое пространство и издержки при модификации данных в таблице. Каждый создаваемый индекс имеет объем, равный объему данных в индексированном поле, плюс объем данных о расположении записей. Если создать индексы на каждое поле в таблице, то их суммарный объем будет больше, чем объем данных в таблице! Поэтому создание большого количества индексов приводит к большому расходу дискового пространства.
Второй момент более важен - это издержки при модификации данных в таблице. В реляционной СУБД, как вы знаете, записи в таблицах неупорядочены и потому добавление/удаление записей происходят без значительных затрат ресурсов сервера. Даже если удаляется запись из середины базы данных, то не происходит перемещения объемов данных для того, чтобы закрыть "дыру", - это попросту не нужно: сервер просто пометит освободившееся место и при случае запишет туда что-нибудь. Что касается добавления, то оно почти всегда происходит в конец таблицы. Однако хотя основные данные в таблице и не "дергаются" сервером при модификации, но данные, хранящиеся в индексах, переупорядочиваются каждый раз при добавлении/удалении записей! То есть серверу при добавлении записи в середину таблицы, например, приходится перестраивать индекс! Конечно, реализация индекса некоторым образом рассчитана на частые перестройки, но эти действия все же занимают время и ресурсы процессора и при слишком большом количестве индексов в таблице модификация данных в ней может быть в десятки раз медленнее, чем у такой же таблицы без индексов!