Ответ
Основные различия лежат в структуре узлов, балансировке и области применения.
| Критерий | Бинарное дерево (Binary Tree) | B-дерево (B-Tree) |
|---|---|---|
| Потомки на узел | Максимум 2. | Много (сотни/тысячи). Узел содержит массив ключей и массив указателей на потомков. |
| Балансировка | Не обязательно. Может выродиться в список. | Всегда сбалансировано. Все листья находятся на одной глубине. |
| Оптимизация | Для работы в оперативной памяти (RAM). | Для работы с медленной памятью (диск, SSD). Минимизирует количество обращений за счет хранения большого количества ключей в узле. |
| Использование | Базис для более сложных структур (AVL, красно-черные деревья) в памяти. | Фундаментальная структура для индексов в файловых системах и СУБД (MySQL, PostgreSQL). |
Пример структуры узла B-дерева:
class BTreeNode {
int[] keys; // Массив ключей в узле
BTreeNode[] children; // Массив указателей на дочерние узлы
int numKeys; // Текущее количество ключей в узле
boolean isLeaf; // Флаг, является ли узел листом
}
Почему B-дерево для диска? Загрузка одного блока (узла) с диска, содержащего сотни ключей, эффективнее множественных чтений небольших узлов бинарного дерева.