CS Notes

btree

12 min read

B-tree

Предпосылки: B+ дерево, страницы и кортежи (ctid, структура страницы), CREATE INDEX — основы.

← VACUUM | GIN →

PostgreSQL называет свой индекс “B-tree”, но технически это B+tree с модификациями, основанный на статье Lehman & Yao (1981) — “Efficient Locking for Concurrent Operations on B-Trees”. B-tree — индекс по умолчанию: при CREATE INDEX без указания метода PostgreSQL создаёт именно его.

От Seq Scan к индексу

Допустим, в интернет-магазине есть таблица orders с 10 миллионами заказов. Клиент открывает страницу заказа — приложение выполняет SELECT * FROM orders WHERE id = 7482013. Без индекса PostgreSQL выполняет Seq Scan: читает все страницы таблицы подряд, проверяя каждую строку. 10 миллионов строк при средней длине строки 150 байт — это примерно 180 000 страниц по 8 КБ. На HDD, где каждое случайное чтение стоит ~10 мс, последовательное чтение 180 000 страниц занимает несколько секунд. Даже на SSD это сотни миллисекунд — неприемлемо для интерактивного запроса.

B-tree индекс по id решает эту задачу за 3–4 чтения страниц. Дерево высотой 3–4 уровня покрывает миллиарды ключей, потому что каждая внутренняя страница (8 КБ) вмещает сотни разделителей. Спуск от корня к листу — это 3–4 random I/O (при холодном кэше), и ещё одно чтение из heap за самой строкой. На SSD это < 1 мс, на HDD — десятки миллисекунд вместо секунд.

Данные таблицы (heap) и индекс — разные файлы. Heap хранит строки в порядке вставки, без сортировки. Индекс — отдельная B+tree-структура, где ключи отсортированы и каждый содержит ctid — физический адрес строки в heap. После поиска по индексу PostgreSQL идёт в heap за данными строки — это random I/O, и его стоимость определяет выбор стратегии сканирования.

Цена B-tree прямая: отдельный файл на диске, который нужно поддерживать при каждом INSERT, DELETE и UPDATE — модификация страниц индекса плюс запись в WAL. А поскольку PostgreSQL обновляет строки через версии (MVCC), индексы на активно изменяемых таблицах накапливают мусор и зависят от VACUUM.

Физическая структура

Индекс — файл из страниц по 8 КБ. Нулевая страница — meta page (указатель на корень и метаданные). Остальные страницы — внутренние (internal) и листовые (leaf). Каждая содержит стандартный заголовок страницы (pd_lsn, pd_lower, pd_upper) и специальную область (special space) с указателями на соседей.

Leaf page:
┌──────────────────────────────────────────────────────┐
│  Page Header (24 байта)                              │
│    pd_lsn: LSN последнего изменения                  │
│    pd_lower / pd_upper: границы свободного места     │
├──────────────────────────────────────────────────────┤
│  Item Pointers: [ItemId 1][ItemId 2][ItemId 3]...    │
├──────────────────────────────────────────────────────┤
│  Free Space                                          │
├──────────────────────────────────────────────────────┤
│  Index Tuples (растут снизу вверх)                   │
│    каждый: [t_tid + t_info + key_data]               │
├──────────────────────────────────────────────────────┤
│  Special Space                                       │
│    btpo_prev / btpo_next: связь с соседними листьями │
│    btpo_level: 0 для листьев                         │
│    btpo_flags: leaf? root? deleted?                  │
└──────────────────────────────────────────────────────┘

Что хранится в index tuple

Содержимое index tuple различается для листовых и внутренних страниц:

Index Tuple (лист):
┌─────────────────────────────────────────┐
│  t_tid: (block, offset)                 │  <-- ctid строки в heap
│  t_info: размер и флаги                 │
│  key_data: значение ключа               │  <-- например, id=7482013
└─────────────────────────────────────────┘

Index Tuple (внутренний узел):
┌─────────────────────────────────────────┐
│  t_tid: (child_block, offset)           │  <-- указатель на дочернюю страницу
│  t_info: размер и флаги                 │
│  key_data: разделитель (pivot)          │  <-- граница для навигации
└─────────────────────────────────────────┘

В листе t_tid — это ctid строки в heap: когда B-tree находит нужный ключ, он использует ctid, чтобы прочитать строку из таблицы. Во внутреннем узле t_tid указывает на дочернюю страницу индекса, а key_data — разделитель (pivot), по которому дерево решает, идти влево или вправо при спуске.

При конкурентной вставке страница может разделиться (split) в тот момент, когда другой процесс её читает. Lehman & Yao решают это двумя дополнениями к классическому B+tree.

