Индекс по bigint на миллион строк оказался деревом из трёх уровней и 2 745 страниц по 8 КБ: корень, внутренние страницы, листья, а страницы каждого уровня ещё и связаны ссылками вправо. Создание индекса и план запроса разобраны в статье про индексы PostgreSQL; здесь вскрываем сам B-tree через pageinspect и код nbtree: high key, усечение ключей, дедупликацию и skip scan 18.
B-tree на 1 млн строк: уровни, high key и right-link
Опыт 1: корень, внутренняя страница и листья
Поднимаем PostgreSQL 18, создаём индекс по bigint на миллион строк и смотрим его метастраницу.
docker run -d --name dba-btree-internals-postgres -e POSTGRES_PASSWORD=pg postgres:18
docker exec -it dba-btree-internals-postgres psql -U postgresCREATE EXTENSION pageinspect;
CREATE TABLE t (id bigint);
INSERT INTO t SELECT g FROM generate_series(1, 1000000) g;
CREATE INDEX t_id ON t (id);
SELECT root, level, (SELECT relpages FROM pg_class WHERE relname = 't_id') AS pages FROM bt_metap('t_id'); root | level | pages
------+-------+-------
290 | 2 | 2745Корень лежит в странице 290, level = 2: до листа два шага вниз. Статистика четырёх страниц: корня, первой внутренней (3) и двух первых листьев (1 и 2).
SELECT s.blkno, s.type, s.live_items, s.free_size, s.btpo_prev, s.btpo_next, s.btpo_level
FROM unnest(ARRAY[290, 3, 1, 2]) AS n, bt_page_stats('t_id', n) AS s; blkno | type | live_items | free_size | btpo_prev | btpo_next | btpo_level
-------+------+------------+-----------+-----------+-----------+------------
290 | r | 10 | 7956 | 0 | 0 | 2
3 | i | 285 | 2456 | 0 | 289 | 1
1 | l | 367 | 808 | 0 | 2 | 0
2 | l | 367 | 808 | 1 | 4 | 0Листья заполнены на 90%: free_size = 808 из 8 192 — это fillfactor 90, который CREATE INDEX оставляет листьям под будущие вставки. Страницы одного уровня образуют двусвязный список: у листа 1 btpo_prev = 0 (левее никого), btpo_next = 2; у листа 2 prev = 1, next = 4. Корень и крайняя правая страница уровня имеют btpo_next = 0. Эти поля лежат в special-области страницы: в куче она пуста (см. устройство страницы), а у листа 1 page_header показывает special = 8176, то есть 16 байт в конце страницы.
Что внутри корня, внутренней страницы и листьев:
SELECT itemoffset, ctid, itemlen, data FROM bt_page_items('t_id', 290) WHERE itemoffset <= 3;
SELECT itemoffset, ctid, itemlen, data FROM bt_page_items('t_id', 3) WHERE itemoffset <= 3;
SELECT itemoffset, ctid, itemlen, data FROM bt_page_items('t_id', 1) WHERE itemoffset <= 2;
SELECT itemoffset, ctid, itemlen, data FROM bt_page_items('t_id', 2) WHERE itemoffset = 2; itemoffset | ctid | itemlen | data
------------+---------+---------+-------------------------
1 | (3,0) | 8 |
2 | (289,1) | 16 | 09 96 01 00 00 00 00 00
3 | (575,1) | 16 | 11 2c 03 00 00 00 00 00
1 | (286,1) | 16 | 09 96 01 00 00 00 00 00
2 | (1,0) | 8 |
3 | (2,1) | 16 | 6f 01 00 00 00 00 00 00
1 | (1,1) | 16 | 6f 01 00 00 00 00 00 00
2 | (0,1) | 16 | 01 00 00 00 00 00 00 00
2 | (1,141) | 16 | 6f 01 00 00 00 00 00 00Четыре результата показаны одним блоком. На внутренних страницах ctid — это номер дочерней страницы, а data — разделитель в little-endian: 09 96 01 — это 0x019609 = 103945. Первый элемент корня (3,0) без ключа — ссылка на самое левое поддерево, «минус бесконечность»; второй, (289,1) с ключом 103945, ведёт в страницу 289, где ключи начинаются с 103945. У страницы 3, которая не самая правая на уровне, первым лежит high key — тот же 103945: верхняя граница её собственных ключей. High key листа 1 (6f 01 = 367) равен первому ключу листа 2 (6f 01, последний результат) и разделителю (2,1) в странице 3. Поэтому у листа 1 live_items = 367: 366 ключей (1…366) и один high key.
Зачем нужны и high key, и ссылка вправо, объясняет README nbtree, REL_18_6:
When a search follows a downlink to a child page, it compares the page's
high key with the search key. If the search key is greater than the high
key, the page must've been split concurrently, and you must follow the
right-link to find the new page containing the key range you're looking
for. This might need to be repeated, if the page has been split more than
once.Источник: nbtree/README, строки 24–29. Это правило Лемана и Яо: читатель спускается, не держа блокировку на родителе, а если страницу тем временем разделили, ему хватает сравнить ключ с high key и сдвинуться вправо. Поэтому разделение страницы не останавливает чтения.
Опыт 2: разделение страницы и усечение суффикса
В листьях нужен весь ключ, а во внутренних страницах и в high key — ровно столько, чтобы отличить левую страницу от правой. Усечение работает на уровне столбцов, а не байтов внутри значения; проверим на длинных ключах. Ключ b — 211 символов с общим префиксом, строим два индекса: по (a, b) и по одному b, и вставляем строки в случайном порядке, чтобы страницы делились настоящими разделениями, а не пакетной сборкой CREATE INDEX.
CREATE TABLE lk (a int, b text);
CREATE INDEX lk_ab ON lk (a, b);
CREATE INDEX lk_b ON lk (b);
INSERT INTO lk
SELECT g / 10, repeat('common-prefix-of-long-string-', 7) || lpad(g::text, 8, '0')
FROM generate_series(1, 200000) g ORDER BY random();
SELECT 'lk_ab' AS idx, st.type, i.itemlen, count(*)
FROM generate_series(1, pg_relation_size('lk_ab') / 8192 - 1) n, bt_page_stats('lk_ab', n) st, bt_page_items('lk_ab', n) i
GROUP BY 2, 3 ORDER BY 2, 3;Тот же запрос для lk_b. Тип страницы: l — лист, i — внутренняя, r — корень.
idx | type | itemlen | count
-------+------+---------+--------
lk_ab | i | 8 | 139
lk_ab | i | 16 | 5758
lk_ab | i | 232 | 2722
lk_ab | l | 16 | 5758
lk_ab | l | 232 | 202722
lk_ab | r | 8 | 1
lk_ab | r | 16 | 138
lk_b | i | 8 | 362
lk_b | i | 224 | 8808
lk_b | l | 224 | 208459
lk_b | r | 8 | 1
lk_b | r | 224 | 11Для (a, b) листья хранят 200 000 ключей по 232 байта, а разделители бывают двух размеров: 16 байт (заголовок, a и выравнивание) и полные 232. 5 896 из 8 618 разделителей (68%) состоят из одного a: на границе страниц a менялся, и b в разделитель не попал. Остальные 2 722 остались с b: на границе стояли строки с одним a. Элементы по 8 байт — «минус бесконечность», по одному на внутреннюю страницу.
В одностолбцовом lk_b усечь нечего: все 8 808 внутренних элементов по 224 байта равны листовым. Усечение отбрасывает хвост из столбцов, а общий префикс внутри text не трогает. Точку разделения выбирает _bt_findsplitloc; комментарий над ней (nbtsplitloc.c, REL_18_6) задаёт приоритеты:
* truncation will be. The implementation picks the split point that
* maximizes the effectiveness of suffix truncation from a small list of
* alternative candidate split points that leave each side of the split with
* about the same share of free space. Suffix truncation is secondary to
* equalizing free space, except in cases with large numbers of duplicates.Источник: nbtsplitloc.c, строки 108–112. Сначала страница делится поровну, и только среди почти равных точек выбирается та, где разделитель короче; поэтому 32% разделителей остались полными.
Опыт 3: дедупликация
Индекс по столбцу с 10 значениями на миллион строк хранит каждое значение 100 000 раз. С PostgreSQL 13 одинаковые ключи сворачиваются в posting list: один ключ и список адресов строк. Строим два одинаковых индекса, один с выключенной дедупликацией.
CREATE TABLE d (k int);
INSERT INTO d SELECT g % 10 FROM generate_series(1, 1000000) g;
CREATE INDEX d_off ON d (k) WITH (deduplicate_items = off);
CREATE INDEX d_on ON d (k) WITH (deduplicate_items = on);
SELECT relname, pg_relation_size(oid) AS bytes, relpages FROM pg_class
WHERE relname IN ('d_off', 'd_on') ORDER BY 1 DESC; relname | bytes | relpages
---------+----------+----------
d_on | 6963200 | 850
d_off | 22519808 | 2749Индекс с дедупликацией в 3,2 раза меньше (22 519 808 / 6 963 200). Посмотрим на первый лист каждого.
SELECT 'd_on' AS idx, live_items, free_size FROM bt_page_stats('d_on', 1)
UNION ALL SELECT 'd_off', live_items, free_size FROM bt_page_stats('d_off', 1);
SELECT itemoffset, itemlen, array_length(tids, 1) AS n_tids FROM bt_page_items('d_on', 1) WHERE itemoffset <= 3; idx | live_items | free_size
-------+------------+-----------
d_on | 10 | 812
d_off | 367 | 800
itemoffset | itemlen | n_tids
------------+---------+--------
1 | 24 |
2 | 808 | 132
3 | 808 | 132Без дедупликации лист хранит 366 записей по 16 байт, по одной на строку. С ней ту же страницу занимают high key и 9 posting list, все по 132 адреса: 808 = 16 + 132 × 6. Это 1 188 адресов на страницу вместо 366 при той же заполненности (free 812 и 800).
Укладывает дубликаты в списки _bt_dedup_pass. Её главный цикл по элементам страницы (nbtdedup.c, REL_18_6):
else if (state->deduplicate &&
_bt_keep_natts_fast(rel, state->base, itup) > nkeyatts &&
_bt_dedup_save_htid(state, itup))
{
/*
* Tuple is equal to base tuple of pending posting list. Heap
* TID(s) for itup have been saved in state.
*/
}Источник: nbtdedup.c, строки 150–158. Если ключ равен базовому кортежу ожидающего списка (_bt_keep_natts_fast(...) > nkeyatts), его адрес дописывается в список; иначе накопленный список закрывается и начинается новый. Проход запускается, когда страница заполнена и нужно место для вставки, прежде чем её делить.
Дедупликация включается не всегда: bt_metap показывает флаг allequalimage, а для text она недоступна при недетерминированной коллации (документация).
Опыт 4: skip scan в PostgreSQL 18
Заметки о выпуске 18 объявляют «Allow skip scans of btree indexes»: составной индекс работает и без условия на ведущие столбцы. Проверяем на индексе (status, created_at): три значения status, миллион строк.
CREATE TABLE o (id bigint, status text, created_at timestamp);
INSERT INTO o SELECT g, (ARRAY['new','paid','shipped'])[1 + g % 3],
timestamp '2026-01-01' + g * interval '30 seconds' FROM generate_series(1, 1000000) g;
CREATE INDEX o_sc ON o (status, created_at);
VACUUM ANALYZE o;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM o WHERE created_at = '2026-03-01 12:00:00'; Index Scan using o_sc on o (cost=0.42..21.74 rows=1 width=21) (actual time=0.045..0.107 rows=1.00 loops=1)
Index Cond: (created_at = '2026-03-01 12:00:00'::timestamp without time zone)
Index Searches: 7
Buffers: shared hit=9 read=15
Execution Time: 0.115 ms(Вывод сокращён: строки Planning опущены.) Планировщик выбрал Index Scan сам, без SET. Признак skip scan — Index Searches: 7: индекс обошли семью спусками, перепрыгивая между значениями status. Почему спусков семь при трёх значениях, здесь не разбирается. Индекс занимает 3 853 страницы, запрос задел 24. Тот же запрос при enable_indexscan = off и enable_bitmapscan = off (узел Gather и счётчик отфильтрованных строк опущены):
Parallel Seq Scan on o (cost=0.00..11578.33 rows=1 width=21) (actual time=8.138..11.315 rows=0.33 loops=3)
Buffers: shared hit=6370
Execution Time: 15.960 ms6 370 буферов против 24, 15,96 мс против 0,115 мс (замеры подряд на одной машине, у индексного плана 15 буферов из 24 были read). Всё зависит от числа значений в ведущем столбце: по документации skip scan разумен, когда их мало, иначе планировщик предпочтёт Seq Scan. Те же строки, но 100 000 значений ведущего user_id:
CREATE TABLE o2 AS SELECT id, (id % 100000) AS user_id, created_at FROM o;
CREATE INDEX o2_uc ON o2 (user_id, created_at);
VACUUM ANALYZE o2;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM o2 WHERE created_at = '2026-03-01 12:00:00';
SET enable_seqscan = off;
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM o2 WHERE created_at = '2026-03-01 12:00:00'; Gather (cost=1000.00..12608.43 rows=1 width=24) (actual time=3.407..13.247 rows=1.00 loops=1)
-> Parallel Seq Scan on o2 (cost=0.00..11608.33 rows=1 width=24) (actual time=6.960..9.606 rows=0.33 loops=3)
Execution Time: 13.268 ms
Index Scan using o2_uc on o2 (cost=0.42..22916.43 rows=1 width=24) (actual time=17.140..26.691 rows=1.00 loops=1)
Index Searches: 1
Buffers: shared hit=3 read=3835 written=1246
Execution Time: 26.706 msПланировщик берёт Seq Scan (стоимость 12 608 против 22 916 у индекса). Принудительный индекс делает один поиск и читает 3 835 буферов при индексе в 3 853 страницы: почти весь индекс, вдвое дольше таблицы (26,7 мс против 13,3 мс). Пропускать нечего.
Что из этого следует
- Длинный ключ дорог везде. Усечение режет хвост из столбцов, а не байты внутри значения:
lk_bхранит 224 байта и в листьях, и в разделителях. Длинный текст надо укорачивать или хешировать в схеме; а в(a, b)68% разделителей свелись к одномуa, так что порядок столбцов важен. - Дедупликация сжала индекс по 10 значениям в 3,2 раза. Индекс, созданный до PostgreSQL 13 и перенесённый
pg_upgrade, нужно перестроитьREINDEX: так сказано в заметках о выпуске 13. - Skip scan не заменяет индекс по неведущему столбцу. Он выигрывает при единицах значений в ведущем столбце (24 буфера против 6 370); при 100 000 планировщик берёт таблицу.
Чек-лист для работы с B-tree
- Уровень и размер смотри в
bt_metapиpg_relation_size. Сравниitemlenв листьях и во внутренних страницах: если разделители не короче, усечение не работает. - Для индекса по столбцу с повторами проверь
allequalimageи размер приdeduplicate_itemson/off, прежде чем считать индекс раздутым. - Перед новым индексом по неведущему столбцу прогони
EXPLAIN (ANALYZE, BUFFERS)на существующем составном и посмотриIndex Searches. - Убери контейнер:
docker rm -f dba-btree-internals-postgres.