А Ковязин - Мир InterBase. Архитектура, администрирование и разработка приложений баз данных в InterBase/FireBird/Yaffil
Перебор всех записей в таблице называется прямым или естественным (NATURAL). Надо сказать, что, несмотря на мощности современных компьютеров, при достаточно большом количестве записей в таблице естественный перебор можег быть очень долгим процессом.
Как устроены индексы
Индекс не является частью таблицы - это отдельный объект, связанный с таблицей и другими объектами базы данных. Это очень важный момент реализации СУБД, который позволяет отделить хранение информации от ее представления.
InterBase, как и всякая другая реляционная база данных, хранит записи в таблицах в неупорядоченном виде, т. е. совершенно не заботится о том, как физически располагаются записи в таблице. Неупорядоченность хранения означает, что две записи, добавляемые в таблицу одна за другой, совсем не обязательно окажутся "рядом". Более того, данные, извлекаемые из таблицы, также не имеют какого-либо порядка, кроме того, который явно должен быть указан пользователем, составляющим запрос на выборку.
Однако без упорядочения хранящихся данных обойтись невозможно: конечные пользователи приложений хотят видеть свои данные в определенном порядке - например, фамилии людей по алфавиту. Задачу представления данных в упорядоченном виде решают индексы. Значения полей, входящих в индекс упорядочены и представлены в особом виде, оптимизированном для поиска нужных значений (а именно это и нужно для построения упорядоченных последовательностей). Отделение хранения данных от их представления дает дополнительные преимущества по сравнению с непосредственной сортировкой - исходную таблицу может потребоваться отсортировать по-разному. Тогда на помощь приходят индексы - их может быть до 64 на каждую таблицу!
Если говорить о реализации индексов на физическом уровне, то они представляют двоичное дерево, узлы которого представляют собой пары "значение поля в индексе" - "расположение данных в таблице". Поиск нужной записи в индексе идет с помощью механизма хеш-поиска - одною из самых быстрых алгоритмов поиска.
Применение индексов
Теперь, когда ясно, что можно требовать от индексов, настало время разобраться с тем, какую роль они играют в базе данных. Индексы используются в трех основных случаях:
* Ускорение выполнения запросов. Индексы создаются для полей, которые используются в условиях поиска SQL-запросов.
* Обеспечение уникальности значений в полях; Ограничение первичного ключа (о которых рассказывалось в главе "Таблицы. Первичные ключи") требует, чтобы во всей таблице не нашлось двух одинаковых значений полей, входящих в первичный ключ. Чтобы выполнить это условие, необходимо при каждой вставке новой записи производить поиск такого же значения, которые будет вставлено. Для поиска записи используется особая разновидность индекса - уникальный индекс (см. ниже).
* Обеспечение ссылочной целостности. Ограничения внешних ключей Foreign key (которые рассмотрены в главе "Ограничения базы данных") используются для проверки того, чтобы вставляемые в таблицу значения обязательно существовали в другой таблице. При создании внешнего ключа автоматически создается индекс, который применяется как для ускорения запросов, использующих соединение таблиц, так и для проверки условий внешнего ключа.
Вот вкратце и все возможные применения индексов. Теперь мы рассмотрим особенности каждого случая более подробно и ответим на ряд часто возникающих вопросов, связанных с применением индексов.
Ускорение выполнения запросов с помощью индексов
Выше описано, что применение индексов может значительно ускорить выполнение запросов. Это действительно так для большинства случаев, но есть и определенные оговорки. Сначала ответим на вопрос, часто возникающий у тех, кто познакомился с индексами. Раз индексы ускоряют выборку из базы данных, почему бы не проиндексировать все поля в таблице? Есть два момента, препятствующих всеобщей индексации, - это дисковое пространство и издержки при модификации данных в таблице. Каждый создаваемый индекс имеет объем, равный объему данных в индексированном поле, плюс объем данных о расположении записей. Если создать индексы на каждое поле в таблице, то их суммарный объем будет больше, чем объем данных в таблице! Поэтому создание большого количества индексов приводит к большому расходу дискового пространства.
Второй момент более важен - это издержки при модификации данных в таблице. В реляционной СУБД, как вы знаете, записи в таблицах неупорядочены и потому добавление/удаление записей происходят без значительных затрат ресурсов сервера. Даже если удаляется запись из середины базы данных, то не происходит перемещения объемов данных для того, чтобы закрыть "дыру", - это попросту не нужно: сервер просто пометит освободившееся место и при случае запишет туда что-нибудь. Что касается добавления, то оно почти всегда происходит в конец таблицы. Однако хотя основные данные в таблице и не "дергаются" сервером при модификации, но данные, хранящиеся в индексах, переупорядочиваются каждый раз при добавлении/удалении записей! То есть серверу при добавлении записи в середину таблицы, например, приходится перестраивать индекс! Конечно, реализация индекса некоторым образом рассчитана на частые перестройки, но эти действия все же занимают время и ресурсы процессора и при слишком большом количестве индексов в таблице модификация данных в ней может быть в десятки раз медленнее, чем у такой же таблицы без индексов!
Это две основные причины, которые препятствуют всеобщей индексации. Помимо них есть и еще несколько замечаний, ограничивающих применение индекса. Первое - это правило 20 %. Оно гласит, что если запрос на выборку возвращает более 20 % записей из таблицы, то использование индекса может замедлить выборку данных! Конечно, ситуация зависит от конкретного запроса и условий, наложенных на выборку, но нужно помнить, что 20 % записей являются порогом, когда эффективность использования индексов ставится под вопрос. Второе замечание формулируется не так очевидно. Оно связано с работой оптимизатора InterBase.
Оптимизатор - это совокупность механизмов, которые разрабатывают таи выполнения запроса. Когда пользователь передает InterBase какой-либо SQL-запрос, он указывает, ЧТО должен вернуть сервер в результате выполнения запроса, но не определяет, КАК сервер должен выполнять запрос. Оптимизатор на основе переданного запроса строит план его выполнения, т. е. откуда и в каком порядке будут браться данные для выполнения запроса, какие индексы будут при этом использоваться. Когда сервер анализирует условия на выборку (это в основном части выражения WHERE, ORDER BY и т. д.), то для каждого поля, входящего в условие, сервер пытается использовать индекс. К сожалению, алгоритм создания плана несовершенен и оптимизатор часто использует индексы, которые не слишком эффективны для конкретного запроса, из-за чего может существенно замедлиться время выполнения. Поэтому создание лишних индексов может привести к созданию неоптимальных планов.
Надо отметить, что в клоне Yaffil эта проблема разрешена за счет использования современных алгоритмов построения пчанов.
Третьим случаем, когда индекс не нужен, являются поля с ограниченным набором значений - например, поле, которое хранит информацию о поле человека и содержит только два возможных значения - "м" и "ж"; нет никакого смысла индексировать это поле.
Итак, основные ограничения на создание индексов мы рассмотрели. Теперь следует рассмотреть вопрос, когда следует использовать индексы, чтобы добиться улучшения производительности. Существует 3 основных случая, когда необходимо проиндексировать поле:
* Когда это поле используется в условиях поиска в запросах.
* Когда соединения таблиц (JOIN) используют это поле.
* Когда это поле используется в предложениях сортировки ORDER BY.
Если поле применяется указанным выше образом, то создание индекса на него может привести к улучшению производительности запроса.
Давайте рассмотрим синтаксис создания индексов. Вот полный формат команды DDL, который позволяет создавать индексы:
CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]]
INDEX index ON table (col [, col ...]);
Минимальным выражением, создающим индекс, является следующее:
CREATE INDEX my_index ON Table_example(ID)
В этом примере создается индекс с именем my_index для таблицы Table_example, причем индексированным полем является поле ID. Индекс является возрастающим, т. е. значения в нем упорядочены по возрастанию, а также неуникальным, т. е. значит, что поле ID может иметь несколько одинаковых значений. Это, конечно же, самый простой пример индекса - самый распространенный.
Как видно из описания синтаксиса, индекс может содержать не одно, а несколько полей. Такой индекс используется при часто выполняющихся запросах, которые содержат в условиях поиска или сортировки сочетание индексированных полей. Например, если у нас есть таблица, содержащая поля Фамилия, Имя, Отчество, то при запросе, использующем сортировку по ФИО, будет применен 1акой индекс. Вообще говоря, необязательно вводить условия на все 3 поля, применяемые в индексе, чтобы использовать его преимущества. Если мы желаем сортировать результат запроса, то индекс будет использован в случае, если первое поле в условии сортировки совпадает с первым полем в индексе, например наш индекс будет задействован в случае сортировки по Фамилии и Имени.
