В первых двух уроках мы рассмотрели «статическую» структуру B+tree — как страница выглядит, что в ней лежит. Теперь — самое интересное: что происходит, когда страница переполняется и Postgres вынужден её делить. Эта операция — page split — самая дорогая в индексе, и именно она объясняет, почему последовательные INSERT работают в разы быстрее случайных.

Page split: anatomy

Каждая страница B+tree — это 8 KiB. В неё помещается определённое число index tuples (для bigint-ключа — около 350-400 после suffix truncation). Когда приходит ещё один INSERT, и места не остаётся, Postgres делает page split:

1. Аллоцирует новую пустую страницу (на конце файла или из free space map).
2. Разделяет содержимое старой страницы примерно пополам (на самом деле — fillfactor-аware).
3. Записывает первые ~50% в старую страницу, оставшиеся — в новую.
4. Обновляет btpo_next старой страницы — теперь она указывает на новую.
5. Обновляет btpo_prev страницы, которая была справа от старой (если есть).
6. Вставляет в родительский узел новый разделитель — ссылку на новую страницу.
7. Если родительский узел тоже переполнен — рекурсивно split вверх.
8. Если split дошёл до root — создаётся новый root, дерево вырастает на уровень.
9. Все изменения пишутся в WAL отдельной записью XLOG_BTREE_SPLIT_L / XLOG_BTREE_SPLIT_R.

Стоимость split: пара page writes + WAL запись + потенциальный split родителя (редко). В худшем случае — full-tree split, когда split идёт вверх до корня. Это очень редко и амортизируется множеством обычных INSERT.

Right-link и конкурентные читатели

Самое красивое — что split не блокирует читателей, и в этом заслуга

1. Reader R1 читает root, узнаёт, что нужный ключ X в листе L. Берёт buffer pin на L.
2. Writer W1 переполняет L и делает split: L → L + L’. Ключ X переезжает на L’.
3. R1 наконец читает L (между шагом 1 и 3 был page lock), не находит X.
4. R1 смотрит на high_key страницы L. Видит, что high_key < X — значит, X переехал направо.
5. R1 идёт по btpo_next на L’, находит X.

Без right-link шаг 5 был бы невозможен — R1 пришлось бы вернуться к root, заново обойти дерево. Это потеря производительности и потенциальный deadlock с другими операциями.

На уровне исходников Postgres: см. _bt_moveright() в nbtsearch.c. Каждый раз перед чтением tuple читатель проверяет high_key и при необходимости двигается направо. Это и есть «move right» из B-link.

Split-этап и WAL: тонкости

Между «решил split» и «зафиксировал split» проходит несколько этапов, и в каждом есть свои гарантии:

1. Хранение в буфере. Сначала Postgres модифицирует буфер в shared_buffers (RAM). Никакого диска.
2. Запись в WAL. Перед commit транзакции изменения попадают в WAL. WAL — это последовательный лог, в который пишут все DML.
3. Group commit. WAL flush’ится на диск либо по таймеру, либо когда наберётся достаточно записей.
4. Checkpoint. Через какое-то время checkpoint форсит запись «грязных» страниц из shared_buffers на диск (в файлы данных).

Split — это set из нескольких операций, которые должны быть атомарными. Postgres использует механизм «full-page images» — в WAL запись о split содержит копии обеих страниц (старой и новой). Это позволяет recovery восстановить корректное состояние, даже если в момент крэша одна из страниц не успела записаться.

Цена: WAL-запись на split — это 8-16 KiB. На горячих таблицах с миллионами splits в день WAL pаспухает. На реальных продах WAL trafic от splits может составлять 20-30% общего объёма.

Sequential inserts: счастливый случай

Если ты вставляешь в индекс в монотонном порядке (например, id SERIAL, BIGSERIAL, или inserted_at TIMESTAMP NOW()), то все новые записи попадают в самый правый лист. И когда этот лист переполняется, происходит split — но rightmost split, оптимизированный кейс:

• Старая страница остаётся почти полной (по fillfactor).
• Новая пустая.
• Все следующие INSERT пишутся в новую страницу, пока она не переполнится.
• Никакого «среднего разрезания» — данные не перемещаются.

Postgres даже распознаёт паттерн «append-only» и применяет оптимизацию: если ты вставляешь подряд возрастающие ключи, fillfactor применяется агрессивнее (старая страница заполняется почти на 100%, новая получает только новые данные).

В итоге: последовательные inserts → почти нет splits → high cache hit rate → быстро.

Random inserts: антипаттерн

Если ключ случайный (UUID v4, hash от чего-то, рандомный идентификатор), каждый INSERT попадает в случайный лист. Что это значит:

