Этот вопрос проверяет понимание структуры B-tree индекса, который используется в базах данных для ускорения поиска и сортировки данных.
B-tree (Balanced Tree) — это иерархическая структура данных, оптимизированная для систем, которые читают и записывают большие блоки информации, например, базы данных и файловые системы. Его ключевая особенность — поддержание сбалансированности, что гарантирует, что время доступа к любому элементу остаётся логарифмическим относительно общего числа элементов, независимо от порядка вставки.
Каждый узел B-tree содержит:
Узел может хранить от t-1 до 2t-1 ключей, где t — минимальная степень дерева. Это позволяет узлам быть "широкими", уменьшая высоту дерева и количество операций ввода-вывода.
Поиск: Начинается с корня. В узле выполняется бинарный поиск по ключам. Если ключ найден (в листовом узле) — возвращаются данные. Если нет — алгоритм переходит в соответствующий дочерний узел и повторяет процесс.
Вставка: Элемент всегда добавляется в листовой узел. Если узел переполняется (ключей становится больше 2t-1), он разделяется на два узла, а средний ключ поднимается в родительский узел. Это может вызвать цепную реакцию разделения вплоть до корня.
Удаление: Более сложная операция. Если удаление приводит к тому, что узел содержит меньше t-1 ключей, он может "занять" ключ у соседнего узла или объединиться с ним, чтобы сохранить свойства дерева.
Рассмотрим простой B-tree с минимальной степенью t=2 (также называемый B-tree порядка 2 или 2-3 дерево). Допустим, у нас есть ключи: 10, 20, 30, 40, 50, 60, 70.
// Примерная структура после вставки:
// Корневой узел: [30]
// Левый дочерний: [10, 20]
// Правый дочерний: [40, 50, 60, 70]
// Алгоритм поиска ключа 45:
1. Начинаем с корня [30]. 45 > 30, идём в правого потомка.
2. В узле [40,50,60,70] ищем 45. Он находится между 40 и 50.
3. Следуем по ссылке между этими ключами (в соответствующем дочернем узле).
4. В листовом узле ключ 45 не найден — поиск завершается неудачей.
B-tree индексы — основа большинства систем управления реляционными базами данных (РСУБД). Они используются для:
WHERE id = 5) и диапазона (WHERE age BETWEEN 20 AND 30).ORDER BY), так как ключи в листьях хранятся отсортированно.Преимущество перед бинарными деревьями (например, красно-чёрными) — лучшая локализация данных. Поскольку узел B-tree может хранить сотни ключей, он идеально соответствует размеру страницы диска (например, 4KB или 16KB). Это минимизирует количество дорогостоящих операций чтения с диска.
Вывод: B-tree индекс следует применять в качестве индекса по умолчанию для большинства столбцов в OLTP-системах, где важны частые поиски, вставки, удаления и запросы по диапазонам. Он обеспечивает стабильную логарифмическую производительность и эффективно использует дисковый ввод-вывод.