«У меня индекс на колонке, почему запрос медленный?» — самый частый вопрос на собеседованиях. И почти всегда ответ упирается в одно: спрашивающий не знает, что такое индекс физически. Не «дерево с ключами», а конкретный набор 8 KiB страниц с конкретной разметкой, по которым ходит читатель.

С этого модуля и до конца следующего мы будем разбирать только индексы — и начнём с самого важного: B+tree, дефолтного индекса в Postgres.

Что такое B-tree вообще

Прежде чем спускаться в детали реализации, нужно зафиксировать, зачем существует B-tree как структура. Это не дань традиции — это конкретное решение конкретной проблемы.

Проблема: у нас есть N значений, и нужно быстро отвечать на вопросы «есть ли в множестве X?», «отдай все в диапазоне [A, B]», «отсортируй по убыванию». Очевидное решение — сбалансированное двоичное дерево (AVL, red-black) — даёт O(log N) на каждую операцию. Но на диске у нас другая физика.

Чтение одного байта с HDD — это 5-10 ms на seek + ~1 ns на доставку. Чтение 8 KiB — те же 5-10 ms на seek + ~1 µs на доставку. Стоимость seek доминирует. На SSD seek дешевле, но всё равно стоит ~50 µs против ~1 ns внутренней операции — отличие в 50000 раз.

Это значит, что в дисковой структуре данных мы готовы «потратить» много CPU и места внутри одной страницы, лишь бы минимизировать число прочитанных страниц. B-tree (Bayer & McCreight, 1972) — это именно про это: высокий fan-out (сотни ключей на страницу) делает дерево очень низким (3-4 уровня для миллиардов записей). Каждый поиск — это 3-4 page reads вместо log2(1B) = 30 reads в binary tree.

B-tree vs B+tree: разница принципиальная

Когда в документации Postgres написано «B-tree index», на самом деле имеется в виду B+tree — модификация, в которой:

• Все данные (TID на heap-кортеж) хранятся только в листьях. Internal-узлы содержат только ключи-разделители и указатели на дочерние страницы. Это позволяет уплотнить internal-уровень и сделать дерево максимально низким.
• Листья связаны двусвязным списком. Соседние листовые страницы знают друг про друга — это нужно для range-scan: после исчерпания одной страницы прыгаем в right-sibling, не возвращаясь в root.

В классическом B-tree (Bayer & McCreight, 1972) данные были и в internal-узлах. На современных СУБД эта схема не используется почти никем — везде B+tree, как у Postgres, MySQL/InnoDB, SQLite.

Layout страницы B+tree

Каждая страница индекса — это всё та же 8 KiB страница, разделённая на ровно те же зоны, что и heap-страница. Разница в одном: special area не пустая, в ней лежит метаинформация B-tree.

Разберём special area. Это структура BTPageOpaqueData (16 байт):

• btpo_prev — указатель (block number) на левую соседнюю страницу того же уровня;
• btpo_next — указатель на правую соседнюю страницу;
• btpo_level — уровень в дереве (0 = leaf, 1, 2, … = internal);
• btpo_flags — биты: BTP_LEAF, BTP_ROOT, BTP_DELETED, BTP_HALF_DEAD, BTP_SPLIT_END.

Именно btpo_next и есть тот самый right-link из

Высота дерева: интуиция

Сколько уровней в B+tree на 1 миллиард строк? Это любимый вопрос. Считаем.

На каждой странице помещается ~(8 KiB - header - special) / (avg index tuple size) записей. Для индекса по bigint (8 байт ключ + 6 байт TID + 4 байта line pointer ≈ 18-24 байта на запись): получаем ~340-400 записей на страницу. Округлим до 200, чтобы учесть padding и overhead.

• 1 уровень (только root, он же leaf): до 200 строк.
• 2 уровня: root указывает на до 200 листьев, каждый — до 200 записей. Итого 40 000.
• 3 уровня: 200 × 200 × 200 = 8 миллионов.
• 4 уровня: 200⁴ = 1.6 миллиарда.

То есть до миллиарда строк хватает 4-х уровней. Это та самая магия B+tree: точечный поиск требует ровно log_fanout(N) page reads. На 1 миллиарде — 4 страницы (16 KiB). Этим и объясняется, почему WHERE id = X на таблице в 100 GiB отрабатывает за миллисекунду.

