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

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

🗄 Оперативное 1: shared_buffers — личный кэш Postgres

В обзорном посте про оперативку постгресса мы насчитали трёх «едоков» памяти. Начнём с первого: shared_buffers. Разберёмся, что это такое и почему он всегда выглядит занятым.

😂 Что это вообще
Как многие знают, Postgres не бегает на диск в каждом запросе. У него есть свой кэш — кусок оперативки, куда он складывает страницы (напомню, что это кусочки по 8 Kb), которые недавно понадобились, чтобы в следующий раз взять их из памяти. Вот этот кэш и есть shared_buffers.

Слово shared («общий») тут ключевое: буферы общие для всех соединений. Один запрос читает страницу с диска и кладет в shared_buffers, а следующий возьмёт её уже из памяти и диск не тронет. (Напомню, что даже на самых мощных SSD разница скорость чтения 10-20 микросекунд, тогда как из оперативки это 50-60 НАНОсекунд, то есть капец как дешево)

📏 Сколько его
Размер задаёт параметр shared_buffers, и фиксируется он при старте сервера. По умолчанию в Postgres это всего 128 MB — наследство времён, когда памяти было мало. На боевом сервере его обычно поднимают примерно до четверти всей оперативки. Текущее значение покажет команда SHOW shared_buffers;

⚙️ Почему он всегда «занят»
Эти 128 MB (или сколько ты выставил) Postgres резервирует под кэш сразу при запуске и держит за собой всё время работы. Поэтому в мониторинге shared_buffers всегда показывает себя занятой памятью. Это не утечка и не повод хвататься за сердце 😰: память заранее отведена под кэш и работает на тебя.

🔬 Что внутри
Что именно сейчас лежит в shared_buffers, показывает расширение pg_buffercache (его надо один раз подключить командой CREATE EXTENSION pg_buffercache).

На прогретой таблице users из миллиона строк (прогретой — значит по ней уже погоняли запросы, и её страницы успели осесть в кэше) у меня вышло так:

🟢 сама таблица заняла 47 MB
🟢 индекс по email — 39 MB
🟢 индекс первичного ключа — 21 MB.

Два индекса вместе съели больше кэша, чем данные! Это частый сюрприз: спрашиваешь «куда ушла память под базу», а ответ нередко оказывается простым — в индексы.

🅰️ Что унести с собой

🟢 shared_buffers — это собственный кэш Postgres в оперативке, общий для всех соединений.
🟢 Его размер фиксируется при старте: по умолчанию 128 MB, на проде обычно около четверти RAM.
🟢 Он всегда выглядит занятым, и это нормально: память заранее отведена под кэш.
🟢 Индексы живут в том же кэше, что и данные, и порой занимают даже больше места.

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