Урок 10.5 · Время чтения: ~11 мин

Этот урок подробно объясняет, как работает B-tree индекс в SQL на физическом и логическом уровне. Вы узнаете, из каких узлов состоит структура, как СУБД проходит по дереву и почему такой подход ускоряет фильтрацию и сортировку. Мы рассмотрим практические примеры на таблицах Sakila и закрепим ключевые правила применения. К концу урока вы будете лучше понимать, когда B-tree индекс действительно ускоряет запросы.

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

В прошлом уроке вы узнали, как создавать индексы. Теперь разберемся, как индекс устроен внутри и почему он ускоряет поиск.

Понимание B-tree поможет вам видеть, когда индекс реально работает и когда его нельзя использовать. Это знание пригодится при оптимизации медленных запросов.

Что такое B-tree индекс

B-tree индекс похож на оглавление в книге. Вместо того чтобы читать все страницы подряд, вы открываете оглавление, находите нужную главу и идете туда напрямую.

В B-tree есть три уровня:

• корневой узел - начало поиска, как обложка оглавления;
• промежуточные узлы - подсказывают, в какую сторону идти дальше;
• листовые узлы - содержат нужные значения и ссылки на строки таблицы.

Вся структура отсортирована, поэтому СУБД может быстро выбирать нужное направление на каждом уровне.

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

                    [ ROOT ]
                   /   |   \
                  /    |    \
            [NODE A] [NODE B] [NODE C]
            / |  \    / | \    / | \
           /  |   \  /  |  \  /  |  \
         [L1][L2][L3][L4][L5][L6][L7][L8]

Каждый узел содержит значения, которые помогают выбрать следующий узел. Листовые узлы (L1–L8) содержат нужные данные.

Как выполняется поиск по B-tree

Когда вы ищете WHERE last_name = 'SMITH', СУБД:

1. стартует из корневого узла;
2. выбирает ветку, где могут быть фамилии, начинающиеся на 'S';
3. спускается вниз, уточняя поиск на каждом уровне;
4. находит нужную фамилию в листовом узле.

Благодаря этому алгоритму поиск очень быстрый — даже в таблице с миллионами строк нужно проверить всего несколько уровней.

Какие операции B-tree ускоряет лучше всего

Равенство (=)

B-tree хорошо подходит для точного поиска значения.

SELECT
   customer_id,
   first_name,
   last_name
FROM customer
WHERE last_name = 'SMITH';

Диапазоны (>, <, BETWEEN)

Из-за отсортированности ключей B-tree эффективен для диапазонных условий.

SELECT
   payment_id,
   amount,
   payment_date
FROM payment
WHERE payment_date >= '2005-07-01'
  AND payment_date < '2005-08-01';

Сортировка (ORDER BY)

Если порядок сортировки совпадает с индексом, СУБД часто может избежать дорогой отдельной сортировки.

SELECT
   payment_id,
   customer_id,
   payment_date
FROM payment
WHERE customer_id = 10
ORDER BY payment_date;

Пример составного B-tree индекса

Создадим индекс под частый шаблон фильтрации и сортировки:

CREATE INDEX idx_payment_customer_date
ON payment (customer_id, payment_date);

Проверим план:

EXPLAIN
SELECT
   payment_id,
   customer_id,
   payment_date,
   amount
FROM payment
WHERE customer_id = 10
  AND payment_date >= '2005-07-01'
ORDER BY payment_date;

Результат: обычно СУБД использует индекс для фильтрации по customer_id и диапазону payment_date, а также для упорядоченного чтения.

Правило левого префикса для составного индекса

Если индекс создан как (customer_id, payment_date), то СУБД лучше всего использует его, если в условии сначала фильтруется по customer_id.

Работает хорошо:

WHERE customer_id = 10

Работает хорошо:

WHERE customer_id = 10 AND payment_date >= '2005-01-01'

Работает плохо:

WHERE payment_date >= '2005-01-01'

Это правило называют "левым префиксом": индекс работает лучше всего, когда вы используете условия слева направо.

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

Index не используется, если:

• вы применяете функцию к столбцу: WHERE YEAR(payment_date) = 2005 — индекс не работает;
• используете маску в начале: WHERE name LIKE '%SMITH' — индекс не поможет;
• условие слишком общее и вернет много строк — индекс может быть медленнее, чем чтение всей таблицы.

Плохо (функция мешает индексу):

SELECT payment_id, payment_date
FROM payment
WHERE YEAR(payment_date) = 2005;

Хорошо (индекс сможет работать):

SELECT payment_id, payment_date
FROM payment
WHERE payment_date >= '2005-01-01'
  AND payment_date < '2006-01-01';

Практические рекомендации

• Индексируйте поля, которые часто участвуют в WHERE, JOIN, ORDER BY.
• Для составных индексов ставьте первым наиболее важный для фильтрации столбец.
• Проверяйте фактическое использование индекса через EXPLAIN.
• Не создавайте избыточные индексы: они увеличивают стоимость записи.

Ключевые выводы этого урока:

• B-tree - это сбалансированная структура, ускоряющая поиск по ключам.
• Основная сила B-tree: равенство, диапазоны и сортировка по индексному порядку.
• Составные индексы подчиняются правилу левого префикса.
• Неподходящая форма условия может лишить запрос преимуществ индекса.
• EXPLAIN помогает понять, используется ли B-tree в реальном плане выполнения.

Вопросы для собеседования

Почему B-tree индекс обычно быстрее полного сканирования?

Потому что СУБД проходит по дереву по веткам и находит нужный диапазон за логарифмическое число шагов, вместо просмотра всех строк таблицы.

Что такое правило левого префикса для составного индекса?

Это правило означает, что оптимизатор лучше всего использует индекс, начиная с первого столбца ключа и далее по порядку.

Как на практике проверить, что B-tree индекс используется?

Нужно выполнить EXPLAIN и посмотреть тип доступа, выбранный ключ и ожидаемое число строк на этапах выполнения.

В следующем уроке мы перейдем к обработке ошибок и приемам отладки SQL-запросов.