Зачем нужны B-деревья и чем они отличаются от обычного дерева поиска?

Отличный вопрос — ответ кроется не в алгоритмах, а в железе.

У бинарного дерева в каждом узле максимум 2 ребёнка. У B-дерева узел может иметь много детей — десятки, сотни и больше. Из-за этого B-дерево очень «широкое» и низкое: даже для миллионов записей высота — всего несколько уровней.

Зачем это надо? Вспомни, как работает БД. Данные лежат на диске (или SSD), а чтение с диска идёт блоками (страницами по 4/8/16 КБ) и стоит в тысячи раз дороже, чем операция в RAM. Главная метрика — число обращений к диску, а оно равно высоте дерева.

Сравни на миллионе ключей:

• BST: высота ≈ log₂(1 000 000) ≈ 20 уровней → до 20 чтений с диска.
• B-дерево с 100 ключами в узле: высота ≈ log₁₀₀(1 000 000) ≈ 3 уровня → 3 чтения.

Разница в разы по числу дорогих дисковых операций. В этом вся суть: один узел B-дерева = одна страница диска, и мы читаем сразу много ключей за одно обращение, а не по одному.

Ключевые свойства B-дерева:

• узел содержит много ключей и много указателей на детей;
• остаётся отсортированным и сбалансированным автоматически при вставках/удалениях;
• высота растёт крайне медленно с ростом данных.

B+tree — популярная разновидность (её и используют MySQL/InnoDB, PostgreSQL):

• все реальные данные хранятся только в листьях, во внутренних узлах — лишь ключи-разделители;
• листья связаны в список → диапазонные запросы (WHERE age BETWEEN 20 AND 30) и ORDER BY делаются простым проходом по листьям, без прыжков по дереву.

Итог: BST хорош в оперативной памяти, но для дисковых индексов важна минимизация чтений блоков — поэтому СУБД выбирают B-tree/B+tree.