Каждая страница (кроме самой правой на уровне) содержит high key — верхнюю границу ключей на странице. Если при поиске ключ >= high key, значит страница разделилась и нужно перейти вправо по right-link (btpo_next в special space). Это позволяет обходиться блокировкой только тех страниц, которые непосредственно модифицируются, — без блокировки всего дерева.

Страница A                          Страница B
┌─────────────────────┐            ┌─────────────────────┐
│ high_key = 50       │            │ high_key = 100      │
│ keys: 10, 20, 30, 40│            │ keys: 50, 60, 70, 80│
│ btpo_next ----------│----------->│                     │
└─────────────────────┘            └─────────────────────┘

Index Scan: точечные запросы и диапазоны

Вернёмся к магазину. SELECT * FROM orders WHERE id = 7482013 выполняется как Index Scan: спуск от корня к листу, нахождение ключа, один поход в heap по ctid, возврат строки.

Теперь менеджер хочет список заказов за январь: SELECT * FROM orders WHERE created_at >= '2026-01-01' AND created_at < '2026-02-01' ORDER BY created_at. B-tree по created_at спускается до листа с первым ключом >= ‘2026-01-01’ и дальше проходит по двусвязному списку листьев (btpo_next) вправо, пока ключи < ‘2026-02-01’. Каждый найденный index tuple даёт ctid для похода в heap.

Двусвязность (наличие btpo_prev) нужна для обратного обхода. SELECT * FROM orders ORDER BY created_at DESC LIMIT 100 спускается до самого правого листа и идёт влево — в плане это Index Scan Backward.

Для каждого найденного ключа Index Scan ходит в heap по ctid — это random I/O (HDD vs SSD). Если запрос возвращает десятки тысяч строк, разбросанных по разным страницам heap, random I/O становится узким местом.

Bitmap Index Scan: средняя селективность

Запрос вернёт 2–15% строк таблицы (например, заказы за целый квартал). Index Scan создаст десятки тысяч random I/O в heap. Seq Scan прочитает всю таблицу последовательно — тоже дорого. PostgreSQL использует третий вариант — Bitmap Index Scan, двухфазное сканирование.

Фаза 1: чтение индекса и построение битовой карты страниц heap, содержащих нужные строки. Фаза 2: чтение этих страниц в порядке номеров (ближе к sequential I/O, каждая страница читается ровно один раз).

Bitmap страниц heap:
Page:  0   1   2   ...  123  ...  291  ...  532  ...
Bit:   0   0   0   ...   1   ...   1   ...   1   ...

Бонус Bitmap: можно комбинировать несколько индексов. Запрос WHERE created_at >= '2026-01-01' AND status = 'shipped' может использовать BitmapAnd двух индексов — по created_at и по status — каждый даёт свою битовую карту, их пересечение даёт только нужные страницы.

Планировщик выбирает стратегию по оценке селективности: Index Scan при < 1–2% строк, Bitmap Index Scan при 2–15%, Seq Scan при > 15%. Подробнее — в планировщике.

Index Only Scan: обход без heap

Менеджер просит сводку: SELECT created_at, amount FROM orders WHERE created_at >= '2026-01-01' AND created_at < '2026-02-01'. Если индекс содержит только created_at, PostgreSQL вынужден ходить в heap за amount. Но если все нужные колонки уже в индексе — heap fetch не нужен. Это Index Only Scan.

Ограничение: Index Only Scan работает только если страница heap помечена как “all-visible” в Visibility Map (VM) — битовой карте, где каждый бит указывает, что все строки на соответствующей странице видимы всем транзакциям (подробнее — VACUUM и MVCC). Если страница недавно менялась и VM ещё не обновлена, PostgreSQL всё равно ходит в heap за проверкой видимости.

Covering Index (INCLUDE, PostgreSQL 11+) решает проблему: дополнительные колонки хранятся в листьях индекса, но не участвуют в сортировке.

CREATE INDEX idx_orders_created_covering
ON orders(created_at)
INCLUDE (amount, status);

Теперь SELECT created_at, amount, status FROM orders WHERE created_at >= '2026-01-01' может выполниться как Index Only Scan — ноль обращений к heap (если VM актуальна). Цена — индекс крупнее, каждый лист содержит больше данных.

Составные индексы и правило левого префикса

Часто нужны запросы по нескольким колонкам: «все заказы пользователя за последний месяц». Составной индекс (user_id, created_at) — один B-tree с многокомпонентным ключом, где записи отсортированы сначала по user_id, при равенстве — по created_at.

