Ответ
B-дерево (B-tree, где 'B' чаще всего означает 'Balanced' — сбалансированное) — это древовидная структура данных, которая хранит данные в отсортированном виде и позволяет выполнять поиск, последовательный доступ, вставку и удаление за логарифмическое время O(log n). Она является основной структурой для индексов в большинстве реляционных баз данных (например, PostgreSQL, MySQL).
Ключевые компоненты:
- Узлы (Nodes): В отличие от бинарного дерева, узел B-дерева может содержать множество ключей и ссылок на дочерние узлы. Ключи в узле отсортированы.
- Листовые узлы (Leaf Nodes): Находятся на самом нижнем уровне дерева. Они содержат индексируемые значения и указатели на фактические строки в таблице. Все листовые узлы находятся на одной глубине.
- Внутренние узлы (Internal Nodes): Узлы между корнем и листьями. Они хранят ключи-разделители и указывают на дочерние узлы.
- Корень (Root): Самый верхний узел, точка входа в дерево.
Как это работает (упрощенно):
- Поиск: Начинается с корневого узла. Сравнивая искомое значение с ключами в узле, алгоритм определяет, в какой из дочерних узлов нужно спуститься. Процесс повторяется, пока не будет достигнут листовой узел с нужными данными.
- Вставка/Удаление: После нахождения нужного места для вставки/удаления в листовом узле, операция выполняется. Если узел переполняется (при вставке) или становится слишком пустым (при удалении), он балансируется: узел разделяется на два или сливается с соседним. Эти изменения могут распространяться вверх по дереву до самого корня.
Почему B-деревья так эффективны для баз данных?
- Оптимизация под дисковый ввод-вывод: Узлы B-дерева имеют большой размер, сопоставимый с размером страницы на диске. Это позволяет за одну операцию чтения с диска загрузить сразу много ключей, минимизируя количество медленных дисковых операций.
- Сбалансированность: Дерево всегда остается сбалансированным, что гарантирует логарифмическую сложность поиска в худшем случае. Нет "длинных" ветвей.
- Поддержка запросов по диапазону: Так как ключи в листовых узлах отсортированы (и часто связаны двунаправленным списком), запросы вроде
WHERE id BETWEEN 100 AND 200выполняются очень быстро путем сканирования последовательных листовых узлов.
Пример использования в SQL:
-- Создание B-tree индекса (по умолчанию в большинстве СУБД)
CREATE INDEX idx_users_on_last_name ON users(last_name);