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

Индекс B-Tree в базах данных

B-Tree (сбалансированное дерево) — это структура данных, используемая для создания индексов в базах данных. Это наиболее распространённый тип индексов в RDBMS (PostgreSQL, MySQL, Oracle).

Что такое индекс

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

Вместо полного сканирования таблицы (O(n)), индекс позволяет найти данные за O(log n).

Структура B-Tree

B-Tree — это многоуровневое сбалансированное дерево.

         [50]
        /    \
    [20, 30] [60, 70]
   /  |  \   /  |  \
 10 25 35 55 65 75 80

Свойства B-Tree:

• Сбалансировано — все листья на одной высоте
• Многоуровневое — может хранить миллиарды записей
• Отсортировано — значения в порядке возрастания
• Оптимизировано для диска — группирует данные в блоки

Порядок B-Tree

Порядок m определяет:

• Максимум детей у узла — m
• Максимум ключей у узла — m - 1

Если порядок = 3:
- Узел может хранить до 2 ключей
- Узел может иметь до 3 детей

      [30, 70]
      /   |   \
   [10] [50] [80]

Пример создания индекса в SQL

-- Создание индекса на столбце
CREATE INDEX idx_users_email ON users(email);

-- Составной индекс (на несколько столбцов)
CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);

-- Уникальный индекс
CREATE UNIQUE INDEX idx_users_email_unique ON users(email);

-- Частичный индекс (для подмножества строк)
CREATE INDEX idx_active_users ON users(email) WHERE is_active = true;

Как B-Tree ускоряет поиск

Без индекса (Full Table Scan):

SELECT * FROM users WHERE email = 'john@example.com';
-- Сканирует все 1000000 строк → O(n)

С индексом B-Tree:

CREATE INDEX idx_users_email ON users(email);
SELECT * FROM users WHERE email = 'john@example.com';
-- Идёт по индексу B-Tree → O(log n) ≈ 20 операций

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

1. Быстрый поиск — O(log n) вместо O(n)
2. Эффективен для range queries — можно найти диапазон (FROM ... TO)
3. Автоматическая сортировка — ORDER BY быстрее работает
4. Дисковая оптимизация — блоки индекса кэшируются в памяти
5. Сбалансирован — гарантированная высота O(log n)

Пример range query

-- Поиск пользователей с id от 1000 до 2000
SELECT * FROM users WHERE id BETWEEN 1000 AND 2000;
-- B-Tree быстро находит начало диапазона (1000)
-- и последовательно читает листья до конца (2000)

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

CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);

Индекс упорядочивается сначала по user_id, потом по created_at:

Индекс:
user_id=1, created_at=2024-01-01
user_id=1, created_at=2024-01-02
user_id=2, created_at=2024-01-01
...

Это ускоряет:

• WHERE user_id = 1 — использует индекс
• WHERE user_id = 1 AND created_at > '2024-01-01' — использует индекс
• WHERE created_at = '2024-01-01' — НЕ использует индекс (нужен левый префикс)

Когда B-Tree неэффективен

1. LIKE с маской слева — LIKE '%john' не использует индекс
2. Функции — WHERE UPPER(email) = 'JOHN@...' может не использовать индекс
3. Очень маленькие таблицы — full scan может быть быстрее
4. Высокая кардинальность в начале — если много одинаковых значений в начале индекса

B-Tree vs B+Tree

B-Tree:

• Ключи и данные во всех узлах
• Сложнее для range queries

B+Tree (более популярен):

• Ключи во всех узлах, данные только в листьях
• Листья связаны списком → эффективен для range queries
• Используется в PostgreSQL, MySQL InnoDB

B+Tree:
         [50]
        /    \
    [20] [70]
    /  |   |  \
  10 20 50 70 80  (листья связаны)
  ↓  ↓  ↓  ↓  ↓
  ptr ptr ptr ptr ptr

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

1. Память — индекс занимает место
2. Замедление вставок — нужно обновить индекс
3. Фрагментация — индекс может фрагментироваться

-- Дефрагментация индекса
REINDEX INDEX idx_users_email; -- PostgreSQL
OPTIMIZE TABLE users; -- MySQL

Как проверить, используется ли индекс

-- EXPLAIN показывает план выполнения
EXPLAIN SELECT * FROM users WHERE email = 'john@example.com';

-- Результат:
-- Index Scan using idx_users_email (cost=0.42..8.44 rows=1)
-- ↑ Используется индекс!

EXPLAIN SELECT * FROM users WHERE UPPER(email) = 'JOHN@EXAMPLE.COM';
-- Seq Scan on users (cost=0.00..35.50 rows=1)
-- ↑ НЕ используется индекс, полное сканирование

Лучшие практики

1. Индексируй WHERE, JOIN, ORDER BY — столбцы, которые часто фильтруются
2. Составные индексы — группируй связанные столбцы
3. Не переиндексируй — каждый индекс замедляет вставки
4. Проверяй EXPLAIN — убедись, что индекс используется
5. Удаляй неиспользуемые индексы — они только замедляют

B-Tree индексы — основа оптимизации запросов в SQL. Правильное использование индексов может ускорить запросы в 1000 раз.