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

Различия индексов MySql, кластеризация, хранение данных в MyIsam и InnoDb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Количество элементов в таблице

Количество сравнений

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

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

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

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

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

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

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

Первичный и вторичный индекс в MyIsam

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

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

Первичный и вторичный индекс в InnoDb

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

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

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

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

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

Источник

Кластерные и «обычные» индексы MySQL (InnoDB)

Все мы помним хрестоматийное объяснение «что такое индексы в БД и как они облегчают задачи поиска нужных строк». Уверен, у большинства из вас перед глазами встаёт нечто подобное:

И сразу становится очевидно, насколько меньше данных нужно перелопатить для поиска двух-трёх нужных строк. Гениально. Просто. Понятно.

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

Итак, что же такое кластерный индекс, чем он лучше некластерного, и как с ним обстоит дело у MySQL.

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

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

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

При использовании «обычного», некластерного индекса, задача поиска сильно ускоряется. Во-первых, индексная таблица весит много меньше таблицы с данными, а значит элементарно может быть прочитана быстрее. Во-вторых, СУБД чаще всего стараются кешировать индексы в оперативную память, которая сама по себе много шустрее жёсткого диска*. В-третьих, в индексах отсутствуют дублирующиеся строки. А значит, как только мы нашли первое значение, поиск можно прекращать — оно же и последнее. В-четвёртых, данные в индексе отсортированы. А в-третьих и в-четвёртых вместе позволяют использовать алгоритм бинарного поиска (он же метод деления пополам), эффективность которого многократно превосходит простой перебор.

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

Индексация — великая сила. Но если представить все указатели индексной таблицы на строки в таблице данных ОДНОВРЕМЕННО, получится достаточно сложная «паутина»:

И эта паутина, со множеством пересекающихся стрелок, подводит нас к проблеме (просто таки наглядно её демонстрирует), которую создаёт некластерный индекс.

Фрагментация

Оптимизатор MySQL может принять решение вообще не использовать индексы для поиска по небольшим таблицам (до пары десятков записей — зависит от конкретной структуры данных и индекса). Почему? Потому что поиск простым перебором читает данные последовательно. А указатель в индексе ссылается на разрозненные участки данных. И прыжки по ссылкам из индекса в конечном итоге могут стоить дороже полного перебора.

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

Что происходит? Находится значение в индексе — это быстро и просто — и из таблицы данных читаются строки, на которые этот индекс ссылается. Естественно, при большой фрагментированности таблицы накладные расходы на чтение из разных её частей становятся ощутимыми.

И вот тут-то нам и пригодятся…

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

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

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

* В разных движках и при разных настройках это может быть вовсе и не конец, и вовсе и не файла. Слово файл здесь означает «некую единицу измерения данных, соответствующую одной таблице», а «конец файла» употребляется как символ последовательной, линейной записи.

Один из самых мощных и производительных движков для MySQL — InnoDB. Тому много причин, и одна из них — кластерные индексы. Проще всего понять как устроены кластерные индексы, если представить их в динамике: как они разрастаются по мере добавления данных, и как начинает ветвиться таблица.

Первый этап: плоский список

Данные в InnoDB хранятся страницами по 16 Кб. Размер одной страницы — это предельный размер узла нашей древовидной структуры, от которого зависит в какой момент начнётся ветвление. Если вся таблица помещается в одну страницу, то она хранится в виде плоского списка, отсортированного по ключевому полю, без отдельной индексной таблицы.

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

Второй этап: дерево

Когда данные перестают помещаться в одну страницу, список превращается в дерево. Страница с данными разделяется на две, причём в том узле (на той странице), где раньше были данные, теперь располагается индекс, охватывающий обе новые страницы. Конкретный узел такого дерева обязан включать в себя индексы всех дочерних узлов или конечные данные, если узел последний. Узлы могут ссылаться друг на друга только в одном направлении: от родителя к потомку.

По мере добавления всё новых и новых данных, дерево будет усложняться и углубляться. И чем больше оно будет и ветвистее, тем больший выйгрышь даст такая схема хранения данны.

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

Вспомним наш запрос (зелёная стрелка):

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

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

