Индексы в базах данных: краткий обзор

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

Принцип работы

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

Виды индексов

Кластерный

• Определяет порядок физического хранения данных на диске, упорядочивая строки таблицы по значениям индекса.
• Строки фактически упорядочиваются на диске в соответствии со значениями кластерного индекса.
• Может быть создан только для одного столбца.

Некластерный

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

Эффективность индексов

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

1. Существенно ускоряют запросы к таблицам с большим объемом данных, особенно при использовании WHERE.
2. Облегчают сортировку данных, полезно при запросах ORDER BY.
3. Могут гарантировать уникальность значений в столбцах (используя уникальные индексы по нескольким столбцам).
4. Оптимизируют JOIN-операции.

Недостатки

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

Основные алгоритмы индексирования

B-Tree (Дерево поиска)

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

Hash-Индекс

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

GiST (Generalized Search Tree)

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

Bitmap-индекс

• Использует битовые карты для обозначения наличия значения.
• Каждый бит представляет уникальное значение или диапазон.
• Эффективен для данных с ограниченным количеством уникальных значений, также для баз данных, где много операций чтения, но мало обновлений/вставок. Часто используется в ситуациях с булевыми значениями.

Full-Text-Индекс

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

Процесс создания индекса

1. Определение столбцов в таблице для индексации. Обычно те, что чаще всего используются в запросах или поисках.
2. Выбор алгоритма индексирования.
3. Применение алгоритма: создается структура данных, сопоставляющая значения в столбцах с местоположениями соответствующих записей таблицы.
4. Сохранение индекса в отдельной структуре данных. Обычно в другой части диска или в памяти.
5. Обновление индекса в случае изменения записей.

Статьи

1. Индексы простым языком на примере
2. Индексы для оптимизации SQL-запросов
3. Типы индексов
4. Подробнее про алгоритмы индексации
5. Насущные вопросы про индексы
6. Примеры алгоритмов индексации и как работают
7. Влияние индексов на производительность БД
8. О типах индексов SQL
9. Обзор типов индексов Oracle, MySQL, PostgreSQL, MS SQL

Видео

1. Коротко об SQL индексах
2. Про индексы кратко
3. Базы данных. Индексы и производительность
4. Индексы в PostgreSQL
5. Структура индексов SQL
6. Подробнее об индексах