Что такое B-Tree

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

Особенности:

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

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

type BTreeNode struct {
    keys     []int
    children []*BTreeNode
    leaf     bool
}

func (n *BTreeNode) search(k int) bool {
    i := 0
    for i < len(n.keys) && k > n.keys[i] {
        i++
    }
    if i < len(n.keys) && k == n.keys[i] {
        return true
    }
    if n.leaf {
        return false
    }
    return n.children[i].search(k)
}