Чем B-дерево отличается от обычного бинарного дерева и почему оно сбалансированное?

B-дерево — это самобалансирующееся дерево поиска, оптимизированное для хранения данных на диске. В обычном бинарном дереве поиска каждый узел содержит один ключ и максимум двух потомков, поэтому при большом объёме данных высота дерева растёт логарифмически, но с большим основанием логарифма по сравнению с B-деревом. B-дерево же позволяет узлу хранить множество ключей (от t-1 до 2t-1) и иметь от t до 2t потомков, где t — минимальная степень дерева.

Ключевые отличия от бинарного дерева

• В бинарном дереве узел имеет не более двух детей и один ключ; в B-дереве — много ключей и много детей.
• Бинарное дерево может быть несбалансированным (вырождаться в список), B-дерево всегда сбалансировано.
• B-дерево хранит данные блоками, что соответствует страницам диска, снижая число операций ввода-вывода.
• Поиск, вставка и удаление в B-дереве выполняются за O(log n), но с меньшим числом обращений к диску.

Почему B-дерево сбалансировано

Балансировка обеспечивается правилами вставки и удаления. При вставке нового ключа узел может переполниться (стать больше 2t-1 ключей). Тогда он расщепляется на два узла, а средний ключ поднимается в родителя. Если и родитель переполнен, процесс повторяется вверх. При удалении, если узел становится слишком пустым (меньше t-1 ключей), происходит заимствование ключа у соседа или слияние узлов. Эти операции гарантируют, что все листья находятся на одной глубине, а высота дерева остаётся O(log n).

Пример на псевдокоде

// Вставка ключа в B-дерево (упрощённо)
function insert(node, key):
  if node is leaf:
    add key to node in sorted order
    if node.keys.length > 2t-1:
      split(node)
  else:
    child = find_child(node, key)
    insert(child, key)
    if child.keys.length > 2t-1:
      split(child)

function split(node):
  mid = node.keys.length / 2
  left = new Node(node.keys[0..mid-1])
  right = new Node(node.keys[mid+1..])
  parent = node.parent
  parent.add_key(node.keys[mid])
  parent.replace_child(node, left, right)
  if parent.keys.length > 2t-1:
    split(parent)

B-деревья широко применяются в базах данных (например, индексы в PostgreSQL, MySQL) и файловых системах (NTFS, ext4), потому что они минимизируют количество чтений с диска. В отличие от бинарных деревьев, где каждый узел требует отдельного доступа, B-дерево читает целый блок данных за одну операцию.

Итог: B-дерево стоит применять там, где данные хранятся на диске и важна производительность ввода-вывода, например в СУБД и файловых системах. Для оперативной памяти часто достаточно бинарных деревьев или хеш-таблиц.