Зачем нужны бинарные деревья в БД?

Зачем нужны бинарные деревья в БД?

Бинарные деревья (особенно B-tree и его варианты) - это фундаментальная структура данных, которая лежит в основе индексов практически во всех современных базах данных.

Основной принцип

Бинарное дерево позволяет быстро искать данные без полного сканирования таблицы:

Полный поиск O(N):   проверяем каждую строку
Поиск в B-tree O(log N): логарифмический поиск

На 1 миллионе строк:
- Полный поиск:  1 000 000 проверок
- B-tree поиск:  ~20 проверок (log2(1M) ≈ 20)

Структура B-tree (самая распространенная)

Визуально B-tree выглядит так:

              [25, 50]
             /    |     \
        [10,20] [30,40] [60,70,80]
        /    \   /   \   /   |    \
      [5] [15] [32] [45] [65] [75] [85]

Свойства B-tree:
- Сбалансированное (все листья на одном уровне)
- Каждый узел содержит несколько значений (не только 2)
- Хорошо использует память дисковые блоки
- Быстрые поиск, вставка, удаление: O(log N)

Зачем нужны в БД?

1. Быстрый поиск по индексированным колонкам

CREATE INDEX idx_users_email ON users(email);

SELECT * FROM users WHERE email = 'john@test.com';
-- Использует B-tree индекс: O(log N) вместо O(N)

Практический пример:

import psycopg2

conn = psycopg2.connect("dbname=test")
cursor = conn.cursor()

# Без индекса: 1M строк = 1M проверок
# С индексом: 1M строк = 20 проверок (B-tree на диске)

cursor.execute("""
    EXPLAIN ANALYZE
    SELECT * FROM users WHERE email = 'john@test.com';
""")

for row in cursor.fetchall():
    print(row)  # Видим разницу в execution time

2. Сортировка данных

-- B-tree уже отсортировано!
SELECT * FROM users ORDER BY email;
-- Быстро, так как индекс уже в нужном порядке

-- Без индекса пришлось бы сортировать O(N log N)

3. Диапазонные запросы

CREATE INDEX idx_price ON products(price);

-- B-tree позволяет найти диапазон эффективно
SELECT * FROM products WHERE price BETWEEN 10 AND 50;
-- Находит первый узел >= 10, потом идет по листьям до 50

4. PRIMARY KEY и UNIQUE constraints

CREATE TABLE users (
    id SERIAL PRIMARY KEY,  -- Автоматический B-tree индекс
    email VARCHAR(255) UNIQUE  -- Тоже B-tree
);

-- Быстрая проверка уникальности
-- Быстрый поиск по ID

Сложность операций на B-tree

Операция          | Сложность | Пример
------------------|-----------|--------
Поиск             | O(log N)  | WHERE id = 5
Вставка           | O(log N)  | INSERT
Удаление          | O(log N)  | DELETE
Сортировка        | O(1)*     | ORDER BY (уже в индексе)
Диапазон          | O(log N + K) | WHERE x BETWEEN a AND b
Полный скан       | O(N)      | SELECT * (без WHERE)

*Если используется индекс и количество результатов K

Типы B-tree в разных БД

PostgreSQL: B-tree (стандартный)

from sqlalchemy import Index

class User(Base):
    __tablename__ = 'users'
    id = Column(Integer, primary_key=True)
    email = Column(String(255), index=True)  # B-tree
    created_at = Column(DateTime)
    
    __table_args__ = (
        Index('idx_created_recent', 'created_at'),
    )

MySQL: B+tree (варианта B-tree)

B+tree отличается от B-tree:
- Данные только в листьях
- Листья связаны между собой (как linked list)
- Лучше для range queries

Когда НЕ использовать B-tree:

-- Hash индекс для точного совпадения (быстрее на одиночных поисках)
CREATE INDEX idx_user_id USING HASH ON users(id);

-- GiST/GIN для специальных типов
CREATE INDEX idx_location USING gist ON places(location);  -- геоданные
CREATE INDEX idx_tags USING gin ON articles(tags);  -- JSON, массивы

