Что означает буква «B» в термине B-дерево?

Единого общепринятого значения буквы "B" нет. Наиболее распространенные трактовки:

1. Balanced (Сбалансированное): Отражает ключевое свойство структуры — дерево остается сбалансированным при вставках и удалениях, что гарантирует логарифмическую сложность операций.
2. Bayer (Байер): По фамилии Рудольфа Байера (Rudolf Bayer), одного из его создателей.
3. Boeing (Боинг): По названию компании Boeing Labs, где структура была впервые разработана и применена.

Что такое B-дерево? Это сбалансированное дерево поиска, оптимизированное для систем, работающих с вторичной памятью (дисками). Оно минимизирует количество обращений к диску за счет того, что каждый узел может хранить много ключей и иметь много потомков.

Основные свойства B-дерева порядка m:

• Корень содержит от 1 до m-1 ключей (если он не лист).
• Каждый внутренний узел (не корень и не лист) содержит от ⌈m/2⌉ - 1 до m-1 ключей.
• Каждый узел с k ключами имеет k+1 потомков.
• Все листовые узлы находятся на одной и той же глубине.
• Ключи в узле отсортированы.

Пример структуры узла B-дерева порядка 3 (2-3 дерево):

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

B-деревья широко используются в базах данных (индексы) и файловых системах.