🌳 Индекс под капотом
Когда добавляешь к таблице индекс по 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 #инженерныештучки

Мы с тобой уже довольно сильно углубились в тему деревьев, главное - не забрести в дремучий лес (ба-дум-тсс🥁). Не переживай, скоро мы выберемся отсюда, а пока что:

🌳 Как B-дерево держит себя ровным и какая у него максимальная высота

⚖️ Balanced — это про что
Если помнишь, одно из толкований буквы B — Balanced, то есть их ещё называют сбалансированными деревьями. Эта сбалансированность заключается в том, что все листья лежат на одной глубине, любой путь от корня до листа одинаковой длины. Нет веток разной глубины, в которые можно надолго провалиться, — поэтому любой спуск к данным стоит одинаково 🟰

🤩 А как у других?
В двоичных деревьях (AVL, красно-чёрных) после вставки одна ветка может стать длиннее другой, и дерево «чинит» себя поворотом: берёт перекосившую тройку узлов и локально переставляет их — бывший потомок становится родителем, поддеревья перевешиваются, высоты выравниваются. Делает это сама структура, на каждой вставке и удалении. Поворот — это их способ оставаться ровными 🔁

🪨 Как поддерживается баланс (видео-дикпик 📱)
B-дерево балансируется без поворотов — делением переполненной страницы (split):
1️⃣ лист наполняется ключами, пока не переполнится;
2️⃣ переполнился — делится надвое (split), а пограничный ключ копируется наверх, к родителю, и становится новым разделителем (по нему потом и выбирают, в какую из половин спускаться);
3️⃣ если переполнился сам корень — он тоже делится на два узла, которые становятся внутренними, потому что сверху над ними встаёт НОВЫЙ корень (появляется новый уровень).
Таким образом дерево не удлиняет отдельные ветки, а растёт вверх равномерно. Возникает резонный вопрос:

📏 Сколько вообще может быть уровней?
Жёсткого лимита в Postgres нет, но из-за большого ветвления высота по int растёт еле-еле:
🔹 2 уровня — до ~100 тыс. строк
🔹 3 — до ~30 млн
🔹 4 — до ~8,5 млрд
🔹 5 — до ~2,4 трлн

А выше упирается в потолок физического хранения таблицы. У каждой строки есть физический адрес: номер блока + слот внутри блока. Номер блока 32-битный, значит блоков максимум ~4,3 млрд (2^32), а в один блок 8 KB влезает примерно 291 строка. Перемножаем 4,3 млрд страниц × 291 запись ≈ 1,2 трлн строк, и больше в таблицу не поместится: для новой строки просто не останется свободного адреса 📍

Пятиуровневое дерево может вместить до ~2,4 трлн ключей, а строк в таблице будет не больше ~1,2 трлн. Таблица кончится раньше, чем дерево заполнит пятый уровень и запросит шестой. Поэтому индекс по int на практике — это 2–5 уровней, и выше пяти не вырастет: столько строк в одну таблицу физически не положить 🛑

🔬 Посмотрим на живом примере (дикпик 1)
Растим таблицу с первичным ключом и смотрим высоту через bt_metap.

Рост в 10 000 раз добавил ровно ОДИН уровень. А точечный поиск всё ещё требует единицы чтений: «корень → ветвь → лист → строка». И столько будет как на тысяче строк, так и на десяти миллионах ✨

🎢 Что это даёт по скорости
Сложность поиска по такому дереву - O(log n), потому что поиск = спуск от корня до листа, то есть ровно столько шагов, сколько в дереве уровней (высота). А высота для дерева с ветвлением f и N записями — это примерно log по основанию f от N.
И в этом весь смысл баланса: если бы split не поддерживал все листья на одной глубине, дерево могло бы выродиться в почти линейную цепочку — и поиск стал бы O(n), то есть потребовались бы миллионы чтений, от которых индекс и спасает 🛟

🅰️ Что унести с собой
🔹 Поиск по индексу — O(log n), потому что большое ветвление держит дерево низким, а split гарантирует одинаковую глубину листьев.
🔹 Это гарантия худшего случая, а не «в среднем»: split держит все листья на одной глубине, поэтому длинных веток просто не бывает.
🔹 Точечный поиск по индексу почти «бесплатный» — что на тысяче строк, что на сотне миллионов это несколько уровней дерева.

Команды, чтобы самому замерить высоту на разных размерах, — в 👉 гисте 👈

🧑‍💻dp 🥁
#бд #postgresql #инженерныештучки #heavywednesday