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

В данный статье мы рассмотрим разницу кластерных и некластерных индексов. Познакомимся со структурой данных 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).

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

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

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) для таблицы по колонке/нескольким колонкам для ускоренного поиска. В таком индексе хранятся данные индексируемой колонки, а так-же кластерный ключ индекса.

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

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

Для InnoDB в MySQL

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

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