Насколько B-Tree индекс ускоряет поиск в базах данных?

B-Tree индексы кардинально ускоряют поиск, снижая его алгоритмическую сложность с линейной O(n) до логарифмической O(log n).

Наглядный пример:
Представьте таблицу с 1 миллиардом записей.

• Без индекса (Full Scan, O(n)): Базе данных придётся проверить в худшем случае 1,000,000,000 записей, чтобы найти нужную.
• С B-Tree индексом (Index Seek, O(log n)): Поиск будет похож на деление пополам. Базе данных потребуется всего лишь около 30 операций (log₂(10⁹) ≈ 30), чтобы найти нужную запись.

Разница в производительности — в миллионы раз.

Преимущества B-Tree:

• Быстрый поиск: Эффективен для точечных запросов (WHERE id = 123).
• Эффективные диапазонные запросы: Отлично подходит для запросов с BETWEEN, >, <, так как данные в индексе уже отсортированы.
• Поддержка сортировки: Может ускорять ORDER BY, если сортировка совпадает с порядком индекса.

Недостатки (компромиссы):

• Замедление операций записи: INSERT, UPDATE, DELETE становятся медленнее, так как базе данных нужно не только изменить данные в таблице, но и обновить структуру B-Tree индекса.
• Занимает место на диске: Индекс — это отдельная структура данных, которая требует дополнительного дискового пространства.
• Низкая селективность: Менее эффективен на полях с низкой кардинальностью (мало уникальных значений), например, на поле «пол» ('мужской', 'женский'). В таких случаях полный скан таблицы может быть даже быстрее.