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

🟢 Junior Level

B-tree (Balanced Tree) — это сбалансированное дерево, которое PostgreSQL использует для хранения индексов по умолчанию.

Почему «balanced»? Все пути от корня до листа одинаковой длины. Это гарантирует, что любой поиск займёт одинаковое время — не будет «плохих» случаев, как в обычном бинарном дереве, которое может выродиться в linked list.

Простая аналогия: Представьте оглавление в книге, разбитое на уровни:

Верхний уровень: разделы (Главы 1-10)
Средний уровень: подразделы (1.1, 1.2, 1.3…)
Нижний уровень: конкретные страницы

Чтобы найти страницу, вы спускаетесь сверху вниз, отбрасывая ненужные разделы.

Основная идея:

Все данные отсортированы
Поиск происходит быстро: даже в миллионе элементов нужно проверить ~20-30 сравнений
PostgreSQL автоматически поддерживает баланс дерева

Пример:

-- Создаём B-tree индекс (по умолчанию)
CREATE INDEX idx_users_email ON users(email);

-- Поиск по индексу: O(log n) вместо O(n)
SELECT * FROM users WHERE email = 'test@example.com';

Когда использовать:

Для большинства случаев (это индекс по умолчанию)
Для поиска по равенству: WHERE id = 5
Для поиска по диапазону: WHERE price BETWEEN 100 AND 500
Для сортировки: ORDER BY created_at DESC

🟡 Middle Level

Как это работает внутри

Индекс хранится в страницах по 8 КБ. Структура иерархическая:

Root (корень)
  ├── Internal Node → Internal Node → Leaf Node
  └── Internal Node → Leaf Node

Структура страницы:

Page Header — метаданные (LSN — Log Sequence Number, номер записи в WAL-логе для восстановления после сбоев; контрольные суммы для проверки целостности)
Index Tuples — пары ключ + TID (указатель на строку в таблице)
Special Area — ссылки на соседние страницы (P_NEXT, P_PREV)
High Key — максимальное значение на странице

Алгоритм поиска

Начинаем с Root страницы
Сравниваем искомое значение с ключами
Спускаемся в нужный дочерний узел
Повторяем, пока не дойдём до Leaf страницы
В Leaf находим TID и читаем строку из таблицы

Почему B-tree, а не обычное бинарное дерево?

Характеристика	Бинарное дерево	B-tree (PostgreSQL)
Фактор ветвления	2 (левый/правый)	100+ (много дочерних узлов)
Высота для 1 млн записей	~20 уровней	~3-4 уровня
I/O операций	Много	Минимум (читаем страницами)

Типичные ошибки

Попытка индексировать всё
- B-tree занимает место на диске и в RAM
- Каждый INSERT/UPDATE требует обновления индекса

Неправильный порядок в составном индексе

-- Индекс (last_name, first_name)
-- ✅ Будет использован
WHERE last_name = 'Ivanov'
   
-- ✅ Будет использован
WHERE last_name = 'Ivanov' AND first_name = 'Ivan'
   
-- ❌ НЕ будет использован (или неэффективно)
WHERE first_name = 'Ivan'

Поиск с функциями

-- ❌ Индекс не будет использован
WHERE UPPER(name) = 'IVAN'
   
-- ✅ Создайте функциональный индекс
CREATE INDEX idx_users_name_upper ON users(UPPER(name));

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

Для полнотекстового поиска → используйте GIN
Для геоданных → используйте GiST
Только для равенства и нужна минимальная занимаемая память → Hash
Для массивов и JSONB → GIN

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

-- B-tree поддерживает сортировку
CREATE INDEX idx_orders_date ON orders(created_at DESC);

-- Запрос без сортировки (данные уже отсортированы в индексе)
SELECT * FROM orders ORDER BY created_at DESC LIMIT 10;
-- Plan: Index Scan Backward (очень быстро)

🔴 Senior Level

Internal Implementation

