Индекс (базы данных)

Материал из Википедии — свободной энциклопедии

Индекс (англ. index) — объект базы данных, создаваемый с целью повышения производительности выполнения запросов. Таблицы в базе данных могут иметь большое количество строк, которые хранятся в произвольном порядке, и их поиск по заданному значению путем последовательного просмотра таблицы строка за строкой может занимать много времени. Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет находить нужную строку по заданному значению. Ускорение работы с использованием индексов достигается в первую очередь за счёт того, что индекс имеет структуру, оптимизированную под поиск - например, балансированного дерева. Некоторые СУБД расширяют возможности индексов введением возможности создания индексов по выражениям. Например, индекс может быть создан по выражению upper(last_name) и соответственно будет хранить ссылки, ключём к которым будет значение поля last_name в верхнем регистре. Кроме того, индексы могут быть объявлены как уникальные и как неуникальные. Уникальный индекс реализует ограничение целостности на таблице, исключая возможность вставки повторяющихся значений.

[править] Архитектура

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

Индексы физическм могут быть реализованы различными структурами. Наиболее частоупотребимы B+ деревья и хэши.

[править] Последовательность столбцов в составном индексе

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

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

[править] Производительность

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

[править] Ограничения

Индексы полезны для многих приложений, однако на их использование накладываются ограничения. Возьмём такой запрос SQL: SELECT first_name FROM people WHERE last_name = 'Франкенштейн';. Для выполнения такого запроса без индекса СУБД должна проверить поле last_name в каждой строке таблицы (этот механизм известен как «полный перебор» или «полный скан таблицы», в плане может отображаться словом «NATURAL»). При использовании индекса СУБД просто проходит по двоичному дереву, пока не найдёт запись "Франкенштейн". Такой проход требует гораздо меньше ресурсов, чем полный перебор таблицы.

Теперь возьмём такой запрос: SELECT email_address FROM customers WHERE email_address LIKE '%@yahoo.com';. Этот запрос должен нам найти всех клиентов, у которых е-мейл заканчивается на "@yahoo.com", однако даже если по столбцу email_address есть индекс, СУБД всё равно будет использовать полный перебор таблицы. Это связано с тем, что индексы строятся в предположении, что слова/символы идут слева направо. Использование символа подстановки в начале условия поиска исключает для СУБД возможность использования поиска по бинарному дереву. Эта проблема может быть решена созданием дополнительного индекса по выражению reverse(email_address) и формированием запроса вида: select email_address from customers where reverse(email_address) like reverse('%@yahoo.com');. В данном случае символ подстановки окажется в самой правой позиции ("moc.oohay@%"), что не исключает использование индекса по reverse(email_address).