На 100K строк индекс примерно 2-3 MiB (200-400 страниц). Высота — 2 уровня: root и листья. Каждый поиск — ровно 2 page reads.

Index tuple: что внутри

В отличие от heap tuple, у index tuple структура проще:

• IndexTupleData header (8 байт): t_tid (heap TID — 6 байт) + t_info (длина и флаги — 2 байта).
• Null bitmap (если в индексе есть nullable-колонки).
• Сами значения ключей с alignment-паддингом.

В leaf-странице t_tid указывает на heap-кортеж — это и есть TID, по которому Postgres дойдёт до данных. В internal-странице t_tid указывает на дочернюю страницу индекса (block number, item offset).

Обрати внимание на Buffers: shared hit=N — это число прочитанных страниц. Для маленького дерева высоты 2 это будет 3 страницы: 2 уровня индекса + 1 heap-страница.

Что такое «pivot tuple»

В internal-страницах хранятся pivot tuples — это особый вид index tuple. От обычного leaf-tuple они отличаются двумя вещами:

1. TID указывает не на heap, а на дочернюю index-страницу. То есть t_tid = (block_in_index, item_in_index).
2. Ключ может быть «truncated». После suffix truncation (см. урок 2) pivot tuple содержит не полный ключ, а только префикс, достаточный для разделения двух дочерних страниц.

Высокий ключ (high_key) листовой страницы — это тоже pivot-tuple, лежит в специальном слоте P_HIKEY. Когда читатель приходит на лист, первым делом сравнивает искомый ключ с high_key: если искомый > high_key, нужно идти направо. Это та самая B-link оптимизация.

В internal-узлах самая первая запись (на offset P_FIRSTDATAKEY) — это «минус бесконечность», sentinel-значение, означающее «всё, что меньше первого реального разделителя». Это упрощает алгоритм бинарного поиска внутри страницы.

Lehman-Yao: B-link tree

В классическом B+tree конкурентный split — это проблема. Представь: читатель идёт от root к листу. По дороге писатель делает split листа, разделяя его на L и L’. Читатель приходит на L, не находит то, что ищет, — и не знает, что ключ переехал в L’.

Решение Lehman & Yao (1981) гениально просто: каждая страница знает свой right-sibling. Когда читатель не находит ключ на странице, но видит на ней «high key» меньше искомого, он идёт по btpo_next направо.

Эта схема позволяет писателям и читателям никогда не блокировать друг друга на одной странице (за исключением микро-секундной buffer pin). Это критическая оптимизация для OLTP-нагрузки, где сотни сессий одновременно читают и пишут.

Внутри Postgres: nbtree.c

Если хочется заглянуть в исходники — модуль src/backend/access/nbtree/ в Postgres-репозитории. Файл nbtsearch.c содержит _bt_search() — главный обход дерева. Загляни в _bt_moveright(): это та самая функция, которая на каждом шаге проверяет high_key и при необходимости прыгает по btpo_next. Прямая реализация Lehman-Yao, дополненная Postgres-специфичными штуками (например, обработкой удалённых страниц и dead-tuples).

Чем не отличается от heap

Файлы индекса лежат там же, где heap — в $PGDATA/base/<dbid>/<relfilenode>. Сегментируются так же по 1 GiB. WAL пишется на каждое изменение. С точки зрения операционной системы — это просто файл из 8 KiB страниц. Логика «B-tree» вся в коде backend’а.

Каждому индексу соответствует свой relfilenode — узнать его можно из pg_class:

SELECT relname, relfilenode, relpages, reltuples
FROM pg_class
WHERE relname IN ('orders', 'orders_pkey');

relpages — число страниц на момент последнего ANALYZE. reltuples — оценочное число строк. Эти данные планировщик использует для costing-расчётов (модуль 7).

Метастраница: page 0

В B-tree-индексе page 0 — это не root, а metapage. Это специальная страница со ссылкой на текущий root. Зачем нужна косвенность? Потому что root может меняться: когда дерево вырастает на уровень (split дошёл до старого root и создан новый), Postgres обновляет указатель в metapage, не трогая остальное.