Запрос WHERE user_id = 42 AND created_at >= '2026-01-01' использует индекс полностью: спуск до user_id=42, затем проход по created_at внутри этого пользователя. Но WHERE created_at >= '2026-01-01' без user_id индекс использовать не может — данные отсортированы сначала по user_id, и в каждом «поддиапазоне» пользователя дата идёт с начала.

Это правило левого префикса. Для индекса (A, B, C):

WHERE A = ?                     ✓ использует индекс
WHERE A = ? AND B = ?           ✓ использует индекс
WHERE A = ? AND B = ? AND C = ? ✓ использует индекс
WHERE A = ? AND C = ?           △ только по A, C фильтруется отдельно
WHERE B = ?                     ✗ индекс бесполезен
WHERE C = ?                     ✗ индекс бесполезен

Аналогия — телефонный справочник, отсортированный по (фамилия, имя): можно найти всех Ивановых, но нельзя эффективно найти всех с именем Иван.

Индекс также помогает с ORDER BY, если порядок совпадает с ключом: ORDER BY user_id, created_at — бесплатная сортировка. ORDER BY user_id ASC, created_at DESC поддерживается через индекс со смешанным порядком: CREATE INDEX ON orders(user_id ASC, created_at DESC).

Уникальные индексы

UNIQUE INDEX запрещает дубликаты. CREATE UNIQUE INDEX idx_email ON users(email) — при INSERT/UPDATE PostgreSQL проверяет, нет ли уже такого значения в индексе. Проверка — это поиск по B-tree, то есть O(log N).

UNIQUE CONSTRAINT (ALTER TABLE ... ADD CONSTRAINT ... UNIQUE) создаёт тот же индекс, но дополнительно регистрирует ограничение в pg_constraint:

АспектUNIQUE CONSTRAINTUNIQUE INDEX
Хранениеpg_constraint + pg_indexтолько pg_index
Цель FOREIGN KEYДаДа (если не partial)
DEFERRABLEДаНет
Partial (WHERE)НетДа
INCLUDE колонкиДа (PG 11+)Да

CONSTRAINT нужен, когда на колонку ссылается внешний ключ другой таблицы или когда проверка должна быть отложена до COMMIT (DEFERRABLE). UNIQUE INDEX гибче: поддерживает частичную уникальность и дополнительные колонки через INCLUDE.

Partial Unique Index — уникальность только для подмножества строк:

CREATE UNIQUE INDEX idx_email_active ON users(email) WHERE deleted_at IS NULL;

Позволяет реализовать soft delete с повторным использованием email: удалённые пользователи не мешают уникальности.

Мутации: INSERT, DELETE, UPDATE

Сканирование читает индекс. Но магазин обрабатывает 100 000 заказов в день — каждый INSERT, DELETE и UPDATE модифицирует дерево. Стоимость этих мутаций определяет реальную цену B-tree.

INSERT и page split

Каждый новый заказ добавляет index tuple в соответствующий лист. Если на странице есть свободное место — вставка и запись в WAL. Если лист полон — происходит split по алгоритму Lehman & Yao:

  1. Спуск до целевого листа.
  2. Вставка ключа — лист переполняется.
  3. Создание новой страницы. Половина ключей переносится в неё. На обеих страницах устанавливаются high key и right-link.
  4. Добавление разделителя в родительский узел (отдельный шаг, может вызвать каскадный split).

Между шагами 3 и 4 дерево «временно неконсистентно»: родитель ещё не знает о новой странице. Но right-link позволяет читателям, попавшим на старую страницу, корректно перейти на новую — именно для этого Lehman & Yao и добавили high key и right-link (описаны выше).

Observable cost: split порождает запись нескольких страниц (старая, новая, родитель) плюс WAL-записи для каждой. При массовой вставке это заметно как всплески latency.

DELETE — нет merge

Заказы старше трёх лет архивируются и удаляются. В учебном B-дереве при удалении выполняется заимствование или слияние (merge) узлов. PostgreSQL этого не делает:

До DELETE:     [10, 20, 30, 40, 50]

После DELETE 30: [10, 20,  _,  40, 50]
                          ^
                    dead tuple (помечен как удалённый, физически на месте)

Три причины, почему PostgreSQL не делает merge. Во-первых, merge требует одновременной блокировки нескольких страниц (текущей, соседней, родительской), что создаёт contention при высоком параллелизме. Во-вторых, удалённая запись может быть ещё видна другим транзакциям через MVCC — физически удалять её нельзя до VACUUM. В-третьих, освободившееся место обычно быстро занимается новыми записями. Dead tuples накапливаются до следующего VACUUM.

UPDATE = новая версия + обновление индексов

В магазине заказы постоянно меняют статус: pending → paid → shipped → delivered. При UPDATE PostgreSQL не изменяет строку in-place — он создаёт новую версию в heap (MVCC). Старая версия помечается через xmax, новая получает свой ctid.

