Локальный вторичный индекс

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

История и предпосылки появления

Концепция локальных индексов возникла как эволюция традиционных индексов реляционных баз данных (например, B-деревьев в Oracle или SQL Server) в контексте распределённых систем. В классических монолитных СУБД все индексы были локальными по умолчанию, так как данные хранились на одном сервере. С переходом к шардированию (сегментированию) и распределённым архитектурам (NoSQL-системы, NewSQL) возникла проблема: глобальные индексы требуют синхронизации между узлами, что снижает производительность записи и увеличивает задержки.

Первые реализации локальных вторичных индексов появились в системах, ориентированных на высокую доступность и горизонтальное масштабирование, таких как Apache Cassandra (около 2010 года) и MongoDB (с версии 2.0). В этих системах локальные индексы стали компромиссом между скоростью записи и возможностью фильтрации данных по неключевым полям.

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

Архитектура

Локальный вторичный индекс хранится на том же узле (шарде), что и соответствующие строки данных. Каждый узел владеет определённым диапазоном первичных ключей (или хешей), и для этих данных строится собственный индекс по указанному вторичному полю. Индекс может быть реализован в виде B-дерева, хеш-таблицы или LSM-дерева (Log-Structured Merge-tree) — в зависимости от СУБД.

Процесс создания и обновления

1. Создание: администратор базы данных выполняет команду CREATE INDEX с указанием ключа индекса (например, CREATE INDEX idx_status ON orders(status) USING LOCAL). СУБД сканирует данные на каждом узле и строит индекс локально.
2. Обновление: при вставке, обновлении или удалении строки на узле индекс на этом же узле обновляется атомарно в рамках той же транзакции (если СУБД поддерживает транзакции на уровне узла). Никаких сообщений другим узлам не отправляется.
3. Поиск: запрос с условием по индексированному полю отправляется на все узлы (или на один, если известно распределение данных). Каждый узел использует свой локальный индекс для быстрого поиска строк в своей части данных. Затем результаты агрегируются на координаторе запроса.

Отличия от глобального индекса

Классификация локальных вторичных индексов

По типу структуры данных

• B-дерево (B-Tree): классический сбалансированный индекс, используемый в PostgreSQL, MySQL (InnoDB), Oracle. Поддерживает эффективный поиск, вставку и удаление для произвольных диапазонов.
• LSM-дерево (Log-Structured Merge-tree): оптимизирован для высокой нагрузки на запись, используется в Cassandra, ScyllaDB, RocksDB. Индекс строится на основе сортированных файлов (SSTables), которые периодически сливаются.
• Хеш-индекс (Hash Index): обеспечивает поиск по точному равенству (например, WHERE id = 5). Используется в Memcached, Redis (как часть структур), но редко применяется для вторичных индексов из-за невозможности диапазонных запросов.
• Битовый индекс (Bitmap Index): эффективен для полей с малым количеством уникальных значений (пол, статус заказа). Применяется в аналитических СУБД (ClickHouse, Oracle).

По способу хранения

• Хранимый вместе с данными (clustered index): строки физически упорядочены по индексированному полю. В распределённых системах встречается редко, так как усложняет шардирование.
• Некластеризованный (non-clustered index): индекс содержит только ключи и ссылки на строки (row pointers или primary keys). Большинство локальных вторичных индексов в NoSQL-системах являются некластеризованными.

Применение в различных СУБД

Apache Cassandra

В Cassandra локальный вторичный индекс (Local Secondary Index, LSI) создаётся на одном узле для данных, хранящихся в определённом диапазоне партиций. Индекс реализован на основе хранилища SSTable и использует LSM-дерево. Запрос с использованием LSI (SELECT * FROM orders WHERE status = 'shipped') отправляется на все узлы, которые параллельно сканируют свои индексы. Это подходит для небольших наборов данных (до нескольких тысяч записей на партицию), но неэффективно для больших объёмов из-за полного сканирования кластера.

MongoDB

MongoDB поддерживает локальные индексы на уровне коллекции. Индекс создаётся для всех документов в коллекции на одном шарде (если используется шардирование). При запросе с использованием локального индекса MongoDB отправляет запрос на все шарды (broadcast), каждый шард использует свой индекс, и результаты объединяются. Это стандартное поведение для вторичных индексов в MongoDB, если не включён глобальный индекс (доступен в MongoDB Atlas).

Amazon DynamoDB

