Внешний поиск. B-деревья.

Определение

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

Свойства

• Сбалансированная структура дерева: Все листовые узлы находятся на одном уровне, что обеспечивает сбалансированную высоту дерева и способствует эффективному выполнению операций.
• Порядок и вместимость узлов: Порядок B-дерева, обозначаемый как "m", указывает на максимальное количество потомков, которое может иметь узел. Узел в B-дереве порядка "m" может иметь до "m-1" ключей и "m" потомков.
• Минимальное количество потомков: Каждый узел, кроме корня, должен иметь как минимум ⌈m/2⌉ потомков
• Корневой узел: Корневой узел должен содержать как минимум два потомка, если он не является листом.
• Листовые узлы: Все листовые узлы находятся на одном уровне.

Операции

• Поиск: Поиск ключа в B-дереве начинается с корня и продолжается через внутренние узлы, пока не будет найден нужный ключ или достигнут листовой узел. Время поиска в среднем составляет O(log n).
• Вставка: Новые ключи добавляются в соответствующее место в существующем узле. Если узел переполняется (превышает максимальное количество ключей), он делится на два узла, и средний ключ перемещается вверх к родительскому узлу и начинает указывать на два новых узла. Время вставки также O(log n).
• Удаление: Удаление ключа может быть более сложным, так как необходимо поддерживать свойства B-дерева. Если удаление ключа приводит к тому, что узел становится слишком малым (меньше минимального количества ключей), могут потребоваться слияние с соседним узлом или перемещение ключей из родительского узла. Время удаления — O(log n).