👈 В прошлый раз мы выяснили, что обычно данные в СУБД лежат в страницах фиксированного размера. А как по этим страницам что-то быстро найти?

🔍 Если искать в лоб
Представь, что ты хочешь найти в толстой книге по базам данных упоминание слова «дерево». Если в конце нет предметного указателя — придётся листать страницу за страницей и глазами выискивать нужное слово.
СУБД без индекса делает ровно то же самое: она прочитает все страницы таблицы подряд, проверит на каждой, есть ли подходящая строка, и оставит то, что нашла. Этот режим работы называется Sequential Scan, или просто Seq Scan — последовательное чтение.
Увидеть, что СУБД делает именно так, можно через EXPLAIN — команду, которая покажет, как планируется выполнить запрос. Видишь в плане Seq Scan — значит СУБД проходит таблицу целиком.
На таблице в 10 млн строк это будет довольно долго, потому что на каждый запрос будут выполняться сотни тысяч чтений страниц с диска ради одной нужной строки 💽

📖 Предметный указатель
В книге это решается просто: там есть предметный указатель — отсортированный по алфавиту список слов с номерами страниц. Открываешь, ищешь слово, прыгаешь на нужную страницу.
В СУБД роль такого указателя играет индекс. Это отдельная структура на диске, в которой ключи (например, значения id) лежат отсортированно, а рядом с каждым — указатель на конкретную страницу таблицы 🧿
Чаще всего первый индекс появляется в таблице автоматически: когда ты добавляешь, например, в свою таблицу users PRIMARY KEY на колонку id, Postgres под капотом создаёт уникальный индекс по этой колонке — users_pkey; в psql его видно через метакоманду \d users как btree (id).

🌳 Что такое btree
В большинстве СУБД (PostgreSQL, MySQL/InnoDB, SQL Server, MongoDB через WiredTiger) индекс по умолчанию — не просто отсортированный список, а B-дерево (точнее, его вариант B+tree).
Почему не список? Главное — число чтений с диска. Бинарный поиск по отсортированному списку из миллиона страниц — это около 20 чтений. И если ключ не монотонный (email, uuid, имя автора), любая вставка в середину означает переписать целый хвост.
B-дерево — это обычное дерево из корня сверху, внутренних узлов в середине и листьев снизу. Оно устроено так:

🟢 В каждом узле много ключей — не один-два, а сотни.
🟢 Все листья на одной глубине. Любой путь от корня до листа одинаковой длины.
🟢 За счёт большого ветвления глубина дерева смешная. Для индекса по сотне миллионов записей это 3–4 уровня. Найти строку = 3–4 чтения. Не миллионы, не тысячи. Три-четыре 🎉
🟢 Листья связаны в список. Поэтому Range-запросы (>, <, BETWEEN) тоже летают: спустился до начала диапазона и пробежал листья подряд.
Аналогия — толстая энциклопедия: тома → главы → разделы. Три шага, и ты на месте 👍

📦 Как это лежит в Postgres (см. дикпик 3)
Структура B-tree один в один ложится на структуру страниц из прошлого поста:
⚪️ Один узел дерева = одна страница 8 KB.
⚪️ Внутренние узлы хранят пары (ключ, ссылка на дочернюю страницу). В одну страницу таких пар влезают сотни.
⚪️ Листья хранят пары (ключ, ctid). Помнишь ctid из прошлого поста? Это указатель «страница такая-то, позиция такая-то» — он ведёт прямо на нужную строку в куче.
⚪️ Индекс лежит отдельным файлом со своим pg_relation_filepath — это не часть таблицы, это самостоятельная сущность.

🔬 Пощупаем (см. дикпики 1 и 2)
Берём таблицу users из прошлого поста (6000 строк, без PRIMARY KEY) и ищем по id. Seq Scan ... Rows Removed by Filter: 5999: прочитали всё, отбросили 5999, оставили одну.

Добавляем первичный ключ. Тот же запрос — план сменился на Index Scan using users_pkey. Сначала Postgres прошёл по B-дереву от корня до листа, там нашёл ctid, по нему сходил в нужную страницу таблицы и достал строку.

🅰️ Что с этим знанием делать
Индекс — это отдельные страницы на диске. Каждый INSERT/UPDATE/DELETE правит и таблицу, и все её индексы. Поэтому вешать их «на всякий случай» на каждое поле — плохая идея: платишь местом на диске, замедлением записи, обслуживанием дерева. При хорошо выбранном индексе взамен этих накладных расходов получаешь быстрый поиск⚡️

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

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