-- Full-text индекс для текстового поиска
CREATE INDEX idx_search ON articles USING gin(search_vector);

Практический пример: оптимизация медленного запроса

# Проблема: медленный запрос
from sqlalchemy import text

# ❌ МЕДЛЕННО: полный скан таблицы
def find_active_users_by_email(email_pattern: str):
    # На 1M пользователей: 1M проверок
    return session.query(User).filter(
        User.email.like(f'{email_pattern}%'),
        User.is_active == True
    ).all()

# Проверяем план выполнения
result = session.execute(text("""
    EXPLAIN ANALYZE
    SELECT * FROM users 
    WHERE email LIKE 'john%' AND is_active = true;
""")

for row in result:
    print(row)  # Seq Scan = полный скан (плохо)

# ✅ БЫСТРО: добавляем индекс
class User(Base):
    __tablename__ = 'users'
    id = Column(Integer, primary_key=True)
    email = Column(String(255), index=True)  # B-tree индекс
    is_active = Column(Boolean)
    
    __table_args__ = (
        # Составной индекс для двух полей
        Index('idx_active_users_email', 'is_active', 'email'),
    )

# Теперь запрос:
# Index Scan = использует B-tree индекс
# На 1M пользователей: ~20 узлов в B-tree

Как выглядит B-tree на диске

Паметь компьютера (RAM):        Диск:
┌─────────────────────┐
│  B-tree root (8KB)  │  ← одного дискового блока
├─────────────────────┤
│  Cached nodes       │        Когда нужны данные:
│  (несколько MB)     │        Читаем 4-8KB блок
└─────────────────────┘        O(log N) блоков
        ↓                       ~20 блоков для 1M записей
      Диск
     ┌──────┐
     │Block1│ <- 4-8KB, содержит индекс данные
     │Block2│
     │Block3│
     └──────┘

Б-tree оптимизирована под размер дисковых блоков!
Этот один из главных плюсов.

Сравнение: B-tree vs Linear search

# Таблица: 1 миллион пользователей

# Без индекса (Linear search)
total_time = 0
for i in range(1_000_000):
    if users[i].email == "john@test.com":
        # Найден, но только после ~500K проверок
        break
# Время: ~50ms на медленном диске

# С B-tree индексом
btree_search_depth = 20  # log(1M) ≈ 20
total_time = 0
for _ in range(btree_search_depth):
    # Каждая итерация: одно обращение к диску (~5ms)
    read_disk_block()
# Время: ~100ms (но константа, не зависит от размера)

# На практике B-tree еще быстрее благодаря кэшированию

Визуализация поиска в B-tree

Ищем email = "john@test.com"

1. Читаем root: [alice, michael, zoe]
   "john" > "alice" and "john" < "michael"
   → идём в средний узел

2. Читаем узел: [james, john, joseph]
   "john" == "john" → НАЙДЕН!

Всего 2 дисковых обращения вместо миллиона

Важные свойства B-tree

✅ Балансировка: все операции O(log N) ✅ Cache-friendly: работает с дисковыми блоками ✅ Масштабируемость: O(log N) даже на петабайтах ✅ Поддержка диапазонов: эффективные range queries ✅ Стабильность: гарантированная сложность

Когда индекс неэффективен

-- Полный скан все равно
SELECT * FROM users WHERE is_active = true;
-- Потому что результатов 80% таблицы
-- Дешевле просканировать всё, чем прыгать по индексу

-- Неиспользуемый индекс
SELECT * FROM users WHERE user_id > 1000000;
-- Результатов < 1%, индекс помогает

Вывод

B-tree нужны в БД для:

✅ Скорость поиска: O(log N) вместо O(N) ✅ Поддержка PRIMARY KEY: быстрый доступ по ID ✅ UNIQUE constraints: быстрая проверка уникальности ✅ Сортировка: ORDER BY использует индекс ✅ Диапазонные запросы: BETWEEN, <, > ✅ Масштабируемость: работают на петабайтах данных ✅ Эффективность: используют дисковые блоки оптимально

Это фундамент современных БД. Без B-tree невозможны быстрые запросы на больших данных.