Для чего нужны индексы в базе данных
Суперсила индексов для оптимизации SQL-запросов
Введение
Вы любите SQL и хотите улучшить свои навыки выполнения SQL-запросов? Вы знаете, что индексация — отличный инструмент для оптимизации запросов, но при этом не уверены, что она из себя представляет, с какой целью и как используется?
Добро пожаловать! Вы оказались именно там, где нужно. Сейчас объясним суть индексации на простом и понятном языке.
Начнем с простого запроса:
Для его выполнения база данных (БД) должна просканировать все 12 миллионов строк, чтобы проверить каждую запись на соответствие. Предположим, что время этой операции составляет 4 секунды.
Можно ли быстрее? Конечно. А Как? С помощью индексации.
Индексация
Понятие индексации
Свое название индексация получила по образу и подобию книжного индекса. Если, читая книгу по статистике, вы ищите информацию о “линейной регрессии”, то, вряд ли, станете поочередно перелистывать сотни страниц, чтобы добраться до главы с интересующим вас материалом.
Вы просто откроете страницу индексов, найдете “линейную регрессию” и сразу перейдете на нужную страницу.
Индексация позволяет задействовать данный метод и в работе БД, которая с помощью созданного индекса быстро находит данные по запросу. А как именно это происходит, разберемся далее.
Создание индексов
Давайте создадим индекс для таблицы product и включим в него ‘category’:
Теперь же задействуем индекс и протестируем выполнение самого первого нашего запроса:
Как видно, в этот раз он будет выполняться намного быстрее и, вероятно, займет 400 миллисекунд.
Выполнение этого запроса займет меньше времени, чем обычно — около 600 миллисекунд. С помощью индекса БД быстро найдет все товары ‘electronics’ и из небольшого списка записей выберет ‘headphones’.
Какова же внутренняя суть процесса?
БД анализирует все возможные пути выполнения запроса, выбирая самый оптимальный из них.
Теперь пора познакомиться с некоторыми терминами БД. Каждый возможный путь называется планом выполнения запроса. По сути, это последовательность операций для получения результата SQL-запроса в реляционной системе управления базами данных (СУРБД).
А компонент СУРБД, определяющий наиболее эффективный способ выполнения запроса с учетом анализа всех возможных планов, называется оптимизатором запросов.
Индексация по нескольким столбцам
Теперь рассмотрим индексацию по нескольким столбцам.
Индекс можно создать более чем для одного столбца.
Данный тип индекса еще больше ускорит выполнение запроса, предположительно до 60 миллисекунд.
Более того, БД может включать более одного индекса.
В каких случаях следует применять индексацию?
Индексы ускоряют работу БД, а по мере ее разрастания их эффективность становится очевиднее.
При этом важно помнить о том, что:
В связи с этим, лучше использовать индексы для БД в хранилищах данных, получающих плановые обновления, т. е. в часы наименьшей нагрузки, а не для производственных, которые обновляются постоянно. Это объясняется тем, что при постоянных обновлениях БД индексы обновляться не будут, а следовательно станут бесполезны.
Типы индексов
Здесь мы кратко рассмотрим 2 типа индексов БД для лучшего понимания темы:
1. Кластеризованные индексы
2. Декластеризованные индексы
Кластеризованные индексы
Кластеризованные называется особый индекс, который использует первичный ключ для структуризации данных в таблице. Он не требует явного объявления и создается по умолчанию при определении ключа. Отсортированный же в порядке возрастания первичный ключ по умолчанию применяется в качестве кластеризованного индекса.
Продемонстрируем вышесказанное на простом примере:
Интересно, как же именно это происходит?
Индексы используют оптимальный метод поиска, известный как двоичный поиск.
Двоичный поиск — это эффективный алгоритм поиска записи в сортированном списке. Принцип его работы основан на повторяющемся делении данных пополам и определении того, находится ли искомая запись до или после записи в середине структуры данных. Если значение искомой записи меньше срединного, то поиск продолжается в первой половине, иначе — во второй. Эта процедура повторяется вплоть до нахождения значения. Благодаря данному методу уменьшается число требуемых поисков и, следовательно, ускоряется выполнение запросов.
Следующая таблица отражает соотношение записей данных и максимальное число поисков:
Аналогичным образом для нашего датасета с 12 миллионами строк понадобится не 12 миллионов, а всего лишь 24 поиска — и всё благодаря двоичному поиску. Думаю, теперь вы осознаете супер силу индексов.
Некластеризованный индекс
Теперь узнаем, как применить преимущества индексации к столбцами, отличающимися от первичного ключа. Для этого существуют некластеризованные индексы.
Их примеры уже встречались в начальных разделах статьи во время написания оптимизированных запросов — это индексы, которые требуют явного определения.
Некластеризованный индекс хранится в одном месте, а физические данные таблицы — в другом. Опять нам на ум приходит сравнение со страницей индексов, которая размещается отдельно от содержимого книги. Благодаря этой особенности для каждой таблицы можно создавать более одного некластеризованного индекса, как было показано ранее.
Как именно это происходит?
Предположим, вы уже создали некластеризованный индекс для столбца и теперь пишите запрос для поиска в нем записи. Этот индекс содержит следующее:
Это наглядно отображено в таблице слева на рис.6:
Давайте рассмотрим этот запрос более подробно:
БД совершает 3 шага:
Как видим, работа с некластеризованным индексом предполагает дополнительный шаг, включающий поиск адреса строки и переход к ней в основной таблице. Следовательно запрос с таким индексом выполняется медленнее в отличие от кластеризованного аналога.
Заключение
Итак, мы выяснили, что такое индексы и какую роль они играют в оптимизации выполнения SQL-запросов, особенно при работе с огромными датасетами.
В завершении приведу вам высказывание Тайгера Вудса, лучшего гольфиста всех времен:
“Независимо от того, насколько хорошо вы играете, вы всегда можете стать лучше, и это вдохновляет”.
«Добавим 2 млн статей и посмотрим, что будет»: как ускорить базу данных с помощью индексов
Разбираемся, как ускорить работу базы данных приложений и сайтов, что такое индексы и как они устроены. Пособие для начинающих backend-разработчиков.
PHP-разработчик digital-агентства «Атвинта», в свободное время пишу на Go/C#/C++. Нравится проектировать и продумывать highload-системы.
Базы данных — это совсем не сложно, даже новички быстро вливаются в тему и начинают работать практически без проблем. А что сложного? Есть таблицы, в них записываем строки — всё просто. Да, и всё работает, никто не жалуется. Пока не наступит момент… когда данных будет много.
Тут нам и приходят на помощь индексы. Во всех базах данных они работают примерно по одному и тому же принципу. В этой статье я буду использовать MariaDB.
Запрос на выборку без индексов
Рассмотрим на простом примере. Есть таблица articles со следующей структурой:
Добавим в таблицу несколько записей:
И сделаем следующий запрос:
Ничего удивительного: простой запрос и выполняется быстро. Но что будет, если данных «чуть-чуть» больше? Давайте добавим, например, 2 млн статей.
И повторим запрос на выборку:
Как видим, время выполнения запроса увеличилось. Хоть и две секунды, но это долго. И нагрузка на диск высокая.
Две секунды на выполнение запроса — не предел; когда данных ещё больше, всё будет ещё хуже. Оптимизировать этот запрос можно с помощью индексов.
Запрос на выборку с индексом
Создаем индекс по колонке views из таблицы articles.
И повторяем запрос:
Вот! Так намного лучше. Выборка проходит так же быстро, как и с тремя записями. В чём же подвох? Как это работает и почему? Что может пойти не так?
Как устроен запрос без индекса и с ним
Запрос к выборке БД без индекса
Что происходит, когда мы запрашиваем данные? А что вы делаете, когда ищете нужную вам строку в таблице? Да, база данных сканирует всю таблицу и выбирает те записи, которые попадают под условия.
Это происходит быстро, когда у нас три записи, и долго, когда их очень много. Ведь наша таблица хранится на физическом носителе и, чтобы просмотреть её всю, нужно считать немало данных.
Запрос к выборке БД с индексом
Я часто встречаю, что индекс путают с id или уникальным идентификатором, считают, что это одно и то же. Это не так! Индекс в базах данных — это другое.
Индекс, который мы создали, представляет из себя такую структуру данных, как B-дерево. Но, например, в InnoDB используется B+-дерево. Всё зависит от подсистемы хранения, а в целом принцип их работы похож. Это дерево строится по колонке views из таблицы articles.
Чтобы понять, как происходит выборка с индексом, нужно знать, как работает B-дерево.
Перед нами B-дерево индекса. В каждом узле хранятся элементы со значениями; в нашем случае это значения из поля views. Также элементы хранят ссылку на строку в таблице.
Поиск начинается с корневого узла. Наша задача — пройти по каждому элементу в узле и сравнить его значение с искомым:
Дерево из примера выше не является копией того, которое построила БД в моём случае. Это я изобразил, чтобы показать, как проходит поиск по дереву.
Рассмотрим алгоритм на примере поиска значения 2001.
То, что мы и искали. А так как искомая ячейка содержит ссылку на место, где лежат наши данные, то мы можем легко и быстро прочитать их.
Ещё один способ запроса с индексом
В данной структуре можно легко делать выборку по диапазонам, например views >= 1000. В случае таких запросов индекс также поможет.
Хоть поиск и значительно ускорился, есть и свои нюансы. Изменения в В-дереве — не самая быстрая операция.
Необходимо, чтобы все конечные узлы (листья) дерева находились на одном уровне, а количество элементов в узлах было одинаковым — тогда мы получим наивысшую скорость выборки.
Чтобы придерживаться этих условий, нужно постоянно проводить перебалансировку дерева. Это и замедляет работу.
Если вы используете несколько десятков индексов в одной таблице, то при вставке или удалении из неё нужно проводить такие нехитрые манипуляции с деревьями. Из этого следует вывод, что не стоит увлекаться и создавать индексы по каждому полю.
Мы рассмотрели создание индекса по одной колонке (views), но в базах данных одной колонкой не ограничишься. Можно создавать составные индексы. Например, если есть поле views и дата created_at, и вы хотите делать подобные запросы: views = 1000 and created_at = «10.10.2019», то имеет смысл создать индекс по двум колонкам.
Что такое индекс mysql и как их использовать
3 ответа 3
Если в кратце, то индекс, это поле по которому оптимизирован(ускорен) поиск.
Поскольку индекс занимает место, то индексировать нужно только те поля, по которым происходит выборка.
Допустим есть таблица.
Допустим вам нужен поиск по имени (firstname).
тогда есть смысл добавить индекс по данному полю.
Будет созданна «карта» которая позволет легко находить записи в оригинальном списке.
Для одной небольшой таблицы приемущество не будет очевидно join несколько (3-4 уже достаточно) таблиц по неиндексированным полям. Убивает сервер на раз!
Вкратце, индексы создаются для повышения производительности поиска данных. Таблицы могут иметь огромное количество строк, которые хранятся в произвольном порядке. Без индекса поиск нужных строк идёт по порядку (последовательно), что на больших объемах данных отнимает много времени.
Индекс создаётся по правилу:
то, чтобы этот запрос отработал быстрее обычного, следует добавить индекс по вышеуказанному правилу:
Тогда тот же самый запрос
отработает гораздо быстрее, если столбец city будет проиндексирован.
На пальцах можно объяснить так:
Когда Вы создаёте таблицу, добавляете в неё данные, то таблица разрастается и она выглядит как просто последовательный список, упорядоченный по тому как в неё данные добавлялись.
Это связано с тем, что когда Вы ищите какую-то запись, то просматриваются все записи, пока не дойдут до нужной.
Когда Вам это окончательно надоедает и Вы хотите что-нибудь сделать, то к Вам на помощь приходят индексы.
Индекс создаётся по какому-то определённому полю (можно по нескольким) по которому, обычно, выполняется поиск. Когда Вы создаёте индекс, то MySql (и любая другая БД) обходит все записи в таблице и строит дерево (скорее всего B-дерево или разновидность), в котором ключами выступает выбранное поле, а содержимым ссылки на записи в таблице.
И когда Вы делаете очередной свой select запрос по таблице, по полю для которого создали индекс MySql (и любая другая БД) знает что у неё есть индекс, по которому пройтись будет быстрее, нежели перебирать все записи и Ваш запрос будет направлен этому индексу и записи, удовлетворяющие условию, будут найдены гораздо быстрее, так как поиск по построенному дереву будет гораздо быстрее, нежели простой перебор всех записей.
Что такое индексы базы данных (для начинающих)?
Многие слышали о том, что индексы в базах данных это весьма полезная штука. Но, одно дело слышать, а другое представлять себе их устройство хотя бы на базовом уровне. Поэтому в рамках данной статьи для начинающих, я рассмотрю этот вопрос, применяя простые и понятные каждому выражения и аналогии из жизни.
Что такое индекс базы данных и зачем он нужен?
Чтобы понять зачем нужны индексы в базе данных и что он собой представляет, сейчас рассмотрим простой пример.
Представьте себе, что у вас есть полочка для книг. При этом изначально эта полочка с книгами пуста. Книги вам то приносят, то уносят, то делают в них какие-то корректировки (к примеру, мемуары или может быть черновики) и тому подобное.
Так как полочка маленькая, то вы как-то не особо задумывались о какой-либо системе классификации, а просто вставляете книги в любые пустые места.
Каждый раз когда-то вам или кому-то необходимо найти определенную книгу, возникает необходимость просматривать все книги с самого начала полочки до первой попавшейся (если нужна только одна книга) или полностью все (если нужно собрать все копии). В принципе, для одной полочки это весьма необременительно.
Теперь, представьте себе, что речь идет не об одной полочке, а об огромном помещении, где находятся тысячи книг.
Тут-то вы и начинаете задумываться о том, что неплохо бы ввести какую-то систему классификации, например, по названию книги. Конечно, полностью сортировать все эти тысячи книг в алфавитном порядке вы не собираетесь, плюс с этим возникло бы куча других вопросов (как добавить книгу в уже заполненную полку и прочие).
Поэтому вы поступаете проще, вы берете каталог, где возможно добавлять листочки. При этом каждую страницу выделяете только под одно название книги, а сами страницы располагаете в каталоге в порядке возрастания названий. Содержание этих страниц весьма просто — вы записываете в каком стеллаже, на какой полке и какой по счету является книга. Если книг несколько, то строчек в этой странице становится несколько.
Таким образом, чтобы найти одну или все нужные книги по названию, вам достаточно открыть этот каталог и быстро пролестнуть до нужной страницы, а затем пройтись по всем указанным стеллажам. При этом для упрощения, вы так же можете первые буквы названий так же индексировать. То есть добавляете наклейку на каждую первую страницу с указанной буквой (таким образом можете сразу перейти, например, к букве «Р», не пролистывая все названия до нее).
Конечно, для поддержки такой системы требуется дополнительное время, но все же оно существенно меньше, чем попытка найти вслепую книгу из тысячи (пара минут против нескольких часов и более).
Так вот, в данном примере, если переносить это в базу данных:
Помещение — это таблица в базе данных. Если чуть проще, то любое скопище однотипных данных (тех же книг), по сути, представляет собой таблицу.
Поиск книги — это sql-запросы получения данных. При этом важно отметить, что сами по себе они не меняются. То есть вам как нужно было найти «Термодинамику», так и осталось нужным найти «Термодинамику». Другое дело, как вы будете это осуществлять — прочесывая тысячи книг или открыв каталог.
Каталог — это и есть упрощенный вариант индекса в базе данных. То есть, индекс это набор дополнительных данных, записанных в удобном виде, который позволяет существенно быстрее осуществлять поиск, хоть и требующий дополнительных усилий для поддерживания его актуальности.
Имя книги (страничка) — это ключ в индексе. То уникальное значение, которое может ссылаться как на одну какую-то запись, так и на несколько. Стоит отметить, что даже если записей для каждого значения будет несколько, это все равно быстрее, чем полный перебор всех данных.
Если суммировать, то можно увидеть, что наличие индекса может быть весьма выгодным. Например, для одной домашней полочки с десятком книг — индекс в общем-то не сильно нужен, а вот когда речь заходит о более больших объемах, то индекс будет весьма полезным.
Так же можно заметить, что добавление индекса не требует того, чтобы сами sql-запросы были переписаны, так как последние являются лишь выражением на упрощенном языке для базы данных. Если продолжить аналогию, то это как попросить кого-то найти вам «Флора и фауна». При этом каким образом и сколько этот кто-то будет искать книгу, будет решать сам этот человек. В данном примере «найти книгу» — это sql-запрос, а этот «кто-то» это база данных.
Какие бывают индексы?
Вообще, в зависимости от типов баз данных, индексы могут быть очень разными и реализоваться за счет специфических математических механизмов. Но, наиболее частым является древовидный индекс, так как поддерживать такой индекс относительно просто и максимальная скорость поиска в нем составляет логарифм по числу максимального количества дочерних узлом от общего количества записей (плюс минус некоторые технические моменты).
Дерево (древовидный индекс) — это специального вида структура, у которой есть корневая вершина и у каждого узла может быть несколько дочерних узлов. При этом каждый узел встречается только один раз и может иметь всего один родительский узел. Выглядит это так:
Как видите, очень похоже на перевернутое обычное зеленое дерево, у которого ветки растут не вверх, а вниз.
Максимальное количество дочерних узлов, как вероятно уже догадались по картинке, это то количество дочерних узлов, больше которого у одного узла не может быть.
Теперь поясню откуда берется логарифм. Дело в том, что дерево обычно заполняется по определенным правилам. К примеру, если у узла максимально может быть всего два дочерних узла (так называемое бинарное дерево), то обычно левый дочерний узел имеет значение меньше текущего, а правый большее значение. Поэтому если вам нужно найти, например, число 30 в дереве с рисунка чуть выше, то вам понадобится всего 4 сравнения (40 — 25 — 32 — 30). Именно из-за этой особенности поиска и берется логарифм (так как каждое сравнение сокращает количество проверяемых элементов в два раза). При этом обычно значение логарифма округляют в большую сторону.
Так же отмечу, что такая скорость достигается за счет того, что дерево строится специальным образом, чтобы не возникало таких ситуаций, как на картинке ниже, где максимальная скорость поиска будет сравнима с простым перебором всех записей.
Как видите, чтобы здесь найти запись с ключом «3» понадобится 4 сравнения (40 — 25 — 10 — 3), хотя всего записей 5.
Практически во всех базах данных, существует деление по уникальности:
Уникальный индекс — это такой индекс, у которого все значения встречаются только один раз. Проводя аналогию, когда каждая книга присутствует только в одном экземпляре и никогда названия книг не совпадают.
Неуникальный индекс — это такой индекс, у которого значения могут повторяться. Проводя аналогию, существуют книги с одними и теми же названиями, но разными авторами, или же просто встречаются копии.
Важно отметить, что если для таблицы создается уникальный индекс, то это означает, что при попытке добавить запись со значением, которое уже встречалось, или же изменить значение какой-то записи на существующее, то база данных не позволит сделать такое действие и будет ругаться (выдавать ошибки). В случае же с неуникальным индексом таких проблем нет.
Так же стоит знать, что индексы делятся по количеству входящих в них полей:
Обычные индексы — состоят из одного поля. Здесь, вероятно, все понятно. Обычный каталог страничек.
Составные индексы — строятся по нескольким полям, при этом расположение полей является важным.
Чуть подробнее про составные индексы. Рассмотрим аналогию с теми же книгами. До этого индекс строился только по названию. Теперь же представим, что книги с одинаковыми названиями часто встречаются. В такой ситуации, легко может получится, что страничка каталога будет состоять из координат сотен книг (десятки авторов и у каждого по десять копий). Бегать их всех проверять — так же немалое количество времени. Поэтому вместо того, чтобы страничка просто перечисляла все местонахождения книг, можно сделать так, чтобы странички с именами книг указывали на дополнительные каталоги, где аналогичным образом проиндексированы авторы.
Немного упрощая, поиск будет выглядит примерно так.
1. Вначале вы ищите в каталоге с именами необходимую страничку с названием.
2. Затем в этой страничке смотрите, где находится соответствующий каталог с авторами.
3. Берете этот каталог и уже в нем находите страничку, где указано месторасположение всех книг с этим автором и названием.
При этом важно понимать, что для каждого названия будет создаваться собственный каталог авторов. То есть в обратном порядке, к сожалению, поиск не осуществить. Если же требуется поиск вначале по автору, а уже затем по названиям книг, то необходимо создавать отдельный составной каталог (составной индекс).
Существуют и другие моменты, но чаще всего достаточно знать хотя бы эти базовые знания.