Что такое индексация в базе данных?

Индексация — это процесс создания и поддержки специальных структур данных (индексов) в СУБД для значительного ускорения операций поиска (SELECT с WHERE), соединения (JOIN) и сортировки (ORDER BY). Индекс работает подобно алфавитному указателю в книге, позволяя быстро найти строки по значениям определенных столбцов, минуя полный перебор всей таблицы (full table scan).

Пример создания индекса в SQL:

-- Создание индекса по столбцу `last_name` в таблице `employees`.
CREATE INDEX idx_employees_last_name ON employees(last_name);
-- Теперь запросы вида SELECT * FROM employees WHERE last_name = 'Smith' выполняются гораздо быстрее.

Как это связано с C++? Аналоги индексов в памяти — это ассоциативные контейнеры стандартной библиотеки:

• std::map / std::set (обычно реализованы как красно-черные деревья) — для упорядоченного доступа.
• std::unordered_map / std::unordered_set (хэш-таблицы) — для доступа по ключу за O(1) в среднем.

Компромиссы (trade-offs) индексации:

• Плюсы: Кардинальное ускорение операций чтения.
• Минусы:
  • Дополнительное дисковое пространство: Индексы занимают место.
  • Замедление операций записи: При INSERT, UPDATE, DELETE СУБД должна обновлять не только таблицу, но и все связанные индексы.
  • Выбор столбцов: Неэффективно индексировать все подряд. Индексы создаются на часто используемых в условиях поиска столбцах.

Типы индексов: B-дерево (наиболее распространенный), хэш-индекс, полнотекстовый, пространственный (GIS).