B-дерево: принципы работы

B-дерево — это сбалансированное дерево поиска, оптимизированное для работы с блочно-ориентированными устройствами хранения (диски, SSD). Основная идея — минимизировать количество операций ввода-вывода за счёт высокой степени ветвления.

Ключевые характеристики

• Порядок дерева (t): минимальная степень. Каждый узел (кроме корня) содержит от t-1 до 2t-1 ключей.
• Высота: для B-дерева порядка t с n ключами высота ≤ log_t((n+1)/2). На практике высота редко превышает 3-4 уровня.
• Все листья на одном уровне: гарантирует сбалансированность.

Структура узла

[Ключ1 | Ключ2 | ... | Ключk]
  ↓       ↓             ↓
[P0]    [P1]    ...    [Pk]

Где:

• k — количество ключей в узле (t-1 ≤ k ≤ 2t-1)
• Pi — указатели на дочерние узлы
• Ключи упорядочены: Ключ1 < Ключ2 < ... < Ключk
• Для любого ключа Ki: все ключи в поддереве Pi-1 < Ki < все ключи в поддереве Pi

Основные операции

Поиск

func (tree *BTree) Search(key int) (value interface{}, found bool) {
    node := tree.root
    for node != nil {
        // Бинарный поиск в узле
        i := sort.Search(len(node.keys), func(j int) bool {
            return node.keys[j] >= key
        })
        
        if i < len(node.keys) && node.keys[i] == key {
            return node.values[i], true
        }
        
        if node.isLeaf {
            return nil, false
        }
        
        node = node.children[i]
    }
    return nil, false
}

Вставка

1. Спуск к листу: находим лист, куда нужно вставить ключ.
2. Разделение при переполнении: если узел содержит 2t-1 ключей:
   • Создаём новый узел
   • Медианный ключ поднимается в родителя
   • Ключи распределяются между старым и новым узлом
3. Гарантия места: при спуске разделяем полные узлы заранее.

Удаление

Наиболее сложная операция. Основные случаи:

• Из листа: просто удаляем, если после удаления ключей ≥ t-1
• Из внутреннего узла: заменяем на predecessor/successor из листа
• При дефиците: заимствуем у соседа или сливаем узлы

Преимущества перед другими структурами

Варианты B-дерева

• B+ дерево: данные только в листьях, внутренние узлы — только ключи. Листья связаны в список для range-запросов. Используется в большинстве СУБД (PostgreSQL, MySQL InnoDB).
• B дерево*: узлы заполнены на 2/3, разделение происходит при полном заполнении двух соседних узлов.
• Префиксное B-дерево: оптимизация для строковых ключей.

Практическое применение

1. Индексы в СУБД: InnoDB использует B+ деревья для clustered и secondary индексов.
2. Файловые системы: NTFS, HFS+, Ext4 используют B-деревья для каталогов.
3. LSM-деревья: альтернатива для write-heavy нагрузок (LevelDB, RocksDB).

Edge cases и подводные камни

• Корень-исключение: корень может содержать от 1 до 2t-1 ключей
• Конкурентный доступ: требуется блокировка на уровне узлов (latch crabbing)
• Кэширование: горячие узлы (корень, верхние уровни) должны оставаться в памяти
• Фрагментация: при частых вставках/удалениях может снижаться заполненность узлов

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