🌳 Индекс под капотом
Когда добавляешь к таблице индекс по id, физически на диске появляется файл этого индекса, рядом с файлом кучи, которая содержит данные в страницах (блоках по 8KB). В файле индекса тоже есть страницы, в которых и хранится то самое B-дерево.
В самом начале файла индекса (в блоке 0) находится служебная метастраница, просто «визитка», которая хранит указатель на корень дерева и пару параметров. Она не является частью дерева: у неё нет родителя/детей, она не участвует в навигации по уровням.

📏 Из чего состоит дерево (Дикпик 1)
Используем bt_metap - функцию из расширения pageinspect. Она читает метастраницу индекса и возвращает её содержимое: в каком блоке сейчас корень, на каком он уровне дерева, и пару служебных полей. У нас корень в блоке 3 внутри файла индекса users_pkey (по смещению 3 × 8 KB).
С пониманием level , то есть уровнем дерева, легко споткнуться: в PostgreSQL листья - это уровень 0, и нумерация растёт вверх, к корню. Поэтому level=1 означает «корень на один уровень выше листьев» → всего 2 уровня (листья на 0, корень на 1). Будь строк миллионы — стало бы level=2: корень → ветви → листья.
Следующий запрос показывает содержимое дерева: 1 страница корня (type: r) и 17 страниц листьев (type: l).

🧭 Что внутри корня (Дикпик 2)
Корень - это не данные, а «оглавление», которое содержит 17 записей вида разделитель (sep_id) → downlink (ссылка на дочерний лист (он же блок, он же страница)): «меньше 367 — блок 1; 367..732 — блок 2; …; от 5857 — блок 18». Числа 367, 733… - это границы маршрутизации.
Каждая запись в корне говорит: «вот сюда (downlink) идут ключи, начиная с такого-то значения». Самый верхний downlink должен ловить всё, что меньше первой реальной границы — а нижней границы у него нет.
Поэтому у первой записи корня нет разделителя (ключ усечён до нуля атрибутов), а её downlink ведёт в первый лист: он совпадает с любым ключом, каким бы маленьким тот ни был.
Разделители (sep_id) - это стыки между листьями, и их значения берутся из того, сколько ключей влезло в предыдущий лист. В один 8-килобайтный лист помещается 366 записей по int: лист 1 (блок 1) держит id 1…366. Когда он заполнился, 367-й ключ — первый, который туда уже не влез, — открывает следующий лист (блок 2). Вот это пограничное значение и поднимается в корень как разделитель: «ключи ≥ 367 → во второй лист, меньше → в первый».
То есть 367 = наименьший id второго листа.

🍃 Что внутри листа (Дикпик 3)
А тут живут настоящие записи: пара ключ id_key → heap_ctid, то есть указатель на строку в той самой куче. И смотри: id_key=1 → (0,1), id_key=121 → (0,121) — это ровно те же ctid, что мы видели в посте про страницы! То есть индекс хранит значения id по порядку и держит указатели на строки. Запись с itemoffset = 1 - это high key, то есть верхняя граница этой страницы.

🔗 Итоговая картина (Дикпик 4)
Как видно, индекс - это отдельный файл на диске, в котором метастраница и B-дерево - (корень + листья), итого 19 страниц. Куча users — другой файл, со своими 50 страницами. Связь односторонняя: листья держат ctid в кучу, но сама куча про индекс ничего не знает.

🏗 Любопытная деталь
Почему корень оказался в блоке 3? ADD PRIMARY KEY собирает дерево снизу вверх: блок 0 - мета, блок 1 - первый лист (пока без корня); он переполняется → создаётся второй лист (блок 2), и тут же рождается их общий родитель (корень) → ему достаётся блок 3.

🔎 Как в итоге ищется WHERE id = 5999
1) Метастраница индекса → корень (блок 3);
2) 5999 ≥ 5857 → последний лист (блок 18);
3) в листе берём heap_ctid;
4) читаем одну heap-страницу.

⚡️~3 чтения вместо 50⚡️