1. Splits происходят везде, во всех листьях понемногу.
2. Каждый split разрезает страницу примерно пополам — half-empty pages засоряют дерево.
3. Buffer cache теряет горячий tail — нет «правого хвоста», который всегда в RAM. Все страницы более-менее холодные.
4. WAL пишется много: каждый split — отдельная запись.
5. Высота дерева растёт быстрее: больше страниц → больше уровней.

На бенчмарках разница между BIGSERIAL и uuid v4 default как PK на таблице в 100M строк — обычно 2-4x по latency для INSERT и 2-3x по размеру индекса.

Обычно индекс по UUID на 30-50% больше индекса по BIGSERIAL при том же числе строк. На реальных таблицах с миллионами записей разница ещё драматичнее.

Buffers: shared hit=N read=M показывает, сколько страниц затронуто. Для INSERT в среднюю страницу — это страницы heap + страницы индексов + WAL. Чем больше индексов, тем больше «амплификация».

L&Y и invariants

Чтобы алгоритм B-link tree работал корректно, должны соблюдаться несколько инвариантов. Перечислим их явно — это полезно для понимания, что именно делает Postgres под капотом:

1. На любом моменте времени каждая страница имеет валидный high_key (кроме самой правой на уровне — у неё high_key отсутствует или +inf). Это значит: если на странице есть ключ X, то X <= high_key.

2. btpo_next указывает на страницу, которая содержит ключи > high_key текущей. То есть переход по right-link гарантированно ведёт к большему диапазону.

3. Split атомарен с точки зрения WAL. Старая страница и новая обновляются одной WAL-записью; recovery всегда видит дерево либо до split, либо после, но не «в процессе».

4. Родительский указатель добавляется лениво. Между моментом «split на уровне K» и «вставка разделителя на уровне K+1» проходит микроскопическое, но ненулевое время. В это время дерево находится в incomplete state: новая страница уже существует, но на неё ещё нет ссылки из родителя. Читатели находят её через right-link — это и есть гениальность Lehman-Yao.

5. Если split на уровне K+1 не успел произойти, новый писатель видит «обрыв» в parent и сам делает _bt_finish_split — доделывает чужую работу. Это decentralized model, который не требует глобального lock’а.

fillfactor и hot-pages

fillfactor — параметр индекса, регулирующий, насколько плотно заполнять страницу при создании/перестройке. По умолчанию для B-tree он 90:

• При CREATE INDEX или REINDEX каждая leaf-страница заполняется на 90%.
• Оставшиеся 10% — «резерв» под будущие INSERT.
• При INSERT в страницу, где есть место, split не происходит — пишем в свободное место.

Тонкости:

• fillfactor = 100 для append-only данных: место в середине страницы не понадобится, все новые ключи идут в правый хвост. Экономит 10% размера индекса.
• fillfactor = 70-80 для интенсивно изменяющихся данных: больше места под INSERT, меньше splits, но больше размер.
• fillfactor для rightmost-split: даже если ты выставил fillfactor = 90, при rightmost split Postgres делает «99/1» — заполняет старую почти до конца, новую оставляет почти пустой. Это специальная оптимизация для sequence-PK.

Эффект на bulk loads

Когда ты загружаешь миллион строк в новую таблицу с PK и парой индексов, splits происходят постоянно. Но это самый дешёвый сценарий — потому что все splits rightmost, страницы в кэше горячие, WAL пишется последовательно.

Чтобы ускорить bulk load:

1. Загрузка в COPY без активных индексов — самый быстрый вариант. Дроп индексы, делай COPY, потом CREATE INDEX. Билд индекса с нуля — на порядок быстрее, чем поддержка индекса в процессе COPY (потому что построение работает на отсортированных данных, без splits).

2. UNLOGGED TABLE для staging — отключает WAL для таблицы, ускоряет inserts в 2-5x. Минус: при крахе содержимое теряется. Подходит для ETL pipeline.

3. maintenance_work_mem побольше — на время CREATE INDEX поставь SET maintenance_work_mem = '4GB'. Помогает сортировке во время билда.

4. max_wal_size выше — иначе бенжамин будет упираться в checkpoint’ы.

В целом: если знаешь, что предстоит bulk load, отключение индексов и их перестроение после загрузки — стандартный приём. Это применяется в pg_restore, pg_dump --create-with-no-indexes, dbmate и других инструментах.

Что делать с уже фрагментированным индексом

Если индекс уже «изжёванный» — много half-empty страниц после рандомных inserts — то даже после изменения паттерна (например, перевели на BIGSERIAL) индекс не уменьшится сам по себе. VACUUM убирает мёртвые записи, но не уплотняет страницы. Нужен REINDEX или REINDEX CONCURRENTLY (мы рассмотрим в уроке 6).

