B-tree и B+tree держат мало уровней на диске и хорошо отвечают на равенство и диапазон. Именно поэтому обычный индекс PostgreSQL — это дерево страниц, а не бинарное дерево указателей в RAM.
Алгоритмы и структуры данных cs собеседование
Бинарное дерево поиска в памяти выглядит просто. Высота log₂ n. Каждый шаг — сравнение и переход по указателю.
На диске тот же рисунок плохой. Страница читается блоками. В Postgres типично 8 КБ. Если в узле один ключ и два ребёнка, высота большая. Каждый уровень — отдельное случайное чтение. На миллионах строк это много прыжков.
B-tree поднимает арность: в одной странице много ключей и указателей на детей. Высота падает до 3–4 даже на больших таблицах. Корень часто лежит в памяти. Внутренние узлы тоже кэшируются. До листьев доходят одним-двумя I/O.
Пример. Представьте библиотеку. Бинарное дерево на диске — стеллаж, где на полке одна книга и стрелки «влево / вправо». Чтобы найти книгу, идёте по многим полкам. B-tree — широкая полка: на одной странице сразу много названий. Спустились три раза — вы на месте.
B+tree идёт дальше. Полезные данные живут в листьях: указатели на строки кучи или сами ключи индекса. Внутренние узлы — только разделители. Листья связаны в список. Range scan идёт последовательно по страницам, не скачками вверх-вниз. Примерно так устроен btree-индекс в PostgreSQL.
Почему не бинарное дерево
Случайное чтение страницы стоит порядки дороже сравнения в CPU. Высокая арность уменьшает число таких чтений. Балансировка B-tree (split и merge страниц) держит узлы заполненными и высоту короткой после вставок и удалений. Это плата за жизнь на блочном устройстве, а не в массиве указателей.
// [ 50 | 120 ] корень (разделители)
// / | \
// [10|20|40] [50|80] [120|200] листья + next →
//
-- равенство и диапазон по префиксу индекса
SELECT * FROM orders WHERE user_id = 42;
SELECT * FROM orders
WHERE user_id = 42 AND created_at >= '2024-01-01';
-- функция на колонке: обычный btree по email не подходит
SELECT * FROM users WHERE lower(email) = 'a@b.c';
-- CREATE INDEX ON users (lower(email));B+tree: данные в листьях, листья связаны — range scan последовательный. Бинарное дерево на диске читало бы страницу на каждый узел.
Следствие для SQL
Равенство и диапазон по левому префиксу ключа индекса — типичное попадание в Index Scan. WHERE lower(email) = $1 при btree по email часто уходит в Seq Scan: дерево хранит исходные значения, а не результат функции. Нужен индекс по выражению. LIKE '%foo' тоже не префикс: книга не открывается на всех «…foo».
Пример. Телефонная книга отсортирована по фамилии. Запрос «Ивановы с 2024 года» идёт по префиксу. Запрос «все, у кого имя с маленькой буквы» книга не ускорит: она хранит имена как есть, не lower(name).
Случайный UUID как первичный ключ размазывает вставки по листьям: page splits, фрагментация, хуже cache. Монотонный идентификатор пишет в «правый» край дерева — предсказуемее, но даёт горячую страницу. Лишний индекс ускоряет SELECT и замедляет каждую запись: дерево тоже нужно обновлять.
B+tree и range
Потому и говорят, что строки индекса «обычно в листьях»: range scan и Index Only Scan опираются на последовательные листья, а не на разрозненные узлы бинарного дерева. Внутренние страницы только направляют поиск. Это удобно и для ORDER BY по префиксу ключа: порядок уже есть в дереве.
Типичная ошибка
Считать, что «есть индекс — будет Index Scan». Планировщик смотрит селективность и стоимость I/O: на малой таблице или при предикате «80% строк» Seq Scan дешевле. Вторая ошибка — ждать, что btree по колонке сработает, если в WHERE колонка обёрнута в функцию.
На собеседовании
Нарисуйте корень и связанные листья. Высота дерева — это число случайных чтений страниц. Дальше EXPLAIN: Index Scan против Seq Scan, префикс ключа против функции в WHERE.