🅰️ Что унести с собой
- PK-индекс - это отсортированный справочник «id → ctid»
- Индекс и таблица - это разные файлы
- ctid на кучу живёт в листьях индекса
- Третий уровень (ветви между корнем и листьями) появляется лишь на сотнях тысяч строк - на 1 млн строк дерево уже трёхуровневое (корень → 10 ветвей → 2733 листа).
- Точечный поиск по PK - это 2–3 обращения к страницам, поэтому он «бесплатный» по ощущениям.
Команды, чтобы повторить и потыкать самому — в 👉гисте 👉

#бд #postgresql #инженерныештучки

🌳 B+-tree: что значит буква B и что значит «+»
В прошлых постах мы с тобой разобрали страницы (👉 раз), увидели, как индекс спасает от Seq Scan (👉 два), и пощупали B-дерево изнутри — корень, разделители, листья (👉 три). Дальше разберёмся, что значит «B», чем B+-дерево отличается от B-дерева, как оно держит себя ровным, и какая сложность поиска по нему🔎

🔤 Что значит 🅱️
Точного ответа нет💁 Структуру B-дерева придумали Рудольф Байер и Эдвард МакКрейт в Boeing Research Labs в начале 70-х, но что означает B — авторы так и не объяснили. Варианты: Balanced, Bayer (фамилия), Boeing (фирма), а ещё broad, bushy, и даже between. По воспоминаниям МакКрейта, Байер шутил: «чем больше думаешь, что значит B в B-tree, тем лучше понимаешь B-tree» (по крайней мере, такая история в вики). Так что «B = balanced» — логичное предположение, но оно не подтверждено разработчиками¯\_(ツ)_/¯

➕ А вот «+» — уже не загадка
Это и есть главное отличие от классического B-дерева, в котором данные могут находиться как во внутренних узлах, так и в листовых. B+-tree, на котором основаны индексы в популярных СУБД (PostgreSQL, MySQL, MongoDB, SQL Server), устроено немного иначе:

🟢 Данные (в случае PostgreSQL, ctid — указатели на строки) живут только в листьях. Внутренние узлы хранят одни ключи-разделители: чистое «оглавление», маршрут до листа. Те самые «≥ 367 → блок 2» из #430.
🟢 Листья сцеплены в связный список. Поэтому поиск по диапазонам (>, <, BETWEEN) работает достаточно быстро: спустился до листьев и побежал по ним подряд, не возвращаясь наверх (см. дикпик 3). Тот же список бесплатно даёт и упорядоченный обход: ORDER BY может выполняться через последовательный обход индекса без дополнительной сортировки (но оптимизатор не всегда выбирает индексный проход).
В классическом B-дереве упорядоченный обход тоже возможен, но для перехода к следующему ключу приходится регулярно возвращаться к внутренним узлам дерева. В B+-дереве листья уже связаны между собой, поэтому диапазонные запросы и последовательный обход выполняются проще и эффективнее📈

И ещё 🅱️онус: благодаря тому, что внутренние узлы хранят только ключи-разделители, они компактнее → в страницу 8 KB влезает больше разделителей → ветвление выше → уровней дерева меньше → меньше чтений с диска.
Насколько степень ветвления выше? В 8 KB-страницу влезают сотни мелких элементов. В листе элемент — это «ключ + ctid» (для int их 366, #430). А во внутреннем узле элемент — «ключ-разделитель + ссылка на дочернюю страницу», и таких ссылок тоже сотни, то есть сотни веток к дочерним узлам (см. дикпик 2).
Для сравнения, двоичные деревья (AVL, красно-чёрные) имеют всего по две ветви, из-за чего они высокие и заточены скорее под оперативную память, а не под диск, поэтому как основу для дисковых индексов их обычно не используют.

🧰 Как это использовать
🔹 «B» — историческая загадка, а «+» — это «данные только в листьях + листья связаны в список».
🔹 Индекс по столбцу ускоряет не только поиск по равенству, но и диапазоны (>, <, BETWEEN): БД спускается к началу диапазона и идёт по связанным листьям. Часто фильтруешь по диапазону — индекс окупается.
🔹 ORDER BY по индексируемому столбцу может пройти без отдельной сортировки, если порядок в запросе совпадает с порядком индекса. Повод согласовать ORDER BY с порядком столбцов в индексе.
🔹 Один B+-tree-индекс закрывает сразу три сценария: точечный поиск, диапазон и сортировку — поэтому индекс по «горячему» столбцу часто полезнее, чем кажется.

#бд #postgresql #инженерныештучки