Здесь действует простое правило, актуальное для любого типа индекса: чем разнообразнее данные, тем эффективнее использовать индекс для поиска конкретных значений.

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

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

Кластерные ключи в InnoDB

Здесь всё просто. Каждая таблица InnoDB имеет кластерный ключ. Каждая. Без исключения.

Гораздо интереснее, какие поля для этого выбираются.

До третьего пункта лучше не доводить свой многострадальный сервер, и добавить таки ID самостоятельно.

И не забывайте, что InnoDB во вторичных ключах хранит полный набор значений полей кластерного ключа в качестве ссылки на конечную строку в таблице. Чем больше первичный ключ, тем больше вторичные ключи.

Источник

Описание кластеризованных и некластеризованных индексов

Таблица или представление может иметь индексы следующих типов.

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

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

Вы можете добавить неключевые столбцы на конечный уровень некластеризованного индекса, чтобы обойти существующее ограничение на ключи индексов и выполнять полностью индексированные запросы. Дополнительные сведения см. в статье Создание индексов с включенными столбцами. Дополнительные сведения об ограничениях на ключи индексов см. в статье Спецификации максимально допустимых параметров SQL Server.

Как кластеризованные, так и некластеризованные индексы могут быть уникальными. Это означает, что никакие две строки не имеют одинаковое значение для ключа индекса. В противном случае индекс не является уникальным, и несколько строк могут содержать одно и то же значение. Дополнительные сведения см. в статье Создание уникальных индексов.

Обслуживание индексов таблиц и представлений происходит автоматически при любом изменении данных в таблице.

Индексы и ограничения

Индексы создаются автоматически при определении ограничений PRIMARY KEY или UNIQUE на основе столбцов таблицы. Например, при создании таблицы с ограничением UNIQUE Компонент Database Engine автоматически создает некластеризованный индекс. При настройке PRIMARY KEY Компонент Database Engine автоматически создает кластеризованный индекс, если он еще не существует. Если вы пытаетесь применить ограничение PRIMARY KEY в существующей таблице, для которой уже создан кластеризованный индекс, SQL Server применяет первичный ключ с помощью некластеризованного индекса.

Как оптимизатор запросов использует индексы

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

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

Дополнительные сведения о правилах и принципах проектирования индексов см. в статье Руководство по проектированию индексов SQL Server.

Источник

18) Кластерный против некластеризованного индекса

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

Индекс — это ключ, построенный из одного или нескольких столбцов в базе данных, который ускоряет выборку строк из таблицы или представления. Этот ключ помогает базе данных, такой как Oracle, SQL Server, MySQL и т. Д., Быстро найти строку, связанную со значениями ключа.

В этом уроке вы узнаете:

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

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

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

Что такое некластеризованный индекс?

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

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

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

Характеристика кластерного индекса

Характеристики некластеризованных индексов

Пример кластерного индекса

В приведенном ниже примере SalesOrderDetailID является кластеризованным индексом. Пример запроса для получения данных

Пример некластеризованного индекса

В следующем примере некластеризованный индекс создается для OrderQty и ProductID следующим образом

Следующий запрос будет получен быстрее по сравнению с кластерным индексом.

Различия между кластерным индексом и некластеризованным индексом

Преимущества кластерного индекса

Плюсы / преимущества кластерного индекса:

Преимущества некластеризованного индекса

Плюсы использования некластеризованного индекса:

Недостатки кластерного индекса

Вот минусы / недостатки использования кластерного индекса:

Недостатки некластеризованного индекса

Вот минусы / недостатки использования некластеризованного индекса:

Источник

Повесть о кластеризованном индексе

После перехода на SQL Server с Oracle удивляет многое. Трудно привыкнуть к автоматическим транзакциям – после update не нужно набирать commit (что приятно), зато в случае ошибки не сможешь набрать rollback (что просто кошмарно). Трудно привыкнуть к архитектуре, в которой журнал используется и для отката, и для наката транзакций. Трудно привыкнуть к ситуации «писатель блокирует читателей, читатель блокирует писателей», а когда привыкнешь – ещё труднее отвыкнуть. И совсем не последнее место в рейтинге трудностей играет засилье кластеризованных индексов. По умолчанию первичный ключ таблицы – именно кластеризованный индекс, и поэтому почти у всех таблиц он есть.

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

