В чем ключевые различия между бинарным деревом и B-деревом?

«В чем ключевые различия между бинарным деревом и B-деревом?» — вопрос из категории Алгоритмы и структуры данных, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Основные различия лежат в структуре узлов, балансировке и области применения.

Критерий Бинарное дерево (Binary Tree) B-дерево (B-Tree)
Потомки на узел Максимум 2. Много (сотни/тысячи). Узел содержит массив ключей и массив указателей на потомков.
Балансировка Не обязательно. Может выродиться в список. Всегда сбалансировано. Все листья находятся на одной глубине.
Оптимизация Для работы в оперативной памяти (RAM). Для работы с медленной памятью (диск, SSD). Минимизирует количество обращений за счет хранения большого количества ключей в узле.
Использование Базис для более сложных структур (AVL, красно-черные деревья) в памяти. Фундаментальная структура для индексов в файловых системах и СУБД (MySQL, PostgreSQL).

Пример структуры узла B-дерева:

class BTreeNode {
    int[] keys;          // Массив ключей в узле
    BTreeNode[] children; // Массив указателей на дочерние узлы
    int numKeys;         // Текущее количество ключей в узле
    boolean isLeaf;      // Флаг, является ли узел листом
}

Почему B-дерево для диска? Загрузка одного блока (узла) с диска, содержащего сотни ключей, эффективнее множественных чтений небольших узлов бинарного дерева.