Что значит B в B-Tree

B в B-Tree означает Balanced (сбалансированное). Это ключевая характеристика структуры данных, гарантирующая, что все листовые узлы находятся на одном уровне, а операции поиска, вставки и удаления выполняются за логарифмическое время O(log n).

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

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

class BTreeNode:
    def __init__(self, leaf=False):
        self.keys = []     # Ключи в узле
        self.children = [] # Дочерние узлы
        self.leaf = leaf   # Флаг листового узла

Основные свойства:

• Все листья на одном уровне.
• Минимальная и максимальная степень ветвления (обычно параметр t).
• Корень содержит от 1 до 2t-1 ключей, остальные узлы — от t-1 до 2t-1.