B-tree (балансированное дерево) — это структура данных, которая позволяет эффективно искать, вставлять и удалять данные. В контексте баз данных B-tree индексы используются для ускорения запросов. **Основные особенности:** - Дерево всегда остается сбалансированным (все листья на одном уровне). - Каждый узел содержит ключи и ссылки на дочерние узлы. - Ключи в узле отсортированы, что позволяет использовать бинарный поиск. - Высота дерева логарифмическая, что обеспечивает быстрый доступ. **Пример структуры узла:** ``` class BTreeNode: def __init__(self, leaf=False): self.leaf = leaf self.keys = [] # Ключи (значения индекса) self.children = [] # Ссылки на дочерние узлы ``` **Применение в базах данных:** - Поиск по диапазону (`WHERE id BETWEEN 10 AND 20`). - Сортировка (`ORDER BY`). - Ускорение `JOIN`, `GROUP BY`. B-tree оптимален для дисковых операций, так как минимизирует количество чтений (обычно 3-4 уровня глубины для миллионов записей).