Реализация B-tree в PostgreSQL основана на модифицированном алгоритме Lehman and Yao, который обеспечивает высокую конкурентность без блокировки всего пути от корня до листа.

Структура Meta-page (страница 0):

Meta-page
  ├── Magic number (идентификатор типа индекса)
  ├── Version
  ├── Root page number
  └── Fastroot (кэш корня для ускорения)

Структура Leaf Node:

┌─────────────────────────────────┐
│ Page Header (16 байт)           │
├─────────────────────────────────┤
│ ItemId_1 → IndexTuple_1         │
│ ItemId_2 → IndexTuple_2         │
│ ...                             │
├─────────────────────────────────┤
│ High Key (максимальное значение)│
├─────────────────────────────────┤
│ Special Area (P_NEXT, P_PREV)   │
└─────────────────────────────────┘

High Key: Критически важен для корректности поиска во время параллельных сплитов. Если при спуске видим, что значение > High Key → переходим по P_NEXT без возврата к корню.

Алгоритм конкурентного доступа

Поиск:

Берём кратковременную AccessShareLock на страницу (легковесная блокировка, которая не мешает другим процессам читать страницу параллельно)
Спускаемся вниз, освобождая блокировку на родительских страницах
Даже если параллельный процесс делает Split, поиск остаётся корректным

Page Split:

До сплита:          После сплита:
┌──────────┐        ┌──────────┐   ┌──────────┐
│ A B C D E│  →     │ A B C    │→  │ D E      │
└──────────┘        └──────────┘   └──────────┘
                         ↑
                    Parent обновлен

Создаём новую страницу “справа”
Перемещаем половину данных
Обновляем родительский узел
Важно: INCLUDE-колонки НЕ хранятся в Internal узлах, только в Leaf

Современные оптимизации (PG 13+)

На PG 12 и ниже дедупликация отсутствует — каждый ключ хранится отдельно. При большом количестве дубликатов индекс раздувается значительно сильнее. Решение: регулярный REINDEX.

Дедупликация:

-- PostgreSQL 13+ объединяет одинаковые ключи
-- Было: (key=1, TID=1), (key=1, TID=2), (key=1, TID=3)
-- Стало: (key=1, TIDs=[1,2,3])

-- Особенно эффективно для колонок с низкой кардинальностью
CREATE INDEX idx_orders_status ON orders(status);
-- Низкая кардинальность = много повторяющихся ключей. Вместо хранения
-- (key='ACTIVE', TID=1), (key='ACTIVE', TID=2), ..., (key='ACTIVE', TID=1000000)
-- дедупликация хранит: (key='ACTIVE', TIDs=[1,2,...,1000000])
-- → экономия пропорциональна количеству дубликатов: 70-90% места

LP_DEAD marking:

При удалении строки в Heap, в индексе запись помечается LP_DEAD
VACUUM физически удаляет такие записи
Важно: VACUUM освобождает место внутри страниц, но НЕ уменьшает физический размер файла на диске

Edge Cases

Bloat (раздувание)

-- Диагностика через pgstattuple
SELECT * FROM pgstatindex('idx_users_email');
-- avg_leaf_density < 50% → время для REINDEX
   
-- Лечение
REINDEX INDEX CONCURRENTLY idx_users_email;

Fill Factor

-- Для часто обновляемых индексов резервируем место
CREATE INDEX idx_orders_status ON orders(status) WITH (fillfactor = 70);
-- 30% страницы остаётся свободным для обновлений
-- Минимизирует Page Splits

Corrupted Index

-- Проверка целостности
SELECT bt_page_items('idx_users_email', 1);
   
-- Пересоздание после сбоя
REINDEX DATABASE my_database;

Производительность

Сложность операций:

Поиск: O(logₙ N), где n — фактор ветвления (обычно 100-1000)
Высота дерева для 1 млрд записей: 3-4 уровня
I/O операций для поиска: 3-4 чтения страниц

Memory Footprint:

