За счет чего индекс позволяет быстрее искать по конкретному полю в БД

Индексы в базах данных: механика ускорения поиска

Суть проблемы

Без индекса база данных выполняет полный скан таблицы (table scan) — проходит по каждой строке последовательно, чтобы найти нужные данные. При таблице из миллионов записей это крайне неэффективно.

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

Индекс — это отдельная структура данных, которая хранит отсортированные значения поля и указатели на строки таблицы. Самая распространённая структура — B-tree (сбалансированное дерево).

Пример логики поиска:

Без индекса:
┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐  ┌─────────┐
│ Row 1   │→ │ Row 2   │→ │ Row 3   │→ │ Row 4   │→ │ Row 5   │ ... (N проверок)
│ id: 100 │  │ id: 250 │  │ id: 150 │  │ id: 890 │  │ id: 320 │
└─────────┘  └─────────┘  └─────────┘  └─────────┘  └─────────┘

С индексом (B-tree):
           ┌──── 500 ────┐
         /                 \
      150                  800
     /   \                /   \
    100   250           700   900
                              ↓
                         Найдена строка Row 4 за log(N) операций

Ключевые преимущества индекса

1. Логарифмическая сложность

• Полный скан: O(N) — проверяем каждую строку
• Поиск с индексом: O(log N) — прыгаем по дереву
• При 1 млн записей: 1M проверок vs 20 операций

2. Отсортированность данных Индекс хранит значения в отсортированном виде, что позволяет:

• Бинарный поиск (binary search)
• Быстрый поиск диапазонов (WHERE id BETWEEN 100 AND 500)
• Эффективную сортировку (ORDER BY без доп. сортировки)

3. Исключение полного скана БД знает точный диапазон значений в индексе и идёт туда напрямую, вместо того чтобы проверять все строки.

Пример на реальных данных

-- Таблица users с 10 млн записей
CREATE TABLE users (
  id BIGINT PRIMARY KEY,
  email VARCHAR(255),
  created_at TIMESTAMP
);

-- Без индекса на email:
-- EXPLAIN ANALYZE:
-- Seq Scan on users  (cost=0.00..180000.00 rows=10000000)
-- Время: ~30 сек

CREATE INDEX idx_users_email ON users(email);

-- С индексом на email:
-- EXPLAIN ANALYZE:
-- Index Scan using idx_users_email (cost=0.29..4.31 rows=1)
-- Время: ~1 мс

За счет чего достигается эффект

Типы индексов и их особенности

1. B-tree индекс (стандартный)

CREATE INDEX idx_name ON table(column);

Лучше для: точный поиск, диапазоны, сортировка.

2. Hash индекс

CREATE INDEX idx_hash ON table USING HASH(column);

Лучше для: только точный поиск (=), быстрее чем B-tree.

3. Bitmap индекс (Oracle, PostgreSQL) Лучше для: колонки с малым количеством уникальных значений.

Когда индекс НЕ помогает

• LIKE с левым wildcard: WHERE name LIKE '%ivan' (сканируется вся таблица)
• Функции на индексированном поле: WHERE UPPER(email) = 'TEST' (индекс не используется)
• OR условия: WHERE id = 1 OR age = 25 (может потребоваться 2 скана)
• Очень селективные индексы: если индекс вернул 99% таблицы — дешевле полный скан

Вывод

Индекс ускоряет поиск благодаря трём факторам:

1. Иерархическая структура (B-tree) вместо линейного поиска
2. Отсортированность для бинарного поиска
3. Указатели на строки исключают лишние операции чтения

Разница в производительности: от миллисекунд (с индексом) до секунд/минут (без индекса) на больших таблицах.