Diagnostic-запрос: pgstatindex('idx_name') из расширения pgstattuple показывает фрагментацию индекса:

• avg_leaf_density — средняя плотность листьев. На свежесозданном индексе ~80-90%, на фрагментированном — 40-60%.
• leaf_fragmentation — насколько листья «разбросаны» по файлу. Высокое значение = много random I/O при range scan.

WAL и crash recovery

Каждый page split пишется в WAL как отдельная запись — XLOG_BTREE_SPLIT_L или XLOG_BTREE_SPLIT_R в зависимости от того, в какую сторону происходит split. В записи содержится:

• block number старой и новой страниц;
• LSN изменения;
• содержимое новой страницы;
• updated high_key старой страницы;
• ссылка на родительский узел и offset для нового разделителя.

Если сервер падает между шагом «записал в WAL» и «применил к данным», recovery догонит изменение — WAL гарантирует atomicity. Если сервер падает в момент split, на recovery WAL «доделает» split: создаст недостающую страницу, обновит right-link, добавит разделитель в родителя. С точки зрения корректности — split неделим.

С точки зрения нагрузки на WAL: при random-insert pattern, как мы обсудили, splits происходят повсеместно — и каждый порождает большую WAL-запись (порядка 8 KiB, потому что в неё кладётся содержимое новой страницы). На горячих таблицах это становится заметной долей всего WAL-трафика, что нагружает archiver, replication и pg_basebackup.

Реальный кейс: hot leaf под нагрузкой

Sequential insert pattern имеет ещё одну специфику. Все INSERT попадают в один и тот же rightmost leaf — пока он не заполнится. Это значит, что эта страница горячая: десятки backend’ов одновременно хотят писать в неё.

Postgres использует buffer content lock на уровне страницы (тип EXCLUSIVE на запись). Если 100 параллельных INSERT’ов идут в одну страницу, они выстраиваются в очередь — что является source of LWLock contention. На бенчмарках это видно как «hot tail» — единственная страница, на которой все backend’ы спинятся.

Решения:

• Параллельные partition’ы (модуль 12): каждый partition имеет свой rightmost leaf, lock distributed.
• Hash-партиционирование PK: ключи распределяются по N partition’ам, каждый имеет свою «правую» страницу.
• На очень больших OLTP (NVMe и десятки CPU) — synchronous_commit = off или commit_delay сокращают время удержания lock’а.

Тонкость: UUID v7 спасает

Если по бизнес-логике нужен UUID (например, distributed system, где нельзя полагаться на sequence), но не хочется страдать от random inserts — есть UUID v7 (timestamp-based). Первые 48 бит UUID v7 — это unix timestamp в миллисекундах, что делает ключ почти монотонным. Splits ведут себя как при sequence-PK, при этом сохраняется глобальная уникальность.

В Postgres 18 будет встроенный uuidv7(), до тех пор — extension pg_uuidv7 или генерация на стороне приложения.

Что почитать дальше

• Lehman & Yao (1981), “Efficient Locking for Concurrent Operations on B-Trees” — оригинальная статья про B-link tree. Семь страниц, читается за вечер. Любой DBA должен иметь её в библиотеке.
• Peter Geoghegan, “PostgreSQL Indexing: Best Practices” — обновляемые слайды от core-разработчика nbtree. Питер сделал большую часть оптимизаций B-tree в PG 12-15.
• Postgres source: src/backend/access/nbtree/README — небольшой документ, который объясняет реализацию изнутри. Бесценный ресурс, если хочется не «общими словами», а конкретно.

Что мы не разобрали

Несколько тем, которые относятся к B-tree, но рассматриваются в других модулях:

• Lock contention на hot leaf — отдельная тема в модуле 10 (locks & concurrency). Здесь мы только упомянули.
• WAL и replica lag при page splits — рассмотрим в модуле 13 (WAL & replication).
• Bloat и vacuum — урок 6 этого же модуля.
• GIN, GiST, BRIN, Hash — модуль 3. Это другие типы индексов, не B-tree; они существуют в Postgres параллельно и решают другие задачи.

Чек-лист

• Page split — деление переполненной страницы на две + добавление разделителя в родителя.
• Right-link (B-link tree) позволяет читателям не блокироваться на split: при необходимости они идут по btpo_next.
• Sequential inserts (BIGSERIAL, timestamp) → rightmost split, оптимальная производительность.
• Random inserts (UUID v4, hash) → splits повсеместно, индекс на 30-50% больше, INSERT в 2-4x медленнее.
• fillfactor = 90 по умолчанию; для append-only можно поднять до 100, для интенсивных обновлений — снизить до 70-80.
• При замене pattern (например, переход на UUID v7) фрагментированный индекс не уплотняется сам — нужен REINDEX CONCURRENTLY.