Что такое B-Tree

B-Tree — это сбалансированное дерево поиска, оптимизированное для работы с дисками и базами данных. Оно минимизирует количество обращений к диску за счёт хранения множества ключей в узлах и поддержания большого коэффициента ветвления.

Особенности B-Tree:

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

Пример использования в Python (упрощённый):

class BTreeNode:
    def __init__(self, leaf=False):
        self.keys = []
        self.children = []
        self.leaf = leaf

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(True)
        self.t = t  # минимальная степень

Применение:
B-Tree часто используется в СУБД (например, PostgreSQL, MySQL) для индексации, так как обеспечивает быстрый поиск даже при больших объёмах данных.