B-tree изнутри

B-tree - дерево, где все листья на одной глубине, а каждый узел - это страница 8 КБ. Есть три роли страниц:

• meta page (страница 0) - служебная, хранит указатель на корень и уровень дерева;
• внутренние страницы - содержат разделители и ссылки вниз (downlinks) на дочерние страницы;
• листовые страницы - содержат записи индекса: значение ключа и ссылку ctid на строку в таблице.

Поиск всегда начинается с meta page, идёт к корню, спускается по внутренним страницам и заканчивается на листе, где лежит ctid. Сбалансированность означает, что путь от корня до любого листа одинаковой длины - поэтому время поиска предсказуемо.

pageinspect показывает страницы индекса так же, как heap. Сначала meta page:

CREATE EXTENSION IF NOT EXISTS pageinspect;

SELECT root, level FROM bt_metap('tickets_pkey');

root - номер страницы корня, level - высота дерева (0 значит, корень и есть лист). Затем смотрим содержимое страницы:

SELECT itemoffset, ctid, data

FROM bt_page_items('tickets_pkey', 1);

На внутренней странице ctid в записи указывает на дочернюю страницу (downlink); на листовой - на строку в таблице. Спускаясь от корня по downlink к нужному диапазону, ты вручную пройдёшь тот же путь, что и планировщик за тебя.

Ключевое свойство B-tree - огромный коэффициент ветвления (fanout). На одной 8-КБ внутренней странице помещаются сотни разделителей, значит у каждого узла сотни детей. Глубина дерева - это логарифм по основанию fanout:

глубина ≈ log_fanout(число строк)

При fanout около 200-300 трёх уровней хватает на десятки миллионов строк, четырёх - на миллиарды. Поэтому поиск по индексу - это 3-4 чтения страниц, а не «обход дерева». Отсюда и стоимость в модели планировщика: индексный доступ дёшев, пока строк отбирается мало (см. btree-structure).

Когда в листовую страницу вставляют ключ, а места нет, страница делится (split): примерно половина записей уезжает в новую страницу, а наверх, в родителя, поднимается разделитель. Если родитель тоже полон - делится и он, вплоть до корня; split корня повышает дерево на уровень.

Чтобы поиск и вставки работали параллельно без блокировки всего дерева, PostgreSQL использует приём Лемана-Яо: на каждой странице есть high key (верхняя граница её диапазона) и right link - ссылка на правого соседа.

[ ... | high key=50 ] --right--> [ 51 | 52 | ... | high key=99 ]

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

Если в колонке много повторов (например, status с десятком значений на миллионы строк), наивный индекс хранил бы значение заново в каждой записи. Дедупликация это устраняет: одинаковые ключи хранятся один раз, а к ним прикреплён posting list - список всех ctid с этим значением.

без дедупликации:  (done, ctid1)(done, ctid2)(done, ctid3)...

с дедупликацией:   (done → [ctid1, ctid2, ctid3, ...])

Это резко уменьшает размер индекса на колонках с низким числом различных значений и ускоряет их чтение. Дедупликация работает автоматически, её видно по размеру индекса и в bt_page_items как записи с posting list.

Внутренним страницам не нужен полный ключ - им нужен лишь разделитель, достаточный, чтобы решить «влево или вправо». Поэтому при подъёме разделителя в родителя PostgreSQL обрезает его до минимального различающего префикса (suffix truncation).

Например, чтобы отделить aardvark от azimuth, в разделителе хватит a плюс второй буквы - остаток не нужен. Обрезка делает внутренние записи короче, на странице помещается больше разделителей, fanout растёт, дерево становится ещё мельче. Это одна из причин, по которой B-tree в PostgreSQL такой компактный на длинных ключах.

В лист можно положить дополнительные колонки, не делая их частью ключа, - через INCLUDE. Они не участвуют в сортировке и спуске, но доступны для чтения прямо из индекса.

CREATE INDEX ON tickets (flight_id) INCLUDE (passenger);

Теперь SELECT flight_id, passenger WHERE flight_id = 7 может пойти по Index-Only Scan: обе колонки есть в листе, в таблицу идти не надо (при выставленной visibility map, см. главу 27). INCLUDE нужен именно для покрытия запроса, а не для поиска: класть в ключ колонку, по которой не ищешь, было бы лишней нагрузкой на спуск и split. Подробнее про эти механизмы - в btree-internals.

На практике глубину B-tree редко считают точно - она почти всегда 3-4. Из-за большого fanout и suffix truncation добавление нулей к числу строк добавляет к глубине доли уровня. Дерево на тысяче строк и на миллиарде различаются по высоте на один-два уровня, не на порядки.

Практический вывод: переживать о «глубоком дереве» не нужно - B-tree остаётся мелким при любом разумном объёме. Реальные проблемы индекса не в глубине, а в другом: раздувание от обновлений, неподходящий operator class, индекс, который не покрывает запрос. Этим и займёмся в главе про проектирование.