Как устроены индексы в реляционных базах данных?

Индекс в БД — это отдельная структура данных (чаще всего B-дерево или его вариации), которая ускоряет операции поиска (WHERE), сортировки (ORDER BY) и соединения (JOIN) за счет предварительно упорядоченных ссылок на строки таблицы.

Аналогия: Индекс в книге позволяет быстро найти нужную страницу, не перелистывая все подряд.

Как работает B-дерево (наиболее распространенный тип):

         [ 15 | 30 ]          <-- Корневой узел (диапазоны ключей)
         /     |     
        /      |      
[5|10]  [20|25]  [35|40]     <-- Внутренние узлы
  |       |        |
(данные) (данные) (данные)    <-- Листовые узлы (содержат ссылки на фактические строки таблицы)

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

• Высокая скорость поиска: Сложность поиска по индексированному полю — O(log n).
• Поддержка сортировки: Данные в листьях упорядочены, что ускоряет ORDER BY и DISTINCT.
• Поддержка уникальности: Уникальный индекс гарантирует отсутствие дубликатов.

Недостатки и затраты:

• Дополнительное место на диске: Индекс занимает память.
• Замедление операций записи: При INSERT, UPDATE, DELETE индекс необходимо перестраивать.

Пример создания и использования в SQL:

-- Создание индекса
CREATE INDEX idx_user_email ON users(email);

-- Создание составного индекса (порядок столбцов важен!)
CREATE INDEX idx_user_name_dep ON users(last_name, department_id);

-- Запрос, который может использовать индекс
SELECT * FROM users WHERE email = 'alice@example.com'; -- Быстро (idx_user_email)
SELECT * FROM users WHERE last_name = 'Smith' AND department_id = 5; -- Быстро (idx_user_name_dep)
SELECT * FROM users WHERE department_id = 5; -- Медленно, если нет отдельного индекса на department_id

Когда создавать индекс:

• На столбцах, часто используемых в условиях WHERE и JOIN.
• На столбцах, используемых в ORDER BY.
• На столбцах с ограничением UNIQUE или PRIMARY KEY (создаются автоматически).

Когда индекс может не помочь:

• На таблицах с частыми массовыми операциями записи.
• На столбцах с низкой селективностью (например, gender с двумя значениями).
• При неправильном порядке столбцов в составном индексе.