Внутреннее устройство B-дерева, структура страниц, алгоритмы поиска и вставки.
B-дерево — индекс по умолчанию в PostgreSQL. Понимание его внутреннего устройства критично для проектирования эффективных индексов и диагностики проблем.
B-дерево (B-Tree, Balanced Tree) — это самосбалансирующееся дерево поиска, которое хранит данные в отсортированном виде. Это индекс по умолчанию в PostgreSQL, используемый в 90%+ случаев.
| Операция | Пример | Эффективность |
|---|---|---|
| Равенство | WHERE id = 100 | ✅ Отлично |
| Сравнение | WHERE created_at > '2026-01-01' | ✅ Отлично |
| Диапазон | WHERE id BETWEEN 100 AND 200 | ✅ Отлично |
| Сортировка | ORDER BY created_at DESC | ✅ Отлично |
| LIKE с префиксом | WHERE email LIKE 'test@%' | ✅ Хорошо |
| IS NULL | WHERE deleted_at IS NULL | ✅ Хорошо |
B-дерево состоит из трёх типов узлов:
┌─────────────┐
│ ROOT │ ← Корневой узел
│ (уровень 2) │
└──────┬──────┘
│
┌─────────────────┼─────────────────┐
│ │ │
┌────▼────┐ ┌────▼────┐ ┌────▼────┐
│INTERNAL │ │INTERNAL │ │INTERNAL │ ← Внутренние узлы
│(уровень1)│ │(уровень1)│ │(уровень1)│
└────┬────┘ └────┬────┘ └────┬────┘
│ │ │
┌────┴────┐ ┌────┴────┐ ┌────┴────┐
▼ ▼ ▼ ▼ ▼ ▼
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
│ LEAF │ │ LEAF │ │ LEAF │ │ LEAF │ │ LEAF │ │ LEAF │ ← Листовые узлы
│(ключ,│ │(ключ,│ │(ключ,│ │(ключ,│ │(ключ,│ │(ключ,│
│ TID) │ │ TID) │ │ TID) │ │ TID) │ │ TID) │ │ TID) │
└──────┘ └──────┘ └──────┘ └──────┘ └──────┘ └──────┘
По умолчанию страница в PostgreSQL занимает 8 КБ (8192 байта).
-- Узнать размер страницы
SHOW block_size; -- 8192
-- Узнать размер индекса в страницах
SELECT
pg_relation_size('idx_users_email') / 8192 AS pages
FROM pg_class;┌─────────────────────────────────────────┐
│ PageHeaderData (24 байта) │ ← Заголовок
├─────────────────────────────────────────┤
│ SpecialSpace (варьируется) │ ← Служебные данные
├─────────────────────────────────────────┤
│ ItemId (4 байта каждый) │ ← Указатели
├─────────────────────────────────────────┤
│ Свободное место │
├─────────────────────────────────────────┤
│ Данные (ключи + указатели) │ ← Растут снизу вверх
└─────────────────────────────────────────┘
Fillfactor — процент заполнения страницы данными при создании/обновлении индекса.
-- Создать индекс с fillfactor 70%
CREATE INDEX idx_users_email ON users(email) WITH (fillfactor = 70);| Fillfactor | Когда использовать |
|---|---|
| 90 (по умолчанию) | Статические данные, редкие обновления |
| 70-80 | Частые обновления, вставки |
| 50-60 | Очень частые обновления, горячие таблицы |
Зачем оставлять место? При вставке нового ключа в заполненную страницу происходит split страницы (деление пополам), что дорого. Reserved space позволяет вставлять данные без split.
Рассмотрим поиск WHERE id = 157:
Шаг 1: Читаем ROOT
┌─────────────────────────┐
│ [50] │ [100] │ [200] │ ← Ключи-разделители
│ ↓ │ ↓ │ ↓ │
│ P1 │ P2 │ P3 │ ← Указатели
└─────────────────────────┘
│
▼ (157 >= 100 и 157 < 200, идём в P2)
Шаг 2: Читаем INTERNAL узел P2
┌─────────────────────────┐
│ [120]│ [140]│ [160]│ ← Ключи-разделители
│ ↓ │ ↓ │ ↓ │
│ L1 │ L2 │ L3 │ ← Указатели на листовые узлы
└─────────────────────────┘
│
▼ (157 >= 140 и 157 < 160, идём в L2)
Шаг 3: Читаем LEAF узел L2
┌─────────────────────────┐
│ (145, TID1) │
│ (147, TID2) │
│ (157, TID3) ← НАЙДЕНО! │
│ (159, TID4) │
└─────────────────────────┘
│
▼
Шаг 4: По TID3 читаем строку из таблицы
Количество чтений: 3 страницы индекса + 1 страница таблицы = 4 чтения
Для дерева высотой 3-4 (типично для миллионов строк) это чрезвычайно эффективно.
Если листовой узел заполнен:
До split (страница заполнена):
┌─────────────────────────────────┐
│ [10] [20] [30] [40] [50] [60] │ ← Нет места
└─────────────────────────────────┘
Вставляем 35:
После split:
┌─────────────────────┐ ┌─────────────────────┐
│ [10] [20] [30] │ │ [40] [50] [60] │
│ ↑ свободное место │ │ ↑ свободное место │
└─────────────────────┘ └─────────────────────┘
│
▼
В родительский узел добавляется разделитель [40]
Split — дорогая операция:
-- Fillfactor 100: split при первой же вставке в заполненную страницу
-- Fillfactor 90: 10% места резерв, меньше split
-- Fillfactor 70: 30% места резер, ещё меньше split, но больше размерВ PostgreSQL удаление работает иначе, чем в классическом B-дереве:
При DELETE или UPDATE:
-- После DELETE индекс не уменьшается сразу
DELETE FROM users WHERE id = 100;
-- Индекс всё ещё содержит запись для id=100 (помечена как удалённая)
-- VACUUM очищает мёртвые записи
VACUUM users;PostgreSQL не уменьшает размер файла индекса после удаления. Освободившиеся страницы помечаются как свободные и переиспользуются для новых вставок.
Высота дерева — количество уровней от корня до листьев.
| Высота | Примерный размер данных |
|---|---|
| 1 | До ~100 записей |
| 2 | До ~10 000 записей |
| 3 | До ~1 000 000 записей |
| 4 | До ~100 000 000 записей |
-- PostgreSQL 13+
SELECT
indexrelname,
pg_stat_get_numscans(indexrelid) as scans,
pg_relation_size(indexrelid) as size
FROM pg_stat_user_indexes
WHERE relname = 'users';
-- Через pgstattuple (расширение)
CREATE EXTENSION IF NOT EXISTS pgstattuple;
SELECT * FROM pgstatindex('idx_users_email');
-- Поле level = высота дерева - 1Почему это важно? Чем выше дерево, тем больше чтений диска для поиска. Но даже для миллиардов строк высота редко превышает 4-5.
B-дерево особенно эффективно для диапазонных запросов:
SELECT * FROM users
WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31'
ORDER BY created_at;2026-01-01) через дерево — O(log n)2026-01-31)Листовые узлы связаны в список:
┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐
│ LEAF │───▶│ LEAF │───▶│ LEAF │───▶│ LEAF │
│ │◀───│ │◀───│ │◀───│ │
└──────┘ └──────┘ └──────┘ └──────┘
↓ ↓ ↓ ↓
2025-12 2026-01 2026-02 2026-03
Преимущество: Не нужно возвращаться к внутренним узлам для каждой строки.
Если данные вставляются в порядке ключа (например, created_at):
Если ключи случайные (например, UUID):
-- Хуже: случайные UUID как первичный ключ
CREATE TABLE events (
id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
data TEXT
);
-- Лучше: последовательный ID + индекс по UUID
CREATE TABLE events (
id BIGSERIAL PRIMARY KEY,
uuid UUID UNIQUE DEFAULT gen_random_uuid(),
data TEXT
);
CREATE INDEX idx_events_uuid ON events(uuid);SELECT
indexname,
pg_size_pretty(pg_relation_size(indexname::regclass)) as size
FROM pg_indexes
WHERE tablename = 'users';SELECT
indexrelname,
idx_scan as scans,
idx_tup_read as tuples_read,
idx_tup_fetch as tuples_fetched
FROM pg_stat_user_indexes
WHERE relname = 'users';-- Простая оценка через pg_stat_user_indexes
SELECT
indexrelname,
pg_size_pretty(pg_relation_size(indexrelid)) as size,
idx_scan as scans
FROM pg_stat_user_indexes
WHERE relname = 'users'
ORDER BY pg_relation_size(indexrelid) DESC;
-- Точная оценка через pgstattuple
CREATE EXTENSION IF NOT EXISTS pgstattuple;
SELECT * FROM pgstatindex('idx_users_email');
-- Поле leaf_fragmentation показывает фрагментацию-- Обычное (блокирует таблицу)
REINDEX INDEX idx_users_email;
-- Конкурентное (без блокировок, PostgreSQL 12+)
REINDEX INDEX CONCURRENTLY idx_users_email;Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.