Кластерные и некластерные индексы реляционных баз данных

В данный статье мы рассмотрим разницу кластерных и некластерных индексов. Познакомимся со структурой данных B-Tree в которой индексы хранятся. А так-же поговорим про составные и покрывающие индесы.

Индекс

Индекс (index) — это объект базы данных, создаваемый с целью повышения производительности поиска данных.

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

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

Кластерный индекс (clustered index) – это тип индекса в СУБД с древовидной структурой, где значения индекса вместе с данными хранятся в виде упорядоченного дерева, обычно в виде сбалансированного дерева поиска — B-дерева (или его вариациями B дереверьев).
В кластерном индексе каждый уровень дерева представляет собой индексные страницы, а конечные страницы (листья, Leaf) содержат реальные данные строк таблицы.

Рассмотрим кластерный индекс (рис.1) построенный на колонке post_id (уникальный идентификатор записи).

Структура кластерного индекса выглядит следующим образом:

1. Корень (root) — вершина дерева, содержат отсортированные значения индекса и указатели на дочерние уровни. Корень данные не хранит.
   Корневой уровень предоставляет начальную точку поиска при выполнении запроса.
2. Промежуточные уровни (intermediate) — хранят отсортированные значения индекса и указатели на дочерние уровни (в нашем случае Leafs). Данные колонок промежуточные уровни не хранят.
3. Листья (leaf) — самые нижние уровни дерева, содержащие полные строки таблицы (колонки с данными). Листья хранятся в упорядоченном по индексу, фрагментированном виде на диске.

Рассмотрим пример:
Мы ищем запись в таблице и все его колонки, где post_id=5.
База данных начинаем поиск с Root node , найдя в списке что искомое значение 5 — это диапазон между 5-6 мы переходим по указателю на Intermediate node в нем мы находим указатель на Leaf Node , где хранятся все данные о post_id=5

Этот пример был упрощен, т.к. в большинстве случаев диапазон в списках будет намного шире (например первая строка от 1-100, а вторая строка от 101-200), и глубина дерева будет иметь больше уровней.

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

B-Tree

Структура дерева B-Tree позволяет быстро и эффективно выполнять поиск, вставку, удаление и обновление записей на основе ключевых значений индексированных колонок.
Сложность алгоритма B-Tree — O(log n).

Ниже в таблице наглядный пример, сколько сравнений нужно сделать для поиска записи в таблице БД с разным количеством строк:

При добавлении новой строки в таблицу, она дописывается не в конец файла, не в конец плоского списка, а в нужную ветку и узел древовидной структуры, соответствующую ей по сортировке. Иногда дерево выполняет ребалансировку.

Можете поиграться с интерактивным интерфейсом добавляя узлы в B-Tree
— Интерактивный пример 1
— Интерактивный пример 2

MySQL InnoDB особенности

В MySQL в InnoDB каждая таблица должна обладать кластерным индексом. Обычно, кластерный индекс — синоним primary key.

Все данные в InnoDB хранятся в кластерном индексе.

• В MySQL для кластерного индекса используется PRIMARY KEY.
• Если он не был создан, InnoDB возьмет первый UNIQUE index, если он существует.
• Если и UNIQUE index не был создан, тогда MySQL создаст скрытый кластерный индекс с именем GEN_CLUST_INDEX, в котором будут содержаться ID индекса, и при добавлении новой строки, ID будет автоматически увеличиваться.

MySQL MyISAM особенности

MyISAM, в отличие от InnoDB, не поддерживает кластерные индексы, все индексы там некластерные.

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

Некластерный индекс (non-clustered index, secondary index) — это это тип индекса в СУБД похожий на кластерный, который создает дополнительную структуру данных (B-tree, Hash, etc) для таблицы по колонке/нескольким колонкам для ускоренного поиска.
В таком индексе хранятся данные индексируемой колонки, а так-же кластерный ключ индекса.

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

В некластерном индексе на листьях древовидной структуры хранятся «ссылки» на запись кластерного индекса.

Указатель на кластерный индекс необходим в случае, если нужно получить данные другой колонки, которая не находится в некластерном индексе.
В этом случае БД выполнит дополнительный поиск строки по кластерном индексу и достанет значения этих колонок из Leaf (листа) кластерного индекса.
В итоге мы получаем 2 поиска по B-Tree дереву: первый некластерный и второй кластерный.

Для InnoDB в MySQL

Имейте ввиду что размер кластерного индекса влияет на размер некластерного индекса, т.к. некластерный индекс содержит ключ кластерного индекса.

Таблицы могут иметь несколько различных некластерный индексов.

Составной индекс

Составной индекс — это индекс, который создан на основе двух или более столбцов в таблице. Он используется для ускорения доступа к данным при выполнении запросов, которые используют в WHERE или JOIN условия столбцы, включенные в индекс.

CREATE INDEX comp_index
ON my_table (column1, column2);

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

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

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

CREATE INDEX covering_index
ON my_table (salary, name, address);

SELECT name, address FROM my_table WHERE salary = 10000;

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

Покрывающие индексы могут замедлять работу БД, если у вас много опрераций на insert и update этих полей.