Автор оригинала: Vlad Mihalcea.
Вступление
В этой статье мы рассмотрим, что такое кластеризованный индекс и почему очень важно понимать, как организованы таблицы при использовании системы реляционных баз данных.
B+ Дерево
Наиболее распространенным индексом, используемым в системе реляционных баз данных, является B+ Дерево . Как и индекс B-Tree , дерево B+ представляет собой самобалансированную упорядоченную древовидную структуру данных.
И B-Дерево, и B-Дерево начинаются с Корневого узла и могут иметь Внутренние Узлы и Конечные узлы. Однако, в отличие от B-дерева, дерево B+ хранит все ключи в конечных узлах, а соседние конечные узлы связаны указателями, что упрощает сканирование диапазона.
Без индекса всякий раз, когда мы ищем заданное значение столбца, нам нужно будет сканировать все записи таблицы и сравнивать каждое значение столбца с предоставленным. Чем больше таблица, тем больше страниц потребуется отсканировать, чтобы найти все соответствующие записи.
С другой стороны, если значение столбца очень избирательно (например, небольшое количество записей соответствует значению столбца), использование индекса дерева B+позволяет нам найти значение столбца намного быстрее, так как для сканирования потребуется меньше страниц.
Кластеризованный индекс
Кластеризованный индекс-это в основном древовидная таблица. Вместо хранения записей в несортированном табличном пространстве кучи кластеризованный индекс в основном представляет собой индекс дерева B+с первичным ключом, конечные узлы которого, упорядоченные по значению столбца ключа кластера, хранят фактические записи таблицы, как показано на следующей диаграмме.
Кластеризованный индекс-это структура таблиц по умолчанию в SQL Server и MySQL. В то время как MySQL добавляет индекс скрытых кластеров, даже если таблица не имеет первичного ключа, SQL Server всегда создает кластеризованный индекс, если таблица содержит столбец первичного ключа. В противном случае SQL Server хранится в виде таблицы кучи.
Кластеризованный индекс может ускорить запросы, которые фильтруют записи по ключу кластеризованного индекса, как обычные операторы CRUD. Поскольку записи расположены в Конечных узлах, при поиске записей по значениям первичного ключа не требуется дополнительный поиск дополнительных значений столбцов.
Например, при выполнении следующего SQL-запроса на SQL Server:
SELECT PostId, Title FROM Post WHERE PostId = ?
Вы можете видеть, что План выполнения использует операцию поиска кластеризованного индекса для поиска конечного узла, содержащего запись Post
, и для сканирования узлов кластеризованного индекса требуется только два логических чтения:
|StmtText | |-------------------------------------------------------------------------------------| |SELECT PostId, Title FROM Post WHERE PostId = @P0 | | |--Clustered Index Seek(OBJECT:([high_performance_sql].[dbo].[Post].[PK_Post_Id]), | | SEEK:([high_performance_sql].[dbo].[Post].[PostID]=[@P0]) ORDERED FORWARD) | Table 'Post'. Scan count 0, logical reads 2, physical reads 0
Кластеризованный и вторичный индекс
Поскольку кластеризованный индекс создается с использованием значений столбца первичного ключа, если вы хотите ускорить запросы, использующие какой-либо другой столбец, вам придется добавить вторичный индекс.
Вторичный индекс будет хранить значение Первичного ключа в своих Конечных узлах, как показано на следующей диаграмме:
Итак, если мы создадим Вторичный индекс в столбце Title
таблицы Post
:
CREATE INDEX IDX_Post_Title on Post (Title)
И мы выполняем следующий SQL-запрос:
SELECT PostId, Title FROM Post WHERE Title = ?
Мы видим, что операция поиска по индексу используется для поиска конечного узла в индексе IDX_Post_Title
, который может предоставить интересующую нас проекцию SQL-запроса:
|StmtText | |------------------------------------------------------------------------------| |SELECT PostId, Title FROM Post WHERE Title = @P0 | | |--Index Seek(OBJECT:([high_performance_sql].[dbo].[Post].[IDX_Post_Title]),| | SEEK:([high_performance_sql].[dbo].[Post].[Title]=[@P0]) ORDERED FORWARD)| Table 'Post'. Scan count 1, logical reads 2, physical reads 0
Поскольку связанное значение столбца postID
Первичного ключа хранится в узле IDX_Post_Title
Leaf, этому запросу не требуется дополнительный поиск для поиска строки Post
в кластеризованном индексе.
С другой стороны, если SQL-запрос, использующий Вторичный индекс, возвращает проекцию, для которой требуются дополнительные значения столбцов, не расположенные в Конечном узле Вторичного индекса, то также необходимо будет пройти Кластеризованный индекс. В SQL Server этот процесс называется Поиском закладок .
Итак, если мы выполним SQL-запрос, который считывает , созданный в
столбце, который не включен в IDX_Post_Title
Вторичный индекс:
SELECT PostId, CreatedOn FROM Post WHERE Title = ?
Мы видим , что сначала используется операция поиска индекса для поиска конечного узла в индексе IDX_Post_Title
, который соответствует предоставленному Заголовку
, а затем Кластеризованный поиск индекса для поиска конечного узла, в котором находится запись Post
, чтобы мы могли прочитать значение столбца CreatedOn
:
|StmtText | |----------------------------------------------------------------------------------------------| |SELECT PostId, CreatedOn FROM Post WHERE Title = @P0 | | |--Nested Loops(Inner Join, OUTER REFERENCES:([high_performance_sql].[dbo].[Post].[PostID]))| | |--Index Seek(OBJECT:([high_performance_sql].[dbo].[Post].[IDX_Post_Title]), | | SEEK:([high_performance_sql].[dbo].[Post].[Title]=[@P0]) ORDERED FORWARD) | | |--Clustered Index Seek(OBJECT:([high_performance_sql].[dbo].[Post].[PK_Post_Id]), | | SEEK:([high_performance_sql].[dbo].[Post].[PostID]= | | [high_performance_sql].[dbo].[Post].[PostID]) LOOKUP ORDERED FORWARD) | Table 'Post'. Scan count 1, logical reads 4, physical reads 0
И, поскольку обходятся как Вторичный индекс, так и Кластеризованный индекс, на этот раз требуется 4 логических чтения.
По этой причине некоторые системы реляционных баз данных, такие как SQL Server, предоставляют предложение INCLUDE
для добавления дополнительных значений столбцов в конечные узлы вторичного индекса, чтобы избежать накладных расходов на поиск закладок.
В нашем случае мы можем изменить IDX_Post_Title
Индекс для включения столбца CreatedOn
, как это:
CREATE NONCLUSTERED INDEX IDX_Post_Title ON Post (Title) INCLUDE (CreatedOn);
И, при выполнении предыдущего SQL-запроса:
SELECT PostId, CreatedOn FROM Post WHERE Title = ?
План выполнения изменяется на поиск по одному индексу в IDX_Post_Title
Вторичном индексе, поскольку больше нет необходимости пересекать кластеризованный индекс, чтобы найти столбец CreatedOn
:
|StmtText | |------------------------------------------------------------------------------| |SELECT PostId, CreatedOn FROM Post WHERE Title = @P0 | | |--Index Seek(OBJECT:([high_performance_sql].[dbo].[Post].[IDX_Post_Title]),| | SEEK:([high_performance_sql].[dbo].[Post].[Title]=[@P0]) ORDERED FORWARD)| Table 'Post'. Scan count 1, logical reads 2, physical reads 0
Размер столбца кластеризованного индекса
Поскольку ключ Кластеризованного индекса хранится в каждом Вторичном индексе, очень важно, чтобы столбец Первичного ключа был как можно более компактным.
Например, если у вас есть таблица Сотрудник
, нет необходимости использовать столбец bigint
в качестве первичного ключа, поскольку столбец int
может содержать более 4 миллиардов записей, и очень маловероятно, что в компании, которую вы моделируете, будет более 4 миллиардов сотрудников.
Поскольку для значения столбца int
требуется 4 байта памяти, в то время как для bigint
требуется 8 байт, вы сэкономите много места как в кластеризованном индексе, так и во всех связанных вторичных индексах.
Использование наиболее компактных типов столбцов, которые все еще могут вместить все возможные значения, еще более важно, когда вы думаете о пуле буферов. Без кэширования рабочего набора в памяти для запросов потребуется большой доступ к диску, что на порядки медленнее, чем оперативная память.
Монотонность столбцов кластеризованного индекса
Поскольку индексы дерева B+являются самобалансированными, важно выбрать столбец первичного ключа, значения которого монотонно возрастают по многим веским причинам.
Во-первых, Конечный узел может вместить несколько записей, и добавление каждой записи одной за другой обеспечит высокий коэффициент заполнения страницы и низкое количество страниц, необходимых для хранения всех записей. С другой стороны, если вы используете столбец первичного ключа UUID, новое значение UUID может не найти ни одной существующей конечной страницы, поэтому все больше и больше конечных страниц будут выделяться и заполняться только частично.
Во-вторых, как объяснено в этой статье Percona вставка записей кластеризованного индекса в случайном порядке может привести к многочисленным разделениям страниц, что требует дополнительной работы по обслуживанию индекса от компонента database engine.
В-третьих, если Кластеризованный индекс очень велик и не полностью помещается в памяти, очень удобно использовать монотонно увеличивающиеся значения Первичного ключа, поскольку вероятность нахождения страницы, кэшированной в Буферном пуле, выше, чем если бы значение Первичного ключа было сгенерировано случайным образом и связанный Конечный узел был удален из Буферного пула.
Вывод
Понимание того, как работает кластеризованный индекс, очень важно, если вы используете MySQL или SQL Server, поскольку это структура данных таблицы по умолчанию.
Выбор монотонно увеличивающегося ключа кластеризованного индекса, который также достаточно компактен, обеспечит лучшую производительность, чем использование случайно распределенных значений столбцов, как в случае столбцов UUID.
Кроме того, для SQL Server, если вы хотите избежать поиска закладок, вы можете использовать предложение INCLUDE
при определении некластеризованного индекса, предназначенного для обслуживания определенного набора запросов, для которых требуются дополнительные столбцы, не используемые для фильтрации.