Индекс (базы данных)
Материал из Википедии — свободной энциклопедии
Индекс (англ. index) — объект базы данных, создаваемый с целью повышения производительности выполнения запросов. Таблицы в базе данных могут иметь большое количество строк, которые хранятся в произвольном порядке, и их поиск по заданному значению путем последовательного просмотра таблицы строка за строкой может занимать много времени. Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет находить нужную строку по заданному значению. Ускорение работы с использованием индексов достигается в первую очередь за счёт того, что индекс имеет структуру, оптимизированную под поиск - например, балансированного дерева. Некоторые СУБД расширяют возможности индексов введением возможности создания индексов по выражениям. Например, индекс может быть создан по выражению upper(last_name) и соответственно будет хранить ссылки, ключом к которым будет значение поля last_name в верхнем регистре. Кроме того, индексы могут быть объявлены как уникальные и как неуникальные. Уникальный индекс реализует ограничение целостности на таблице, исключая возможность вставки повторяющихся значений.
Содержание |
[править] Архитектура
Существует два типа индексов: кластерные и некластерные. У каждой таблицы может быть только один кластерный индекс и множество некластерных. При наличии кластерного индекса строки таблицы физически хранятся в заданном порядке и непосредственно связаны с элементами индекса, благодаря чему значительно ускоряется доступ к данным при использовании запросов, использующих данный индекс. Если в таблице нет кластерного индекса, таблица является неупорядоченной. Некластерный индекс, созданный для такой таблицы, содержит только указатели на записи таблицы, в связи с чем при выборке необходимо по крайней мере ещё одно обращение к диску для получения собственно записи.
Индексы физически могут быть реализованы различными структурами. Наиболее частоупотребимы B* деревья, B+ деревья, B-деревья и хеши.
[править] Последовательность столбцов в составном индексе
Последовательность, в которой столбцы представлены в составном индексе, достаточно важна. Дело в том, что получить набор данных по запросу, затрагивающему только первый из проиндексированных столбцов, можно. Однако в большинстве СУБД невозможно или неэффективно получение данных только по второму и далее проиндексированным столбцам (без ограничений на первый столбец).
Например, представим себе телефонный справочник, отсортированный вначале по городу, затем по фамилии, и затем по имени. Если вы знаете город, вы можете легко найти все телефоны этого города. Однако в таком справочнике будет весьма трудоёмко найти все телефоны, записанные на определённую фамилию - для этого необходимо посмотреть в секцию каждого города и поискать там нужную фамилию. Некоторые СУБД выполняют эту работу, остальные же просто не используют такой индекс.
[править] Производительность
Для оптимальной производительности запросов индексы обычно создаются на тех столбцах таблицы, которые часто используются в запросах. Для одной таблицы может быть создано несколько индексов. Однако увеличение числа индексов замедляет операции добавления, обновления, удаления строк таблицы, поскольку при этом приходится обновлять сами индексы.
[править] Ограничения
Индексы полезны для многих приложений, однако на их использование накладываются ограничения. Возьмём такой запрос SQL: SELECT first_name FROM people WHERE last_name = 'Франкенштейн';. Для выполнения такого запроса без индекса СУБД должна проверить поле last_name в каждой строке таблицы (этот механизм известен как «полный перебор» или «полный скан таблицы», в плане может отображаться словом «NATURAL»). При использовании индекса СУБД просто проходит по B-дереву, пока не найдёт запись "Франкенштейн". Такой проход требует гораздо меньше ресурсов, чем полный перебор таблицы.
Теперь возьмём такой запрос: SELECT email_address FROM customers WHERE email_address LIKE '%@yahoo.com';. Этот запрос должен нам найти всех клиентов, у которых е-мейл заканчивается на "@yahoo.com", однако даже если по столбцу email_address есть индекс, СУБД всё равно будет использовать полный перебор таблицы. Это связано с тем, что индексы строятся в предположении, что слова/символы идут слева направо. Использование символа подстановки в начале условия поиска исключает для СУБД возможность использования поиска по B-дереву. Эта проблема может быть решена созданием дополнительного индекса по выражению reverse(email_address) и формированием запроса вида: select email_address from customers where reverse(email_address) like reverse('%@yahoo.com');. В данном случае символ подстановки окажется в самой правой позиции ("moc.oohay@%"), что не исключает использование индекса по reverse(email_address).
[править] Редкий индекс
Редкий индекс (англ. sparse index) в базах данных – это файл с последовательностью пар ключей и указателей[1]. Каждый ключ в редком индексе, в отличие от плотного индекса, ассоциируется с определённым указателем на блок в сортированном файле данных. Идея использования индексов пришла оттого что современные базы данных слишком массивны и не помещаются в основную память. Мы обычно делим данные на блоки и размещаем данные в памяти поблочно. Однако поиск записи в БД может занять много времени. С другой стороны, файл индексов или блок индексов намного меньше блока данных и может поместиться в буфере основной памяти что увеличивает скорость поиска записи. Поскольку, ключи отсортированы можно воспользоваться бинарным поиском. В кластерных индексах с дублированными ключами редкий индекс указывает на наименьший ключ в каждом блоке.
[править] Примечания
- ↑ Литература: Database Systems: The Complete Book. Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer D. Widom
Особенности индексов для бизнес-приложений 1С:Предприятие 8 в субд отражены здесь