DynamoDB предоставляет два типа вторичных индексов: локальные (Local Secondary Index, LSI) и глобальные (Global Secondary Index, GSI). LSI создаётся для одной партиции (partition key) и может иметь другой ключ сортировки (sort key). Он хранится на том же узле, что и основная таблица, и обновляется синхронно при записи. LSI позволяет выполнять запросы с условиями по вторичному ключу в пределах одной партиции без полного сканирования.

CockroachDB

CockroachDB — NewSQL-система, которая по умолчанию использует глобальные индексы, но поддерживает локальные индексы (через ключевое слово STORING или INCLUDE). Локальный индекс в CockroachDB — это индекс, который хранится в той же партиции (range), что и данные. Он не требует распределённых транзакций для обновления, что повышает производительность записи, но ограничивает область поиска одной партицией.

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

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

• Высокая производительность записи: обновление индекса происходит локально, без сетевого взаимодействия и распределённых транзакций. Это особенно важно для систем с высокой нагрузкой на запись (логи, события, IoT).
• Простота реализации: не требуется сложных протоколов согласования (2PC, Paxos, Raft) для поддержания консистентности индекса между узлами.
• Горизонтальное масштабирование: добавление нового узла не требует перестроения глобального индекса — каждый узел строит свой индекс независимо.
• Устойчивость к сбоям: при отказе одного узла теряется только его часть данных и индекса, остальные узлы продолжают работу.

Недостатки

• Низкая производительность чтения при широких запросах: запрос с фильтром по вторичному полю, который потенциально может находиться на любом узле, требует отправки запроса на все узлы (broadcast). Это приводит к линейному росту времени ответа с увеличением числа узлов.
• Неоднородность распределения данных: если данные распределены неравномерно (например, один пользователь имеет 90% заказов), то локальный индекс на одном узле будет перегружен, а на других — простаивать.
• Ограниченная поддержка сложных запросов: локальные индексы плохо подходят для JOIN-запросов, агрегаций по всему кластеру и запросов с множественными условиями.
• Сложность управления: администратору необходимо понимать, какие запросы будут использовать локальные индексы, чтобы избежать полного сканирования всех узлов.

Сравнение с альтернативами

Глобальный вторичный индекс (GSI)

GSI обеспечивает прямой доступ к данным по вторичному ключу без сканирования всех узлов, но требует распределённой координации при записи. В системах с высокой нагрузкой на запись (более 10 000 записей в секунду) GSI может стать узким местом из-за блокировок и сетевых задержек. Локальный индекс предпочтительнее для сценариев, где запись доминирует над чтением, а запросы по вторичному полю редки или ограничены одной партицией.

Полное сканирование (full scan)

Без индекса запрос по неключевому полю приводит к полному сканированию всех данных на всех узлах. Локальный индекс ускоряет этот процесс, так как каждый узел использует индекс для фильтрации своих данных, но всё равно требует отправки запроса на все узлы. Полное сканирование без индекса может быть в 10–100 раз медленнее.

Примеры использования

• Интернет-магазин: таблица заказов шардируется по user_id. Локальный индекс по полю status позволяет быстро найти все заказы одного пользователя с определённым статусом (например, «доставлен»), не сканируя все данные пользователя.
• Система мониторинга: таблица событий шардируется по host_id. Локальный индекс по полю event_type помогает фильтровать события на конкретном хосте (например, «error») без затрагивания других хостов.
• Социальная сеть: таблица постов шардируется по user_id. Локальный индекс по полю created_at позволяет получать посты пользователя за определённый период времени.

Критика и ограничения

Локальные вторичные индексы критикуются за неэффективность при запросах, которые требуют поиска по всему кластеру. В распределённых системах с большим числом узлов (более 10) broadcast-запросы с использованием локальных индексов могут приводить к значительному увеличению времени ответа и нагрузки на сеть. В таких случаях рекомендуется использовать глобальные индексы или денормализацию данных (материализованные представления).

Кроме того, локальные индексы не поддерживают уникальность на уровне кластера — уникальность может быть гарантирована только в пределах одного узла. Это ограничение делает их непригодными для полей, которые должны быть уникальными глобально (например, email пользователя).

Источники

• Cassandra: The Definitive Guide, Eben Hewitt, 2010.
• MongoDB: The Definitive Guide, Kristina Chodorow, 2013.
• Amazon DynamoDB Developer Guide, AWS Documentation, 2023.
• CockroachDB Documentation: Indexes, Cockroach Labs, 2024.
• Designing Data-Intensive Applications, Martin Kleppmann, 2017.
• «Distributed Systems: Principles and Paradigms», Andrew S. Tanenbaum, 2007.