Кластеризованный индекс¶

Кластеризованный индекс (англ. clustered index) — это тип индекса базы данных, который определяет физический порядок хранения строк таблицы на диске. В отличие от некластеризованного индекса, который создаёт отдельную структуру, содержащую ссылки на строки, кластеризованный индекс перестраивает саму таблицу таким образом, что её строки располагаются в порядке, соответствующем ключу индекса. Таблица может иметь только один кластеризованный индекс, поскольку данные могут быть отсортированы только одним способом.

¶История и происхождение

Концепция кластеризованных индексов возникла в рамках развития реляционных баз данных в 1970-х годах. Одним из первых систем, реализовавших эту идею, стала СУБД System R, разработанная в исследовательском центре IBM. В её документации 1976 года впервые было предложено различать индексы, которые хранят данные в упорядоченном виде (clustered), и те, которые хранят только указатели (non-clustered). В 1980-х годах кластеризованные индексы стали стандартной функцией коммерческих СУБД, таких как IBM DB2, Microsoft SQL Server (с версии 4.2 в 1993 году) и Oracle Database (с версии 7.0 в 1992 году, где они называются index-organized tables). В открытых системах, таких как PostgreSQL, кластеризованные индексы реализованы как временная операция (CLUSTER), а не постоянное свойство таблицы, что отличает их от подходов Microsoft SQL Server и MySQL (InnoDB).

¶Устройство и принцип работы

¶Физическая организация

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

В СУБД MySQL (движок InnoDB) кластеризованный индекс является обязательным: если таблица не имеет явно заданного первичного ключа, InnoDB автоматически создаёт скрытый кластеризованный индекс на основе уникального идентификатора (ROWID). В Microsoft SQL Server кластеризованный индекс необязателен: таблица может быть кучей (heap) без какого-либо индекса, либо иметь кластеризованный индекс.

¶Сортировка и вставка

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

¶Сравнение с некластеризованным индексом

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

¶Преимущества

• Быстрый поиск по диапазону: поскольку строки физически упорядочены, запросы с условиями BETWEEN, >, <, ORDER BY по ключу индекса выполняются очень эффективно — достаточно прочитать последовательный блок страниц.
• Снижение числа операций ввода-вывода: для запросов, возвращающих много строк, кластеризованный индекс уменьшает количество обращений к диску, так как данные находятся рядом.
• Эффективность для операций JOIN: если ключ соединения совпадает с ключом кластеризованного индекса, слияние (merge join) выполняется быстро.

¶Недостатки

• Низкая производительность вставок: каждая вставка требует перестроения B-дерева, что особенно заметно при вставке в середину диапазона (например, при использовании GUID в качестве ключа).
• Фрагментация: при частых вставках и обновлениях страницы данных могут фрагментироваться, что снижает производительность сканирования.
• Ограничение на один индекс: невозможно оптимизировать два разных порядка сортировки одновременно.
• Затраты на перестроение: при изменении ключа кластеризованного индекса (например, при смене первичного ключа) требуется перестроение всей таблицы.

¶Области применения

¶Оптимальные сценарии

• Таблицы с частыми запросами по диапазону: например, таблицы логов, где данные часто запрашиваются по дате.
• Таблицы с последовательным доступом: например, таблицы с идентификаторами, которые генерируются по возрастанию (IDENTITY, AUTO_INCREMENT).
• Таблицы с малым числом обновлений: где данные вставляются редко, но часто читаются.

¶Неоптимальные сценарии

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

¶Реализации в различных СУБД

¶Microsoft SQL Server

Кластеризованный индекс создаётся по умолчанию при определении первичного ключа, если не указано NONCLUSTERED. Можно создать кластеризованный индекс на любом столбце или комбинации столбцов, включая уникальные и неуникальные. В SQL Server 2014 и новее поддерживается кластеризованный columnstore-индекс, предназначенный для аналитических нагрузок.

¶MySQL (InnoDB)

В движке InnoDB кластеризованный индекс является обязательным. Если таблица имеет первичный ключ, он используется как кластеризованный индекс. Если первичного ключа нет, InnoDB выбирает первый уникальный индекс, где все столбцы не NULL. Если такого индекса нет, создаётся скрытый кластеризованный индекс (GEN_CLUST_INDEX) на основе 6-байтового идентификатора строки.

¶PostgreSQL

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

¶Oracle Database

В Oracle кластеризованные индексы реализованы как index-organized tables (IOT). В таких таблицах данные хранятся в B-дереве, как в кластеризованном индексе. IOT особенно эффективны для таблиц с частым доступом по первичному ключу и для таблиц-справочников.

¶Критика и альтернативы

Основная критика кластеризованных индексов связана с их влиянием на производительность вставок и обновлений. В системах с высокой нагрузкой на запись (OLTP) кластеризованные индексы могут стать узким местом. Альтернативой является использование некластеризованных индексов в сочетании с кучей (heap) или использование хеш-индексов, которые не требуют сортировки данных. В современных СУБД, таких как SQL Server 2016+, появились индексы с оптимизацией для вставок (например, clustered columnstore с batch mode), которые частично решают эту проблему.

¶Интересные факты

• В Microsoft SQL Server кластеризованный индекс может быть создан на основе вычисляемого столбца (computed column), если он определён как PERSISTED.
• В MySQL (InnoDB) вторичные индексы (некластеризованные) содержат не указатели на строки, а значения первичного ключа кластеризованного индекса. Это означает, что поиск по вторичному индексу требует двух обращений: сначала к вторичному индексу, затем к кластеризованному.
• В некоторых СУБД (например, IBM DB2) кластеризованный индекс может быть не уникальным, что позволяет хранить несколько строк с одинаковым ключом.

¶Источники

• Microsoft Learn: Clustered and Nonclustered Indexes Described
• MySQL 8.0 Reference Manual: Clustered and Secondary Indexes
• PostgreSQL Documentation: CLUSTER
• Oracle Database Concepts: Index-Organized Tables
• Ramakrishnan, R., Gehrke, J. Database Management Systems (3rd ed.). McGraw-Hill, 2003.