Як працює 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