За счет чего индекс БД ускоряет запрос?

Как индексы ускоряют запросы в БД

Индекс — это структура данных, которая позволяет СУБД находить строки намного быстрее, чем сканирование всей таблицы. Разберемся, почему это работает.

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

Без индекса СУБД должна просмотреть КАЖДУЮ строку в таблице:

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

Если в таблице 1 млн строк:

• Возможно, нужно сравнить 1 млн email адресов
• Временная сложность: O(n)
• В худшем случае ищемый email в конце → 1 млн сравнений

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

Индекс создает отдельную структуру данных (обычно B-дерево), которая хранит отсортированные значения и указатели на строки:

┌─────────────────────────────────┐
│      Таблица users              │
├─────────────────────────────────┤
│ id │ email           │ name      │
├────┼─────────────────┼───────────┤
│ 1  │ alice@ex.com    │ Alice     │
│ 2  │ bob@ex.com      │ Bob       │
│ 3  │ charlie@ex.com  │ Charlie   │
│ 4  │ david@ex.com    │ David     │
└─────────────────────────────────┘

      ↓ Индекс на email ↓

┌──────────────────────────────────┐
│      Индекс (B-дерево)           │
├──────────────────────────────────┤
│ alice@ex.com    → указатель на 1  │
│ bob@ex.com      → указатель на 2  │
│ charlie@ex.com  → указатель на 3  │
│ david@ex.com    → указатель на 4  │
└──────────────────────────────────┘

При поиске john@ex.com, СУБД ищет в индексе (отсортированный список), а не в таблице.

Механизм: B-дерево

Большинство баз данных используют B-дерево (сбалансированное дерево поиска):

Уровень 0 (корень):           [M]
                      /                  \
                     /                    \
Уровень 1:    [A ... L]              [N ... Z]
              /  |  |  \\            /  |  |  \\
          [листья с данными]

Поиск в B-дереве: O(log n) вместо O(n)

Для 1 млн записей:
- Без индекса (полный скан):    1 млн сравнений
- С индексом (B-дерево):        log₂(1,000,000) ≈ 20 сравнений

Ускорение: в 50,000 раз! 🚀

Пример: поиск в таблице из 1000 строк

-- Без индекса: FULL TABLE SCAN
SELECT * FROM users WHERE id = 500;
-- Время: ~10ms (нужно проверить 500 строк в худшем случае)

CREATE INDEX idx_users_id ON users(id);

-- С индексом: USING INDEX
SELECT * FROM users WHERE id = 500;
-- Время: ~0.1ms (логарифмический поиск, ~10 шагов)
-- Ускорение: в 100 раз!

Виды индексов и их использование

1. Single Column Index (простой индекс)

CREATE INDEX idx_email ON users(email);

-- Запрос использует индекс
SELECT * FROM users WHERE email = 'john@example.com';

2. Composite Index (составной индекс)

CREATE INDEX idx_user_email_status ON users(email, status);

-- Обе колонки в WHERE → индекс работает эффективно
SELECT * FROM users 
WHERE email = 'john@example.com' AND status = 'active';

3. Unique Index

CREATE UNIQUE INDEX idx_unique_email ON users(email);
-- Гарантирует уникальность + ускоряет поиск

4. Full-text Index

CREATE FULLTEXT INDEX idx_article_text ON articles(content);

-- Быстрый поиск текста в больших полях
SELECT * FROM articles 
WHERE MATCH(content) AGAINST('database' IN BOOLEAN MODE);

EXPLAIN: как проверить использование индекса

-- Без индекса: FULL SCAN
EXPLAIN SELECT * FROM users WHERE email = 'john@example.com';

id | select_type | table | type | possible_keys | key  | key_len | rows
1  | SIMPLE      | users | ALL  | NULL          | NULL | NULL    | 1000
-- ALL = полный скан всех 1000 строк! ❌