Если бы root был page 0, при росте дерева пришлось бы переносить page 0 → page N, что ломает все ссылки в индексе. Косвенность через metapage решает проблему.

Когда читатель начинает поиск, он сначала читает metapage (одна страница), узнаёт block number текущего root, идёт туда. Поэтому в Buffers: shared hit=N для Index Scan ты часто видишь N = высота_дерева + 1: metapage + уровни + лист. Postgres кеширует metapage очень агрессивно — _bt_getrootheight() обычно отдаёт ответ без I/O.

Что внутри _bt_search()

Псевдокод обхода дерева от Postgres (упрощённо):

buf = _bt_getroot(rel);
for (;;) {
    page = BufferGetPage(buf);
    // move right while needed (B-link tree!)
    buf = _bt_moveright(rel, buf, key);
    page = BufferGetPage(buf);

    if (P_ISLEAF(page)) {
        // нашли лист — ищем точное совпадение
        return _bt_binsrch(rel, page, key);
    }

    // не лист — спускаемся
    child_offset = _bt_binsrch(rel, page, key);
    child_block = _bt_get_child(page, child_offset);
    buf = _bt_relandgetbuf(rel, buf, child_block);
}

Три вещи стоит запомнить:

1. _bt_moveright на каждом шаге — главный механизм B-link.
2. _bt_binsrch — бинарный поиск внутри страницы (страница ведь упорядочена). На 400 записях это ~9 сравнений, мгновенно.
3. _bt_relandgetbuf — атомарная замена pin’а одного буфера на другой. Это важно для concurrency: между release и get нет окна, в которое можно вклиниться.

Index Scan: с точки зрения executor’а

В исполнении SQL-запроса B-tree участвует в виде узла плана IndexScan, IndexOnlyScan или BitmapIndexScan. Внутри executor’а это выглядит так:

1. Start — открыть индекс, перевести WHERE col = X в ScanKey.
2. Position — вызвать _bt_first(), который проходит дерево от root до нужного листа.
3. Next — вызвать index_getnext_tid(), который отдаёт по одному TID из листа.
4. Heap fetch — для каждого TID идти в heap (если не Index Only Scan).
5. End — закрыть индекс.

_bt_first() — это вход в _bt_search(), который мы видели в псевдокоде. После того как мы нашли нужный лист, executor запоминает «текущее положение» (BTScanPosData), и каждый _bt_next() либо отдаёт следующий слот, либо прыгает по btpo_next на right-sibling.

Range scan (WHERE col >= 10 AND col <= 20) работает поверх того же механизма: мы находим первый лист с col = 10, дальше идём по right-link, отдаём TID за TID, пока не дойдём до col > 20. Это очень дёшево — после позиционирования каждая следующая запись отдаётся без полного обхода дерева.

Полезные функции для диагностики

В стандартной поставке Postgres есть набор функций для интроспекции индексов. Перечислим самые полезные:

• pg_relation_size('idx') — байты.
• pg_indexes_size('table') — суммарный размер всех индексов таблицы.
• pg_stat_user_indexes — статистика использования (число сканирований, число вернутых tuples).
• pgstatindex(idx) из pgstattuple — глубокая статистика B-tree: высота, плотность, фрагментация.
• pg_index — определение индекса: список колонок, выражение, предикат, флаги.

В модуле 6 мы вернёмся к этому набору при разборе maintenance. Здесь важно знать, что инструменты есть — не нужно «писать дамп файла индекса в hex и смотреть глазами», хотя на крайний случай и так можно.

Чек-лист

• В Postgres «B-tree index» — это на самом деле B+tree: данные только в листьях, internal-узлы — только ключи-разделители.
• Структура страницы: PageHeader (24) → ItemId array → free space → tuples → BTPageOpaqueData (16).
• В BTPageOpaqueData лежат btpo_prev, btpo_next, btpo_level, btpo_flags.
• Реализация — B-link tree (Lehman & Yao, 1981): right-link pointers позволяют конкурентные операции без блокировки путей.
• Высота дерева: log_fanout(N). При fan-out 200-300 четыре уровня держат миллиарды строк.
• Файл индекса — это файл из 8 KiB страниц, точно как heap; отличие только в layout.