Как устроены индексы в MySql, чем отличается индексирование в двух наиболее популярных движках MyISAM и InnoDb, чем первичные ключи отличаются от простого индекса, что такое кластерные индексы и покрывающие индексы, как с помощью них можно ускорить запросы. Вот как мне кажется наиболее интересные темы которые раскрою в этой статье. Тут же постараюсь подробно раскрыть тему с позиции того как работает этот механизм внутри. Буквально на пальцах и с позиции абстракций а не конкретики. В общем чтоб было минимум текста и максимум понятно.

Небольшое оглавление:

• Вводная информация

• Что представляет из себя индекс в MySql

• Скорость чтения из индекса

• Отличия в индексах MyISAM и InnoDb

• Кластерный индекс

• Первичные и "вторичные" индексы в чем отличия

• Покрывающие индексы

Вводная информация

В MySql существует несколько типов индексов и каждый из них хорош для выполнения своих специализированных задач. Например Hash индекс хорош для хранения данных в виде ключ - значение в оперативной памяти, FULLTEXT индекс для поиска по текстовым документам, SPATIAL для хранения информации о гео-объектах, UNIQUE для уникальных значений. Но все же в подавляющем большинстве случаев мы используем индекс на основе B-дерева (BTREE) или Balanced-Tree. Сбалансированное оно потому что высота каждого поддерева с общим корневым элементом может отличаться, но всегда не более чем на константную величину. Далее в статье речь пойдет именно про BTREE индексы, по умолчанию под индексами буду подразумевать именно их.

Что представляет из себя индекс в MySql

На рисунке изобразил схематично как устроен индекс. Имеются узловые элементы (квадраты) и листья (круги). Предположим у нас есть таблица с колонками "Val" и "ID" как на рисунке. В этой таблице индекс построен по числовому полю "ID". Тогда получается что в узловых элементах находятся значения индекса и ссылки на другой более нижний узел или лист. В листовых же элементах точно так же лежат значения индекса которые уже ссылаются непосредственно на данные из таблицы.

Процесс поиска происходит примерно следующим образом. Например нужно найти строку с индексом 11.

• начинаем просмотр корневого (верхнего) узла

• первое значение в нем 10

• идем к следующему 19, оно уже больше чем нам нужно

• по ссылке слева от 19 переходим к следующему нижнему узлу

• там первое значение 13, оно больше чем нам нужно

• опять по ссылке слева переходим к более нижнему элементу

• это уже будет листовой элемент, в нем уже лежат непосредственно данные

• просматриваем данные по порядку

• находим 11

• переходим по ссылке непосредственно к строке в таблице.

Скорость чтения из индекса

Такое устройство индекса позволяет обеспечить логарифмическую скорость поиска O(log n). Это очень быстро. Вот таблица где для наглядности посчитал сколько сравнений нужно сделать для поиска записи в таблице с разным количеством данных:

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

Отличия в индексах MyISAM и InnoDb

MyIsam это более старый движок чем InnoDb и все описанное выше хорошо описывает устройство индекса именно в MyIsam. Более того для MyIsam можно сказать что первичный индекс и просто обычный индекс ни чем между собой не отличаются. В целом таблицы построенные на движке MyIsam вполне себе могут существовать даже без первичного ключа и без всякого индекса в целом. А вот InnoDb уже более свежий и продвинутый движок, и тут как раз есть отличия первичного ключа и просто индекса. Создать таблицу InnoDb тоже можно не указав первичный ключ, но в этом случае первичный ключ все равно создастся. Это называется суррогатный первичный ключ. InnoDb сам выберет поле по которому нужно этот ключ создать, если ни одно поле не подходит, то создаст новое числовое поле, которое конечно же будет скрыто и в структуре его не увидеть. Для разбора индексов InnoDb первым делом нужно начать с кластеризации.

Кластерный индекс

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

Более того, если мы говорим о таблицах на основе движка InnoDb, то в целом понятие таблица довольно абстрактное. На картинке она нарисована просто для наглядности. На самом деле ни какой таблицы по сути не существует, а все данные просто хранятся в кластерном индексе.

Первичные и "вторичные" индексы в чем отличия

Выше было оговорено что для MyIsam нет разницы между первичными и "вторичными" ключами.

На картинке нарисован первичный и вторичный ключ в MyIsam. Первичный ключ построен по полю "ID", вторичный по полю "Val". Видно что их структура одинакова. И в том и в другом в листьях расположены значения индекса и ссылки на строки в таблице.

В InnoDb это устроено немного по другому.

Как уже говорил, таблица тут просто для наглядности. Все ее данные хранятся в первичном (кластерном ключе). Тут первичный ключ построен по полю "Id", вторичный по полю "Val". Видно что в листьях первичного ключа лежат значения индекса + все данные из строк таблицы. Во вторичном же ключе, в листьях лежат значения ключа + первичный ключ.

Можно резюмировать что для MyIsam нет различий между первичным и вторичными индексами. Для InnoDb первичный ключ содержит в себе все данные таблицы, вторичный же ключ содержит значения ключа плюс значение первичного ключа. Получается что при поиске по вторичному ключу, поиск будет произведен дважды. Первый раз непосредственно по самому индексу, будет найдено значение первичного индекса. И уже второй раз по найденому первичному индексу для поиска данных всей строки.

Покрывающие индексы

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

Смысл покрывающих индексов в том, что MySql может вытаскивать данные непосредственно из самого индекса, не читая при этом всю строку и вовсе не читая строку. Для такой оптимизации нужно чтобы все поля указанные в SELECT имелись в индексе. То есть например у нас имеется таблица с полями "id", "name", "surname", "age", "address". И мы проиндексировали ее по полю "id". В запросе мы хотим получить например "id" и "name". При таком условии MySql найдет по первичному ключу нужную строку, прочитает ее и отбросит все поля не указанные в SELECT. Если же мы немного оптимизируем этот запрос и построим индкес по двум полям "id" и "name", то в таком случае MySql найдя нужную строку по этому индексу не пойдет читать всю эту строку, а просто возьмет данные, которые нужны непосредственно из индекса. Правда есть обратная сторона такого подхода, а именно размер индекса в этом случае будет больше, по этому нужно грамотно подходить к построению покрывающих индексов.

Более подробно можно почитать в очень хорошей книге "MySQL по максимуму" Бэрон Шварц, Петр Зайцев, Вадим Ткаченко