-- С индексом: INDEX SEARCH
CREATE INDEX idx_email ON users(email);
EXPLAIN SELECT * FROM users WHERE email = 'john@example.com';

id | select_type | table | type | possible_keys | key      | key_len | rows
1  | SIMPLE      | users | ref  | idx_email     | idx_email| 50      | 1
-- ref = использование индекса, всего 1 строка! ✓

Реальный пример на Python

import time
from sqlalchemy import create_engine, Index, Column, String, Integer
from sqlalchemy.orm import declarative_base, Session

Base = declarative_base()

class User(Base):
    __tablename__ = 'users'
    id = Column(Integer, primary_key=True)
    email = Column(String(100))
    name = Column(String(100))

# Без индекса
engine = create_engine('sqlite:///:memory:')
Base.metadata.create_all(engine)

# Добавляем 10000 пользователей
with Session(engine) as session:
    for i in range(10000):
        session.add(User(email=f'user{i}@example.com', name=f'User {i}'))
    session.commit()

# Поиск БЕЗ индекса
start = time.time()
with Session(engine) as session:
    for _ in range(100):
        user = session.query(User).filter_by(email='user5000@example.com').first()
print(f'Без индекса: {(time.time() - start)*1000:.2f}ms')
# Результат: ~50ms (полный скан 10000 строк x 100 раз)

# Создаем индекс
Index('idx_email', User.email).create(engine)

# Поиск С индексом
start = time.time()
with Session(engine) as session:
    for _ in range(100):
        user = session.query(User).filter_by(email='user5000@example.com').first()
print(f'С индексом: {(time.time() - start)*1000:.2f}ms')
# Результат: ~2ms (логарифмический поиск)

# Ускорение: 50/2 = 25x! 🚀

Стоимость индексов

Индексы ускоряют SELECT, но замедляют INSERT/UPDATE/DELETE:

-- Без индекса: быстрый INSERT
INSERT INTO users (email, name) VALUES ('john@example.com', 'John');
-- Время: 0.1ms

-- С индексом на email: INSERT медленнее
INSERT INTO users (email, name) VALUES ('john@example.com', 'John');
-- Время: 0.5ms (нужно обновить индекс B-дерево)

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

Таблица users: 100 MB
Индекс на email: 20 MB (дополнительно)

Общее место: 120 MB

Когда использовать индексы

✅ Используй индексы на:

• Столбцах в WHERE (фильтрация)
• Столбцах в JOIN (связи)
• Столбцах в ORDER BY (сортировка)
• Столбцах в GROUP BY (группировка)
• PRIMARY KEY (автоматически)
• FOREIGN KEY (рекомендуется)

❌ НЕ используй индексы на:

• Столбцах с низкой селективностью (много одинаковых значений)
• Очень частые UPDATE/DELETE операции
• Булевы столбцы (только 2 значения)
• Маленькие таблицы (< 1000 строк)

Пример оптимальной индексации

from sqlalchemy import Index

class User(Base):
    __tablename__ = 'users'
    id = Column(Integer, primary_key=True)  # Индекс автоматически
    email = Column(String(100), unique=True)  # Индекс автоматически
    status = Column(String(20), default='active')
    created_at = Column(DateTime, default=datetime.utcnow)
    
    # Составной индекс для частых запросов
    __table_args__ = (
        Index('idx_status_created', 'status', 'created_at'),
    )

# Эти запросы будут быстрыми:
# 1. SELECT * FROM users WHERE email = '...'
# 2. SELECT * FROM users WHERE status = 'active' ORDER BY created_at

Вывод

Индексы ускоряют запросы за счет:

1. Структуры данных (B-дерево): O(log n) вместо O(n)
2. Отсортированности: бинарный поиск вместо линейного
3. Меньше операций ввода-вывода: меньше дисковых операций

Без индекса: поиск среди 1 млн строк требует 1 млн сравнений С индексом: поиск требует ~20 сравнений

Это основная причина, почему индексы критичны для производительности БД.