Почему индексы эффективнее?

# Почему индексы эффективнее?

Основная идея

Индексы в базе данных решают фундаментальную проблему: как быстро найти нужные строки без сканирования всей таблицы?

Как работают индексы

Без индекса база данных вынуждена выполнять полное сканирование таблицы (Full Table Scan). Для таблицы с 1 млн записей нужно проверить все миллион записей. Индекс создает специальную структуру данных, обычно B-Tree или Hash Table, которая позволяет быстро найти нужные данные:

// Без индекса: O(n) - линейный поиск
SELECT * FROM users WHERE email = "john@example.com"; // проверяет все миллионы строк

// С индексом на email: O(log n) - бинарный поиск в B-Tree
SELECT * FROM users WHERE email = "john@example.com"; // находит за ~20 операций

Конкретный пример производительности

Таблица с 10 млн пользователей:

Без индекса:

• Среднее время: ~2 секунды (проверяет 5 млн строк)
• Нагрузка на процессор: 100%
• Блокировка других запросов

С индексом на нужное поле:

• Время: ~5 миллисекунд
• Нагрузка на процессор: <1%
• Другие запросы не блокируются

Разница: в 400 раз быстрее!

Структура B-Tree индекса

Б-дерево организует данные иерархически:

                    [M]
                   /   \
              [D]         [S]
             / | \       / | \
            A B C E F... P Q R T U...

Чтобы найти значение, база спускается по дереву, отсекая половину оставшихся данных на каждом уровне (как в бинарном поиске).

Когда индексы дают максимальный прирост

1. Фильтрация по WHERE — самый частый случай

   SELECT * FROM orders WHERE customer_id = 123 -- индекс на customer_id нужен
   

2. JOIN условия — поля в ON

   SELECT * FROM orders o 
   JOIN customers c ON o.customer_id = c.id -- индексы на обоих полях
   

3. ORDER BY и GROUP BY — если поле в индексе, сортировка быстра

   SELECT * FROM orders ORDER BY created_at -- B-Tree уже отсортирован
   

4. LIMIT с пагинацией

   SELECT * FROM orders ORDER BY id LIMIT 20 OFFSET 1000000 -- без индекса проверяет миллион
   

Цена индексов

Индексы — это не всегда хорошо:

• Память: индекс занимает дополнительное место на диске (часто 10-30% от размера таблицы)
• INSERT/UPDATE/DELETE медленнее: при каждом изменении нужно обновить индекс
• Выбор неправильного индекса: может быть медленнее, чем Full Scan

Пример из Java приложения

// Плохо: N+1 проблема из-за отсутствия индекса
List<User> users = userRepository.findAll(); // загружает всех пользователей
for (User user : users) {
    List<Order> orders = orderRepository.findByUserId(user.getId()); // ЗАПРОС на каждого юзера!
}

// Хорошо: с индексом на user_id
// Первый запрос с JOIN загружает все данные за раз
List<UserWithOrders> result = jdbcTemplate.query(
    "SELECT u.*, o.* FROM users u LEFT JOIN orders o ON u.id = o.user_id",
    new UserOrderRowMapper()
); // индекс на orders.user_id делает JOIN быстрым

Практические рекомендации

1. Индексировать поля в WHERE: если часто ищешь по email, создай индекс
2. Индексировать внешние ключи (FK): почти всегда нужны для JOIN
3. Не индексировать всё подряд: только часто используемые поля
4. Составные индексы: если WHERE с несколькими условиями, рассмотри индекс на (field1, field2)
5. Мониторить слоу-квери: использовать EXPLAIN для анализа плана выполнения

Вывод

Индексы эффективнее, потому что снижают количество операций чтения с диска с O(n) до O(log n). На больших таблицах это разница между миллисекундами и секундами. Однако правильный выбор индексов требует анализа реальных запросов в твоем приложении.