Файлы, страницы, RID

Данные любой таблицы физически сохранены в файле базы данных. Файл БД делится на страницы (page) – логические единицы хранения для сервера. Страница в MS SQL Server обязательно имеет размер 8 килобайт (8192 байта), из них под данные отдано 8060 байт. Для каждой строки можно указать её физический адрес, так называемый Row ID (RID): в каком файле она находится, в какой по порядку странице этого файла, в каком месте страницы. Страницу таблица присваивает целиком – на одной странице могут быть данные только одной таблицы. Более того, при необходимости считать/записать строку сервер считывает/записывает всю страницу, поскольку так получается гораздо быстрее.

Как устроен B-tree индекс?

B-tree означает balanced tree, «сбалансированное дерево». Индекс содержит ровно одну корневую страницу, которая является точкой входа для поиска. Корневая страница содержит значения ключей и ссылки на страницы следующего уровня для данных значений индекса. При поиске по индексу находится последнее значение, которое не превосходит искомое, и происходит переход на соответствующую страницу. На последнем, листьевом уровне дерева перечислены все ключи, и для каждого из них указана ссылка (bookmark) на данные таблицы. Естественным кандидатом на роль ссылки является RID, и он в самом деле используется в этом качестве для случая кучи. На следующем рисунке буквы B обозначают ссылки на строки таблицы.

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

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

Куча мала

Рассмотрим некоторую модельную таблицу, организованную в виде кучи: какого-то определённого порядка в записях нет.
RID, который запись получает в самом начале, остаётся с ней почти всегда. В редких случаях записи в куче могут перемещаться на другую страницу – это происходит, когда после обновления строка перестаёт помещаться на то место, которое она занимала. Но в таком случае на прежнем месте остаётся ссылка на новое размещение – то есть, зная RID, полученный строкой при добавлении, строку можно найти всегда. Поэтому для индексов на куче наилучший выбор для ссылки на данные – именно RID.

Предположим, в таблице 200 тысяч записей, и в каждую страницу помещается от 48 до 52 записей. Будем считать, что таблица занимает 4000 страниц. Допустим, нам нужно найти все записи, в которых поле [City] имеет значение ‘Perm’. Также допустим, что их всего 3, но мы об этом пока не знаем.

Серверу придётся просканировать все 4000 страниц. Даже если сервер найдёт все 3 записи, ему всё равно придётся идти до конца – ведь нет гарантии, что больше нужных записей нет. Итак, для выполнения запроса понадобится 4000 логических чтений страницы.
А если у нас есть индекс, в котором можно искать двоичным поиском – скажем, дерево высоты 3? Тогда серверу потребуется 3 чтения индексных страниц для того, чтобы найти адрес первой записи. Адреса второй и третьей записей будут лежать рядом – либо в той же странице, либо в следующей: страницы индекса по горизонтали соединены ссылками. То есть после максимум 4 чтений сервер наверняка знает RID всех трёх записей. Если сильно не повезёт, все 3 записи лежат в разных страницах. Таким образом, при наличии индекса после 7 логических чтений страницы все 3 записи наверняка будут найдены. 7 против 4000 – впечатляет.

Но так хорошо будет, когда записей мало. А если это не ‘Perm’, а ‘Moscow’, и нужных записей не 3, а 20 тысяч? Это не очень много, всего 10 процентов от общего количества записей. Но картина быстро становится не столь радужной.

За 3 чтения сервер найдёт первую запись. А затем ему потребуется считать 20 тысяч RID и 20 тысяч раз прочитать страницу, чтобы получить строку: мы помним, что сервер читает данные только целыми страницами. Вполне может получиться так, что нужные записи рассеяны по всей таблице, и для обеспечения 20 тысяч логических чтений потребуется считать большую часть страниц с диска. Ещё хорошо, если не все. Вместо 4 тысяч логических чтений мы получаем 20 тысяч.

Индекс очень хорошо работает на поиске небольшого количества значений, но плохо работает на прохождении больших диапазонов.

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

А как же быть с диапазонами?

