Какая скорость доступа у индекса B-Tree в БД?

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

B-Tree — это основная структура индексирования в современных БД (PostgreSQL, MySQL, SQLite). Понимание его производительности критично для оптимизации запросов.

1. Временная сложность B-Tree

Сложность: O(log n), где n — количество записей

Маленькая БД (1000 записей):
  log₂(1000) ≈ 10 операций

Большая БД (1 миллион записей):
  log₂(1000000) ≈ 20 операций

Энормная БД (1 миллиард записей):
  log₂(1000000000) ≈ 30 операций

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

B-Tree — это сбалансированное дерево, где каждый узел содержит несколько ключей:

Порядок B-Tree (часто 128-256):

                    [50, 150, 250]
                   /      |      \
              [25,40]  [75,125]  [175,225]  [275,300]
               / |  \    / |  \   / |  \    / |  \
              ...........................

Важно: Каждый узел может содержать М ключей, поэтому глубина дерева намного меньше:

# Пример: B-Tree порядка 128
def calculate_tree_depth(n_records, order=128):
    import math
    # Максимальное количество записей на каждом уровне
    # Корень: 1 узел с М ключами
    # Уровень 1: М узлов
    # Уровень 2: М² узлов
    # Уровень k: М^k узлов
    
    depth = math.ceil(math.log(n_records, order))
    return depth

