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

🌳 Как 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