Как устроен B-tree индекс

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 уровня глубины для миллионов записей).