Почему B-tree индекс имеет сложность O(log n)?

B-tree — это сбалансированное дерево с несколькими ключами в каждом узле, где все листья находятся на одном уровне. Высота дерева растёт логарифмически от количества элементов, потому что каждый узел содержит множество ключей (а не один, как в бинарном дереве), что уменьшает глубину дерева.

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

Пример: если в каждом узле хранится до m ключей, то высота дерева примерно равна log base m (n), что значительно меньше, чем в бинарном дереве, где m=2.