Проблема именно в том, что в конце поиска по индексу сервер получает не данные, а только адрес, по которому они лежат. Серверу ещё нужно идти по этому адресу и брать данные оттуда. Вот было бы здорово, если бы в конце пути сразу лежали данные!
Некоторые, собственно, и лежат. Значения ключей, например, лежат именно в индексе – за ними идти не нужно. Только за неключевыми полями. А что будет, если неключевые поля тоже положить в индекс? Ну допустим, не все, а только те, которые нужны сканирующему запросу?

А будет в таком случае индекс с добавочными (included) столбцами. Он проигрывает обычному индексу по размеру: его листьевые страницы содержат не только ключи и адреса строк, но и часть данных. В поиске одиночного значения такой индекс работает не хуже, а в сканировании диапазонов – намного, намного лучше. Если индекс покрывает запрос (то есть содержит все столбцы, перечисленные в запросе), то для выполнения запроса таблица не нужна вообще. Возможность взять все требуемые данные из индекса, не обращаясь к закладкам, даёт громадный выигрыш.

Вернёмся к нашему модельному примеру. Предположим, что требуемые для запроса столбцы включены в индекс. Для простоты предположим, что в листьевую страницу индекса попадают ровно 50 записей (ключи, добавленные столбцы, ссылки на записи). Тогда сканирование 20 тысяч записей потребует чтения всего лишь 400 страниц индекса – вместо 20 тысяч логических чтений для непокрывающего индекса.

400 против 20 тысяч – разница в 50 раз. Оптимизатор запросов недаром любит предлагать включить в индекс те или иные столбцы.
А может, стоит добавить в индекс все столбцы? Тогда любой запрос будет покрыт индексом обязательно. Более того, тогда в листьях даже не нужны RID, потому что ни за какими данными такой индекс не будет обращаться в таблицу, у него всё под рукой. Да в таком случае становится не нужна и сама таблица!

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

Где подвох?

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

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

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

Представим себе сканирование диапазона в 20 тысяч записей по некластеризованному индексу, построенному на кластеризованном. Теперь понадобится выполнить не 20 тысяч логических чтений страницы по известному RID, а 20 тысяч поисков в кластеризованном индексе – и каждый поиск потребует 3, а то и более, логических чтений.

А если ключ кластеризованного индекса не уникален? А так не бывает. Для сервера он обязательно уникален. Если пользователь попросил создать неуникальный кластеризованный индекс, сервер к каждому ключу припишет 4-байтовое целое число, которое обеспечит уникальность ключа. Делается это прозрачно для пользователей: сервер не только не сообщает им точного значения числа, но и не выдаёт сам факт его наличия. Уникальность ключа нужна именно для возможности однозначной идентификации записей – чтобы ключ кластеризованного индекса мог служить адресом строки.

Так делать или не делать?

Вооружённые теорией, мы можем описать рациональную процедуру построения кластеризованного индекса. Следует выписать все индексы, которые нужны таблице, и выбрать из них кандидата на кластеризацию.
Не нужно делать кластеризованный индекс только для того, чтобы он был. Если по ключу индекса не предполагается сканирование – это не очень хороший кандидат для кластеризации (если по другим индексам сканирование предполагается – то даже очень плохой кандидат). Неправильный выбор кандидата на кластеризацию ухудшит производительность, потому что все остальные индексы станут работать хуже, чем работали на куче.

Предлагается следующий алгоритм выбора:

Постскриптум. Почему он единственный?

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

Кластеризованный индекс, во-первых, содержит все данные в листьевых вершинах, а во-вторых, не содержит никаких ссылок на данные таблицы (потому что никакой внешней по отношению к нему таблицы нет). Ну и что мешает завести несколько так устроенных индексов – содержащих все поля и не содержащих ссылки? Я не знаю. Могу только предложить.

Прежде всего – мы же можем завести сколько угодно индексов, в которые будут включены все поля. Значит, весь выигрыш, который нам сулит наличие нескольких кластеризованных индексов, относительно невелик: на листьевом уровне добавочных индексов не будет ссылок на данные, то есть мы сэкономим немного места. А какие проблемы повлечёт за собой создание нескольких кластеризованных индексов?

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

Источник