До UPDATE:
  (id=1, status='pending')  ctid=(100,1)  xmin=500, xmax=∞

После UPDATE SET status='paid':
  (id=1, status='pending')  ctid=(100,1)  xmin=500, xmax=600  <-- мёртвая
  (id=1, status='paid')     ctid=(100,5)  xmin=600, xmax=∞   <-- живая

Все индексы на таблице должны получить новую запись, указывающую на ctid=(100,5). Старая запись в индексе — dead tuple, ожидающая VACUUM. При 100 000 обновлений статуса в день на таблице с тремя индексами — это 300 000 dead index tuples в день.

HOT: UPDATE без обновления индексов

HOT (Heap-Only Tuples) — оптимизация (PostgreSQL 8.3+), при которой новая версия строки создаётся без вставки записей в индексы. Работает при двух условиях: изменяемые колонки не входят ни в один индекс, и новая версия помещается на ту же страницу heap.

Если у таблицы orders индексы только по id и created_at, а UPDATE меняет status — HOT применим. Индексы продолжают указывать на старый ctid. При поиске PostgreSQL доходит до старой версии по ctid из индекса и перенаправляется на новую версию через указатель в heap (HOT chain).

Heap page 100:
  (1) (id=1, status='pending')  DEAD, HOT chain -> (5)
  (5) (id=1, status='paid')     LIVE

Index по id:
  [id=1, ctid=(100,1)]  <-- НЕ ИЗМЕНИЛСЯ

Мониторинг HOT:

SELECT relname, n_tup_upd, n_tup_hot_upd,
       round(100.0 * n_tup_hot_upd / nullif(n_tup_upd, 0), 1) as hot_pct
FROM pg_stat_user_tables WHERE relname = 'orders';

Хороший показатель — hot_pct > 90%. Если процент низкий, стоит проверить: возможно, один из индексов включает изменяемую колонку, и его можно убрать или перепроектировать.

Bloat: следствие MVCC для индекса

Даже с HOT dead tuples накапливаются. После множества DELETE и UPDATE индекс содержит полупустые страницы — это bloat (раздувание). Следствия: больше страниц при сканировании (Index Scan читает больше), больше места на диске, полезные данные вытесняются из буферного кэша.

VACUUM чистит dead tuples в индексе, освобождая место внутри страниц для повторного использования:

До VACUUM:    [10, 20, DEAD, DEAD, 50, DEAD, 70]
После VACUUM: [10, 20, 50, 70,  _,  _,  _]
                                 свободное место

Но VACUUM не уменьшает размер файла индекса — освобождённые страницы остаются в файле. Если bloat серьёзный, нужен REINDEX:

REINDEX INDEX idx_orders_id;                -- блокирует таблицу
REINDEX INDEX CONCURRENTLY idx_orders_id;   -- PostgreSQL 12+, без блокировки

Operator classes и collation

B-tree требует операторов сравнения для типа данных. Operator class (операторный класс) — набор из пяти стратегий (<, ⇐, =, >=, >) и support function compare(a, b), определяющих порядок для конкретного типа. Для стандартных типов (integer, text, uuid, timestamp) operator classes создаются автоматически; указывать их вручную нужно редко.

Для строковых типов порядок определяется collation — правилами сравнения символов. Collation “C” выполняет побайтовое сравнение: предсказуемый порядок (по ASCII/UTF-8 кодам), ‘Z’ < ‘a’ (заглавные перед строчными), быстрое. Локализованная collation (например, “en_US.UTF-8”) учитывает языковые правила: ‘a’ < ‘B’ < ‘c’, регистронезависимая сортировка.

Практическое следствие: LIKE 'prefix%' использует B-tree индекс только при collation “C” или со специальным operator class text_pattern_ops. При локализованной collation PostgreSQL не может гарантировать, что байтовый префикс совпадает с логическим, и индекс не применяется:

-- При локализованной collation обычный индекс не поможет с LIKE
-- Специальный operator class решает проблему:
CREATE INDEX idx_email_pattern ON users(email text_pattern_ops);
SELECT * FROM users WHERE email LIKE 'john%';  -- теперь использует индекс

Версии (выборочно)

ВерсияИзменения в B-tree
11 (2018)Covering indexes (INCLUDE)
12 (2019)REINDEX CONCURRENTLY
13 (2020)Дедупликация

B-tree покрывает точные совпадения, диапазоны и сортировку. Когда нужно заглянуть внутрь составных значений — массивов, JSONB, полнотекстовых векторов — работает GIN.

Sources

← VACUUM | GIN →

Graph View

Backlinks