Что такое индекс B-Tree

B-Tree (балансированное дерево) — это структура данных, используемая в базах данных и файловых системах для эффективного поиска, вставки и удаления данных. В Java часто применяется в индексах СУБД (например, MySQL, PostgreSQL).

Особенности:

• Автоматически балансируется, сохраняя одинаковую глубину всех листьев.
• Поддерживает быстрый поиск, вставку и удаление за O(log n).
• Каждый узел может содержать множество ключей и дочерних узлов (в отличие от бинарного дерева).

Пример (упрощённый B-Tree в Java):

class BTreeNode {
    int[] keys;
    BTreeNode[] children;
    boolean isLeaf;

    BTreeNode(int degree, boolean isLeaf) {
        this.keys = new int[2 * degree - 1];
        this.children = new BTreeNode[2 * degree];
        this.isLeaf = isLeaf;
    }
}

Применение:

• Индексы в БД для ускорения WHERE, JOIN, ORDER BY.
• Хранение больших данных на диске с минимизацией чтений.