Что такое B-дерево (B-Tree) и где оно применяется?

Ответ

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

Расшифровка названия

Вопреки распространенному мнению, что "B" означает "Balanced" (сбалансированное), официальной расшифровки нет. Создатели (Рудольф Байер и Эдвард МакКрейт) никогда её не давали. Среди неофициальных версий: Balanced, Boeing (компания, где они работали) или Bayer (фамилия одного из авторов).

Ключевые свойства

Сбалансированность: Все листовые узлы (листья) находятся на одной и той же глубине.
Много ключей в узле: В отличие от бинарного дерева, узел B-дерева может содержать множество ключей и иметь множество дочерних узлов. Это его главная особенность.
Эффективность: Операции поиска, вставки и удаления выполняются за логарифмическое время O(log n).
Оптимизация под дисковые операции: За счет большого количества ключей в узле высота дерева остается очень маленькой даже для огромного объема данных. Так как каждый узел может быть загружен с диска за одну операцию чтения, это минимизирует количество медленных дисковых I/O.

// Упрощенная концептуальная структура узла B-дерева в Go
type BTreeNode struct {
    isLeaf   bool      // Является ли узел листом
    keys     []int     // Ключи, хранящиеся в узле
    children []*BTreeNode // Указатели на дочерние узлы
}

Основные области применения

B-деревья и их вариации (B+ деревья, B* деревья) являются стандартом де-факто для:

Систем управления базами данных (СУБД): Для создания индексов таблиц. Например, PostgreSQL и MySQL (InnoDB) используют B+ деревья для индексации.
Файловых систем: Для организации метаданных файлов и каталогов (например, в HFS+, NTFS, ext4).