> Какие операции выигрывают от B-tree индекса, а какие нет (Python)

Короткий ответ

B-tree индекс выигрывает для операций точечного поиска по равенству, диапазонных запросов, сортировки и префиксного поиска по левой части ключа. Не выигрывает для операций с функциями над колонками, LIKE с ведущим wildcard, поиска по подстроке, OR по разным колонкам без составного индекса, а также для операций, где селективность низкая и оптимизатор выбирает full scan. Также индекс бесполезен для записи, если обновляется много строк - overhead на поддержание дерева перевешивает выигрыш.

Подробное объяснение

B-tree - сбалансированное дерево, где листья хранят отсортированные ключи и ссылки на строки. Это даёт O(log n) на поиск и O(log n) на вставку/удаление, но главное - упорядоченность листьев позволяет эффективно сканировать диапазоны.

Выигрывают:

• WHERE col = value - точечный lookup, O(log n) вместо O(n)
• WHERE col > value, BETWEEN, IN - диапазонное сканирование по упорядоченным листьям
• ORDER BY col - индекс уже отсортирован, избегаем filesort
• GROUP BY col - аналогично, группы идут подряд
• WHERE col LIKE 'prefix%' - префиксный поиск работает как диапазон
• Составные индексы (a, b) - для запросов с a и a, b, но не с b отдельно

Не выигрывают:

• WHERE UPPER(col) = ... или WHERE col + 1 > 10 - функция или арифметика ломает упорядоченность, индекс не используется
• LIKE '%substring%' - ведущий wildcard требует полного сканирования
• WHERE col1 = 1 OR col2 = 2 - если нет составного индекса, OR по разным колонкам часто превращается в два lookup + merge, что может быть хуже full scan
• WHERE col IS NULL - в некоторых СУБД NULL не индексируется или обрабатывается отдельно
• Запросы с низкой селективностью - если условие выбирает 30%+ строк, оптимизатор выберет seq scan, потому что random I/O по индексу дороже последовательного чтения
• Операции с NOT, != - обычно не используют индекс, если только селективность не высокая

На практике

В Python-стеках с PostgreSQL или MySQL важно помнить, что B-tree - это не серебряная пуля. Для JSONB, полнотекстового поиска, геоданных нужны другие типы индексов (GIN, GiST, BRIN). Также стоит учитывать, что составной индекс (a, b) работает для a, a+b, но не для b - это правило leftmost prefix. Для OR по разным колонкам часто выгоднее UNION ALL с отдельными индексами, чем один составной. При диагностике медленных запросов смотрите EXPLAIN ANALYZE - если видите Seq Scan там, где ожидали Index Scan, проверьте, не обёрнута ли колонка в функцию.

Пример кода

SQL
-- Хорошо для B-tree
SELECT * FROM users WHERE email = 'a@b.com';
SELECT * FROM orders WHERE created_at BETWEEN '2024-01-01' AND '2024-01-31';
SELECT * FROM products ORDER BY price;

-- Плохо для B-tree
SELECT * FROM users WHERE LOWER(email) = 'a@b.com';  -- функция
SELECT * FROM posts WHERE content LIKE '%python%';   -- ведущий wildcard
SELECT * FROM users WHERE age > 18 OR status = 'active';  -- OR по разным колонкам

В Python с SQLAlchemy это выглядит так:

PYTHON
# Хорошо - индекс используется
session.query(User).filter(User.email == 'a@b.com').all()
session.query(Order).filter(Order.created_at.between('2024-01-01', '2024-01-31')).all()

# Плохо - индекс не используется
session.query(User).filter(func.lower(User.email) == 'a@b.com').all()
session.query(Post).filter(Post.content.like('%python%')).all()

Как отвечать на собеседовании

Начните с короткого определения B-tree и его ключевого свойства - упорядоченности. Затем перечислите операции, которые выигрывают: равенство, диапазоны, сортировка, префиксный LIKE. Потом - которые не выигрывают: функции над колонками, ведущий wildcard, OR по разным колонкам, низкая селективность. Приведите пример из реального опыта: например, как вы ускорили запрос, добавив составной индекс, или как EXPLAIN показал, что индекс не используется из-за обёртки в функцию. Упомяните trade-off: индекс ускоряет чтение, но замедляет запись и занимает место. Если спросят про Python - скажите, что ORM не влияет на планировщик, важно только то, какой SQL генерируется.

Что проверяет интервьюер

Проверяется понимание внутренней структуры B-tree, а не заученные правила. Интервьюер хочет увидеть, что вы понимаете, почему функция ломает индекс - потому что дерево хранит исходные значения, а не результат функции. Также проверяется умение рассуждать о селективности и trade-off между read и write performance. Для senior важно показать, что вы не просто знаете список, а можете объяснить, как оптимизатор принимает решение, и умеете читать EXPLAIN.

Типичные ошибки

• Говорить, что индекс ускоряет все запросы - это не так, и это сразу выдаёт junior
• Путать B-tree с hash-индексом - hash не поддерживает диапазоны и сортировку
• Забывать про leftmost prefix для составных индексов
• Утверждать, что LIKE '%text%' можно ускорить B-tree - это работает только с триграммными индексами (pg_trgm)
• Не упоминать, что для OR по разным колонкам иногда лучше UNION ALL
• Говорить, что индекс не нужен для маленьких таблиц - это верно, но не потому что индекс плохой, а потому что full scan дешевле из-за отсутствия random I/O