Как хранится индекс в БД?

Как хранятся индексы в базах данных

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

Основные структуры хранения индексов

B9-деревья и B+-деревья

Наиболее распространённая структура для индексов в реляционных БД (PostgreSQL, MySQL, SQL Server, Oracle). B+-деревья — это сбалансированные деревья поиска, где:

• Все ключи хранятся в листовых узлах
• Внутренние узлы содержат ключи для навигации
• Листовые узлы связаны в односвязный список для быстрого диапазонного поиска

-- Пример создания индекса в SQL
CREATE INDEX idx_users_email ON users(email);

В физическом хранилище B+-дерево состоит из страниц (обычно 4-16 КБ), которые соответствуют узлам дерева. Каждая страница содержит:

• Заголовок страницы (метаданные)
• Массив ключей и указателей
• Свободное пространство для вставок

Хеш-индексы

Используются для точечного поиска (точное совпадение). Принцип:

• Ключ преобразуется хеш-функцией в номер бакета
• В бакете хранятся ссылки на строки данных

// Пример работы хеш-RGдекса
int bucketIndex = GetHashCode(key) % totalBuckets;
var records = buckets[bucketIndex].Find(key);

Bitmap1-индексы

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

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

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

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

-- Кластеризованный индекс в SQL Server
CREATE CLUSTERED INDEX idx_users_id ON users(id);

Особенности:

• Таблица может иметь только один кластеризованный индекс
• Данные хранятся в порядке ключа индекса
• Листовые узлы содержат сами строки данных

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

Отдельная структура, которая хранит ключи и указатели на данные.

-- Некластеризованный индекс
CREATE NONCLUSTERED INDEX idx_users_lastname ON users(last_name);

Структура:

• Для таблиц с кластеризованным индексом — содержит ключ кластеризованного индекса
• Для таблиц без кластеризованного индекса (куча) — содержит физический адрес строки

Внутреннее устройство страниц индекса

Типичная страница индекса (8 КБ в SQL Server):

| Заголовок страницы (96 байт) | Массив слотов | Данные индекса | Свободное пространство |

Заголовок содержит:

• ID страницы
• Указатель на следующую/предыдущую страницу
• Уровень страницы в дереве
• Количество записей

Записи индекса содержат:

• Ключевые значения
• Для некластеризованных индексов — ключ кластеризованного индекса или RID
• Метаданные (флаги, размер)

Особенности хранения в разных СУБД

PostgreSQL

Использует B9-деревья с дополнительными оптимизациями:

• Индексы хранятся в отдельных файлах
• Поддержка частичных индексов (WHERE в CREATE INDEX)
• Расширяемая архитектура (GIN, GiST для полнотекстового поиска)

MySQL (InnoDB)

• Кластеризованный индекс по первичному ключу
• Вторичные индексы ссылаются на первичный ключ
• Адаптивный хеш-индекс в памяти для горячих данных

SQL Server

• Разделение на страницы по 8 КБ
• Файловые группы для распределения по дискам
• Columnstore-индексы для аналитических запросов

Оптимизации и современные тенденции

1. Columnstore-индексы — хранение данных по столбцам, а не строкам
2. Индексы в памяти — хеш- и диапазон-индексы для таблиц в оперативной памяти
3. Покрывающие индексы (covering indexes) — включение всех необходимых столбцов в индекс
4. Фильтрованные индексы — индексы только для части данных

-- Покрывающий индекс
CREATE INDEX idx_users_covering ON users(last_name) INCLUDE (first_name, email);

Влияние на производительность

Положительное:

• Ускорение поиска с O(n) до O(log n)
• Ускорение сортировки и группировки
• Возможность использования только индекса (index-only scan)

Отрицательное:

• Замедление INSERT/UPDATE/DELETE
• Дополнительное дисковое пространство
• Сложность выбора оптимальных индексов

Рекомендации по проектированию:

1. Индексируйте столбцы в WHERE, JOIN, ORDER BY
2. Используйте составные индексы для часто используемых комбинаций
3. Избегайте избыточных индексов
4. Регулярно проводите обслуживание (перестроение, реорганизация)

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