Как устроен индекс?

Как устроен индекс в MySQL и других базах данных?

Индекс — это специальная структура данных внутри базы данных, предназначенная для ускорения поиска и сортировки данных в таблице. По сути, это отдельный "справочник", который хранит ключевые значения (например, значения колонки) и ссылки на соответствующие строки в основной таблице. Это позволяет избежать полного сканирования таблицы (full table scan) и быстро находить нужные записи.

Основные принципы работы индекса

1. Аналогия с книгой: Индекс похож на оглавление в книге. Чтобы найти информацию о конкретной теме, вы не читаете всю книгу, а смотрите в оглавление, где указаны страницы.
2. Типы индексов: Наиболее распространённый тип — B-дерево (Balanced Tree), особенно его вариант B+tree, который используется в MySQL/InnoDB. Также существуют hash-индексы, fulltext-индексы, spatial-индексы и другие.
3. Структура B+tree:

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

Внутренняя реализация индекса в MySQL (InnoDB)

В MySQL с движком InnoDB индекс реализован как кластерный индекс (clustered index) для первичного ключа и как некластерные индексы (secondary indexes) для остальных колонок.

Кластерный индекс (по первичному ключу)

Это основной индекс, который определяет физический порядок данных в таблице. Сами данные таблицы хранятся в листовых узлах этого B+tree. Поэтому поиск по первичному ключу максимально эффективен.

-- Таблица с первичным ключом id. Данные хранятся в кластерном индексе по id.
CREATE TABLE users (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    email VARCHAR(100)
);
-- Физически в файле .ibd строки упорядочены по значению id.

Некластерные (вторичные) индексы

Индексы по другим колонкам хранят в своих листовых узлах не сами данные строки, а значение первичного ключа соответствующей записи. Поэтому при использовании такого индекса происходит два шага:

1. Поиск в B+tree вторичного индекса по значению колонки (например, email) для получения id.
2. Затем поиск в кластерном индексе по найденному id для получения всей строки. Этот второй шаг называется "переход по ключу" (key lookup).

-- Вторичный индекс по колонке email
CREATE INDEX idx_email ON users(email);
-- В листовых узлах idx_email хранятся: значение email -> значение id (первичный ключ).

Пример поиска с использованием индекса

Рассмотрим запрос:

SELECT * FROM users WHERE email = 'alex@example.com';

Если индекс idx_email существует, процесс будет таким:

1. Поиск в B+tree индекса idx_email: Начиная с корневого узла, двигаемся по внутренним узлам, сравнивая значения, чтобы найти листовой узел, содержащий ключ 'alex@example.com'.
2. Получение id: В листовом узле находится значение id, связанное с этим email (например, id = 42).
3. Поиск в кластерном индексе: Используя id=42, выполняем быстрый поиск в основном B+tree (кластерном индексе по id) и получаем всю строку данных для users.id=42.
4. Возврат результата: Клиенту возвращается полная строка.

Если индекс отсутствует, то двигажок выполнит full table scan, читая и проверяя каждую строку таблицы последовательно, что гораздо медленнее на больших таблицах.

Ключевые особенности и соображения

• Сортировка: Индексы хранят данные в отсортированном порядке (по ключу индекса). Это позволяет быстро выполнять операции ORDER BY и поиск по диапазону (WHERE date > '2023-01-01').
• Составные индексы: Индекс может быть создан по нескольким колонкам. Порядок колонок в определении индекса критически важен.

  CREATE INDEX idx_name_age ON users(name, age);
  -- Этот индекс полезен для условий WHERE name = ... AND age = ..., или только WHERE name = ..., но НЕ полезен для WHERE age = ... (без name).
  

• Накладные расходы: Индексы требуют дополнительного дискового пространства и увеличивают время операций INSERT, UPDATE, DELETE, поскольку движок должен обновлять не только данные, но и все соответствующие индексы. Поэтому не следует индексировать все колонки без необходимости.
• Покрывающие индексы (covering index): Если все колонки, необходимые для запроса, присутствуют в самом индексе (например, вторичный индекс содержит колонки email и name, и нам нужен только SELECT email, name), то не требуется переход к кластерному индексу, что значительно ускоряет запрос.
• Выборка данных: Индексы используются не только для фильтрации (WHERE), но также для операций JOIN и группировки (GROUP BY).

Итог: Индекс — это мощный механизм оптимизации, основанный на эффективных структурах данных, таких как B+tree. Он позволяет превращать медленные операции линейного поиска (O(n)) в быстрые операции логарифмического поиска (O(log n)). Однако его использование требует глубокого понимания структуры таблиц, частоты запросов и баланса между скоростью чтения и скоростью обновления данных. Правильное проектирование индексов — одна из ключевых задач в оптимизации производительности бэкенда.