print(f\"1 миллион записей: глубина {calculate_tree_depth(1_000_000)}\")  # 3-4
print(f\"1 миллиард записей: глубина {calculate_tree_depth(1_000_000_000)}\")  # 4-5

3. Физическая скорость доступа

Операции на диске:

Каждый узел B-Tree находится в одном блоке диска (обычно 4KB - 8KB)

Время доступа:
- Случайный доступ к диску: ~5-10 мс
- Доступ к памяти: ~10 нс (в 1 миллион раз быстрее)

Для поиска по индексу:
- B-Tree глубиной 3-4 = 3-4 случайных доступа
- Время: 15-40 мс типично
- Без индекса (full table scan): до 1-2 секунд

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

import time
import sqlite3

# Создаём БД
db = sqlite3.connect(:memory:)
cursor = db.cursor()

# Таблица без индекса
cursor.execute(\"CREATE TABLE users_no_index (id INTEGER, name TEXT)\")
for i in range(1_000_000):
    cursor.execute(\"INSERT INTO users_no_index VALUES (?, ?)\", (i, fUser{i}))
db.commit()

# Таблица с индексом
cursor.execute(\"CREATE TABLE users_with_index (id INTEGER, name TEXT)\")
for i in range(1_000_000):
    cursor.execute(\"INSERT INTO users_with_index VALUES (?, ?)\", (i, fUser{i}))
cursor.execute(\"CREATE INDEX idx_users_id ON users_with_index(id)\")
db.commit()

# Тест без индекса (full table scan)
start = time.time()
cursor.execute(\"SELECT * FROM users_no_index WHERE id = 999999\")
no_index_time = time.time() - start

# Тест с индексом (B-Tree)
start = time.time()
cursor.execute(\"SELECT * FROM users_with_index WHERE id = 999999\")
index_time = time.time() - start

print(f\"Без индекса: {no_index_time*1000:.2f} ms\")
print(f\"С индексом: {index_time*1000:.2f} ms\")
print(f\"Ускорение: {no_index_time/index_time:.0f}x\")

Результаты типичные:

Без индекса: 50-100 ms (полный скан)
С индексом: 0.5-2 ms (B-Tree)
Ускорение: 50-100x

5. Типы индексов и их скорость

B-Tree (умолчание в PostgreSQL/MySQL):

Поиск точного значения: O(log n)
Поиск диапазона: O(log n + k), где k — результаты
Поиск с LIKE: O(log n + k) если prefix
Поиск с IS NULL: O(log n)

Примеры:
SELECT * FROM users WHERE id = 100           -- O(log n), ~20 ips для 1M
SELECT * FROM users WHERE id BETWEEN 100 AND 200  -- O(log n + 100)
SELECT * FROM users WHERE name LIKE John% -- O(log n + k)

Hash индекс (быстрее для точного поиска):

Поиск точного значения: O(1)
Поиск диапазона: не поддерживается

Примеры:
SELECT * FROM users WHERE id = 100           -- O(1), мгновенно
SELECT * FROM users WHERE id > 100           -- не может использовать

GiST/GIN (для полнотекстового поиска):

Полнотекстовый поиск: O(log n)
Поиск по JSON: O(log n)

6. Когда B-Tree теряет эффективность

Проблема 1: Невыборочный индекс

-- Индекс есть, но вернёт 50% таблицы
SELECT * FROM users WHERE active = true;  -- Медленнее, чем full scan!

-- Решение: composite index
CREATE INDEX idx_users_active_id ON users(active, id);

Проблема 2: Левый префикс в LIKE

-- Индекс на (name) не помогает
SELECT * FROM users WHERE name LIKE %john%;  -- Full scan

-- Решение: полнотекстовый индекс
CREATE INDEX idx_users_name_fts ON users USING GIN(to_tsvector(russian, name));

Проблема 3: Функции в WHERE

-- Индекс не используется
SELECT * FROM users WHERE UPPER(name) = JOHN;  -- Full scan

-- Решение: functional index
CREATE INDEX idx_users_name_upper ON users(UPPER(name));

7. Оптимизация индексов

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

-- Composite index (a, b, c)
CREATE INDEX idx_composite ON table(a, b, c);

-- Помогает при:
SELECT * FROM table WHERE a = 1 AND b = 2 AND c = 3;  -- O(log n)
SELECT * FROM table WHERE a = 1 AND b = 2;            -- O(log n)
SELECT * FROM table WHERE a = 1;                       -- O(log n)

-- НЕ помогает при:
SELECT * FROM table WHERE b = 2;                       -- Full scan
SELECT * FROM table WHERE c = 3;                       -- Full scan

Правило ESC (Equality, Sort, Comparison):

-- Плохо:
CREATE INDEX idx ON orders(date, status, amount);

-- Хорошо (ESC порядок):
CREATE INDEX idx ON orders(status, date, amount);  -- E, C, S
-- status = ? (Equality)
-- date BETWEEN ? AND ? (Comparison)
-- ORDER BY amount (Sort)

8. Мониторинг и отладка

PostgreSQL: EXPLAIN ANALYZE

EXPLAIN ANALYZE
SELECT * FROM users WHERE id = 100;

-- Output:
-- Index Scan using idx_users_id on users (cost=0.29..8.30 rows=1)
--   Index Cond: (id = 100)
--   Planning Time: 0.042 ms
--   Execution Time: 0.105 ms

MySQL: EXPLAIN FORMAT=JSON

EXPLAIN FORMAT=JSON
SELECT * FROM users WHERE id = 100;

-- Смотрим на \"key\" (используется ли индекс)
-- Смотрим на \"rows\" (сколько строк скано)

9. Реальные измерения

import sqlite3
import time
import random

db = sqlite3.connect(:memory:)
cursor = db.cursor()

# Создаём таблицу
cursor.execute(\"CREATE TABLE products (id INTEGER PRIMARY KEY, price REAL)\")
for i in range(1_000_000):
    cursor.execute(\"INSERT INTO products VALUES (?, ?)\", (i, random.uniform(0, 1000)))
db.commit()

# Тест: 1000 поисков
times = []
for _ in range(1000):
    random_id = random.randint(1, 1_000_000)
    start = time.time()
    cursor.execute(\"SELECT * FROM products WHERE id = ?\", (random_id,))
    times.append(time.time() - start)

average_time = sum(times) / len(times)
print(f\"Среднее время поиска: {average_time*1000:.3f} ms\")
print(f\"Min: {min(times)*1000:.3f} ms\")
print(f\"Max: {max(times)*1000:.3f} ms\")

10. Выводы

B-Tree индекс = O(log n), очень быстро:

Практические советы:

• Добавляй индекс на столбцы в WHERE
• Для range queries: BETWEEN, <, >
• Для LIKE: только если prefix (%value не работает)
• Следи за кардинальностью (избегай индексов на boolean)
• Используй EXPLAIN для проверки
• Регулярно анализируй с ANALYZE/VACUUM

B-Tree индексы — это магия современных БД, превращающая часы поиска в миллисекунды!