Индексы в SQL базах данных

Что такое индексы?

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

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

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

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

Создание индекса

Возвращаясь к таблице users, вы можете принять решение добавить индекс к столбцу email, чтобы ускорить любые запросы, которые работают со значением этого столбца. Это касается также операций UPDATE или DELETE, которые используют электронную почту пользователя. Вот так можно добавить этот индекс:

ALTER TABLE users ADD INDEX idx_email (email);

Эта команда создаёт индекс для столбца users.email c названием индекса idx_email. При наличии индекса оптимизатор запросов базы данных может выбрать его использование, если сочтет это полезным. Если в таблице более одного индекса, оптимизатор запросов должен решить, применение какого из индексов наиболее выгодно по конкретной инструкции SQL.

Серверы баз данных позволяют просматривать индексы для таблицы. В MySQL для этого присутствует команда SHOW, чтобы увидеть все индексы в определённой таблице.

SHOW INDEX FROM users;

Если индекс более не нужен, то удалить его можно таким образом:

ALTER TABLE users DROP INDEX idx_email;

Уникальные индексы

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

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

Многостолбцовые индексы

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

ALTER TABLE users ADD INDEX idx_full_name (last_name, first_name);

Можно заметить, что фамилия (last_name) идёт в индексе первым номером и это неспроста, так как очередность столбцов в индексе имеет значение. Этот запрос будет полезен для поиска по фамилии и имени или просто фамилии, в оставшемся случае (по имени) он будет бесполезен. Нужно учесть, что фамилия здесь более уникальная особенность, чем имя пользователя, поэтому стоит на первом месте.

Типы индексов

Существуют различные реализации индексов основанных на различных механизмах индексирования.

Индексы B-tree

MySQL, Oracle Database и SQL Server по умолчанию имеют индексы на основе сбалансированного дерева ( B-tree). Индексы B-tree структурно организованы в виде деревьев с одним или более узлами ветвления ведущих к одному уровню листовых узлов. Узлы ветвления используются для навигации по дереву, а "листья" содержат фактическую информацию и данные о местонахождении. Например, если для поиска по первой букве имени пользователя в запросе используется буква F, то сервер просмотрит верхний узел ветвления и следует по ссылке к следующему узлу ветвления, который заведует именами, начинающимися с A по M (второй узел на этом уровне отвечает за неиспольземый здесь N-Z диапазон) и следует далее к узлу, который содержит более суженный раздел D-F, в последнем и находится искомый результат на F.

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

Бинарные индексы (Binary Indexes)

Индексы на основе бинарного дерева представляют собой специализированные структуры данных, которые хранят значения в виде бинарного дерева поиска. В таком индексе каждый узел имеет не более двух потомков: один левый (меньший или равный родителю) и один правый (больше родителя). Это позволяет осуществлять быстрый поиск, удаление и вставку элементов, следуя правилам бинарного дерева поиска.

Основное преимущество индексов бинарных заключается в том, что операции поиска, вставки и удаления выполняются в среднем за O(log n) времени, что делает их эффективными для работы с большими наборами данных. Однако для поддержания быстроты операций, важно, чтобы данные были сбалансированными. В противном случае время работы может увеличиться до O(n).

Смысл бинарного поиска – делить данные пополам и смотреть – текущее значение больше или меньше нужного, потом снова пополам, пока не обнаружится результат.

Hash индексы

Индексы Hash представляют собой высокопроизводительные структуры для быстрого доступа к данным, оптимизированные для быстрого поиска отдельных значений. В отличие от B-tree, которые сохраняют данные в иерархической структуре, хеш-индексы используют хеш-функцию для преобразования значений ключей в адреса хранения.

Каждый элемент в индексе Hash ассоциируется с конкретным значением ключа, и при его добавлении или поиске происходит вычисление хеша, который указывает на место хранения данных. Это обеспечивает очень быструю скорость поиска — обычно O(1). Однако в случае коллизий (когда два разных ключа имеют одинаковое значение хеша) используется специальный метод для их разрешения, например, цепочная адресация.

Индексы Hash широко используются в MySQL для обеспечения быстрого доступа к данным по уникальным ключам, особенно в ситуациях, когда необходимо выполнять точные запросы. Однако стоит отметить, что они неэффективны для диапазонных запросов и операций, желающих осуществить поиск (например, “больше” или “меньше”), из-за потери порядковой информации.

Индексы Full-text (Полнотекстовые индексы)

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

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

Полнотекстовые индексы применяются в MySQL, PostgreSQL и SQL Server, предоставляя возможность пользователям быстро находить нужные документы по ключевым словам. Это особенно актуально в случаях, когда необходимо обрабатывать запросы на основе поиска по тексту, что значительно расширяет функциональность баз данных.

Применение выражений в индексах

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

Пример простого индекса с выражением (преобразование в нижний регистр) для MySQL:

CREATE INDEX idx_email_lower ON users (LOWER(email));

Этот индекс с выражением должен оптимизировать поиск, в случае, если будет использован регистронезависимый запрос по email, например:

SELECT * FROM users WHERE LOWER(email) = 'example@example.com';

GIST индексы

GIST (Generalized Search Tree) — это специализированный тип индекса, который используется для работы с данными в PostgreSQL и обеспечивает доступ к различным типам данных, включая геометрические, полнотекстовые и другие. GIST позволяет создавать индексы для сложных объектов, которые не могут быть эффективно проиндексированы с помощью обычных B-деревьев. Например, если вы работаете с географическими данными, GIST может значительно ускорить выполнение запросов, таких как поиск объектов в определенной области или нахождение ближайших точек.

Выполнение индексов

Для каждого запроса сервер базы данных подбирает стратегию выполнения. Если в связанных с запросом таблицах есть индексы сервер учтет их наличие для оптимизации. Чтобы посмотреть, какая стратегия была выбрана для конкретного запроса, различные БД предлагают примерно схожий инструмент, например, в MySQL существует оператор EXPLAIN. Добавленный перед запросом, он отменяет его выполнение, но выводит собственную информацию о том, как оптимизатор запросов собирается его выполнить и, что важно, какие индексы из существующих будут задействованы.

Недостатки индексов

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

По мотивам источника: "Изучаем SQL. Генерация, выборка и обработка данных.", 3-e издание, Алан Болье.