Сколько будет выполнтся поиск по индексу в бд?

Время выполнения поиска по индексу

Сложность в Big O нотации

Поиск по индексу выполняется за O(log N) — логарифмическое время.

где N — количество строк в таблице.

Пример расчёта

Для B-Tree индекса (самый распространённый)

Таблица с 1 млн строк:
log₂(1,000,000) ≈ 20 дисковых операций

Таблица с 1 млрд строк:
log₂(1,000,000,000) ≈ 30 дисковых операций

Таблица с 1 трлн строк:
log₂(1,000,000,000,000) ≈ 40 дисковых операций

Реальные времена

При условии:

• B-Tree индекс (PostgreSQL, MySQL)
• SSD диск (типичный в облаке)
• 8 KB блок (default)
• Условие на одну колонку: WHERE id = 123

10 строк → 0.001 ms (в памяти)
1000 строк → 0.01 ms
100K строк → 0.1 ms
1M строк → 1 ms
10M строк → 2 ms
100M строк → 3 ms
1B строк → 4 ms

Сравнение: индекс vs полное сканирование

Для таблицы с 100M строк:

Полное сканирование (Full Scan):
100M строк * 0.001 ms = 100 секунд

Поиск по индексу (Index Scan):
log₂(100M) = 27 операций * 0.1 ms = 2.7 ms

Ускорение в 37000 раз!

Как измерить реальное время?

-- PostgreSQL
EXPLAIN ANALYZE
SELECT * FROM users WHERE id = 12345;

-- Выведет:
-- Index Scan using users_pkey on users (cost=0.29..2.34 rows=1) (actual time=0.123..0.126 rows=1)

-- MySQL
EXPLAIN
SELECT * FROM users WHERE id = 12345;

-- Выведет:
-- Using index (говорит, что использовался индекс)

От чего зависит время?

1. Тип индекса

B-Tree: O(log N) — 2-4 мс на 1B строк
Hash: O(1) — но только для =, не для >, <, LIKE
Bitmap: O(log N) — для множественных условий
Full-text: O(k) — зависит от количества совпадений

2. Размер результата

-- Быстро (индекс)
WHERE id = 123
-- Поиск: 3 ms
-- Чтение: 1 row * 0.001 ms = 0.001 ms
-- Итого: 3 ms

-- Медленнее (индекс + много операций чтения)
WHERE age > 30
-- Поиск: 3 ms
-- Чтение результатов: 50M rows * 0.001 ms = 50 сек
-- Итого: 50 сек

3. Селективность индекса

Высокая селективность (возвращает 1 строку):
WHERE id = 123  (уникальный индекс)
→ 2-4 ms

Средняя селективность (5% строк):
WHERE country = Russia  (5M из 100M)
→ 5 ms (поиск) + 5 сек (чтение) = 5 сек

Низкая селективность (50% строк):
WHERE is_active = true  (50M из 100M)
→ 2 ms (поиск) + 50 сек (чтение) = 50 сек
→ Оптимизатор может использовать Full Scan вместо индекса

4. Кеш базы данных

Первый запрос (данные не в кеше):
3 ms (дисковые операции)

Второй запрос (данные в кеше памяти):
0.1 ms (читаем из памяти)

Пример EXPLAIN анализа

EXPLAIN ANALYZE
SELECT * FROM orders WHERE customer_id = 456;

Планировщик вывел:
Index Scan using orders_customer_id_idx 
  on orders  (cost=0.42..4.44 rows=10) (actual time=0.234..0.456 rows=10 loops=1)
  Index Cond: (customer_id = 456)
  Execution time: 0.512 ms

Что это значит:
- cost=0.42 начальная стоимость, 4.44 финальная
- actual time=0.234 (время поиска по индексу)
- rows=10 (ожидаемо 10 строк, реально 10)
- Execution time=0.512 ms (общее время)

Hash индекс (O(1) поиск)

Преимущество: Поиск за O(1) константное время.

CREATE INDEX hash_idx ON users USING HASH(email);

SELECT * FROM users WHERE email = alice@example.com;
-- Время: 0.1-0.2 ms (независимо от размера таблицы!)

Недостаток: Работает только для =, не поддерживает >, <, BETWEEN.

-- Не будет использовать hash индекс
WHERE email LIKE a%  
WHERE email > a  
WHERE email IN (...)

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

1. Плохая селективность

WHERE is_active = true  -- 99% таблицы
-- Индекс бесполезен, используется Full Scan

2. Условия, не поддерживаемые индексом

INDEX на col1 и col2

WHERE col1 = X AND col2 = Y  -- Использует индекс ✓
WHERE col2 = Y               -- НЕ использует индекс ✗
WHERE col1 > X OR col2 = Y   -- Не может использовать ✗

3. Слишком сложный запрос

WHERE YEAR(created_at) = 2024  -- Функция блокирует индекс

-- Лучше:
WHERE created_at >= 2024-01-01 AND created_at < 2025-01-01

Оптимизация индексов

-- Для быстрого поиска по одной колонке
CREATE INDEX idx_user_id ON orders(user_id);

-- Composite индекс (первая колонка для условия)
CREATE INDEX idx_user_date ON orders(user_id, created_at);

-- Partial индекс (только активные строки)
CREATE INDEX idx_active_users ON users(id) WHERE is_active = true;

-- Covering индекс (весь результат из индекса)
CREATE INDEX idx_covering ON users(user_id, email, name);
SELECT user_id, email, name FROM users WHERE user_id = 456;
-- Не нужно читать основную таблицу!

Практическое резюме

Вывод

Поиск по B-Tree индексу выполняется за O(log N), что означает:

• Даже для 1 млрд строк это всего 30 дисковых операций
• Реальное время: 2-5 мс на современном SSD
• Используйте индексы для условий с высокой селективностью
• Для скорости обновления выбирайте правильно типы индексов