Каждая запись в индексе: ~16-24 байта + размер ключа
Для 100 млн записей с int-ключом: ~2-3 ГБ индекса
Критично: Индекс должен помещаться в shared_buffers (RAM)

Production Experience

Реальный сценарий:

E-commerce платформа: 500 млн заказов
Проблема: Индекс на order_id раздулся до 50 ГБ (Bloat 60%)
Симптом: Запросы замедлились в 10 раз, Cache Miss rate > 40%
Решение:
- REINDEX CONCURRENTLY (без блокировки)
- Добавили fillfactor = 80 при пересоздании
- Результат: Индекс стал 20 ГБ, Cache Hit rate > 95%

Monitoring

-- Проверка состояния индекса
SELECT 
    indexrelname,
    pg_size_pretty(pg_relation_size(indexrelid)) as size,
    idx_scan,
    idx_tup_read,
    idx_tup_fetch
FROM pg_stat_user_indexes
WHERE relname = 'orders';

-- Проверка Bloat
SELECT 
    index_name,
    bloat_pct,
    real_size,
    extra_size
FROM pg_index_bloat_stats
WHERE schemaname = 'public';

-- Проверка уровня дерева
SELECT * FROM pgstatindex('idx_orders_id');
-- tree_level = 0 → всё в одной странице
-- tree_level = 3 → нормальное большое дерево

Best Practices

Используйте CONCURRENTLY для создания/пересоздания в production
Устанавливайте fillfactor = 70-80 для часто обновляемых индексов
Регулярно проверяйте avg_leaf_density через pgstattuple
Дедупликация включена по умолчанию в PG 13+ — убедитесь, что используете актуальную версию
Мониторьте размер индексов относительно RAM

Резюме для Senior

B-tree — дисковая структура, оптимизированная под конкурентность (Lehman & Yao)
High Key обеспечивает корректность поиска во время параллельных сплитов
INCLUDE-колонки только в Leaf узлах — не раздувают дерево поиска
Дедупликация (PG 13+) радикально уменьшает Bloat для низкокардинальных колонок
REINDEX CONCURRENTLY — основной инструмент борьбы с Bloat в production

🎯 Шпаргалка для интервью

Обязательно знать:

B-tree — иерархическая структура: Root → Internal → Leaf (TID → Heap)
Фактор ветвления 100+ → высота 3-4 уровня даже для 1 млрд записей
Сложность поиска: O(logₙ N), где n — фактор ветвления
Lehman-Yao алгоритм: конкурентный доступ без блокировки всего пути
High Key — максимальное значение на странице, нужен для корректности при сплитах
Дедупликация (PG 13+): объединяет одинаковые ключи → экономия 70-90% места
fillfactor = 70-80 для часто обновляемых индексов → меньше сплитов

Частые уточняющие вопросы:

«Почему B-tree, а не бинарное дерево?» → B-tree фактор ветвления 100+ vs 2, меньше I/O
«Что такое Page Split и почему это плохо?» → деление страницы при вставке → Bloat
«Как дедупликация экономит место?» → (key=1, TIDs=[1,2,3]) вместо 3 отдельных записей
«Что будет, если Bloat 60%?» → Cache Miss, Random I/O, REINDEX CONCURRENTLY
«Почему INCLUDE-колонки только в Leaf?» → Не раздувают Internal узлы → меньше уровней дерева

Красные флаги (НЕ говорить):

❌ «B-tree — это бинарное дерево» (нет, B-tree = многопоточное дерево)
❌ «VACUUM уменьшает размер файла индекса» (нет, нужен REINDEX)
❌ «Дедупликация работает для всех индексов» (только PG 13+, не для уникальных)

Связанные темы:

[[Для чего нужны индексы]] → обзор типов индексов
[[Что такое составной индекс]] → лексикографическая сортировка
[[Что такое кардинальность индекса]] → дедупликация для низкокардинальных колонок
[[Как работает MVCC в PostgreSQL]] → TID, HOT, Visibility Map