B-Tree (Сбалансированное дерево)

Что такое B-Tree

B-Tree (Balanced Tree) — самобалансирующееся дерево поиска, в котором каждый узел может хранить несколько ключей и иметь несколько дочерних узлов. Разработано в 1970 году Рудольфом Байером и Эдом МакКрейтом для эффективной работы с дисковым хранилищем.

Основные свойства

Для B-Tree порядка t (минимальная степень, t ≥ 2):

Свойство Значение
Минимум ключей в узле t - 1 (кроме корня)
Максимум ключей в узле 2t - 1
Минимум дочерних узлов t (для внутреннего узла)
Максимум дочерних узлов 2t
Все листья на одном уровне
Ключи в узле отсортированы по возрастанию

Структура узла

┌─────────────────────────────────────────────┐
│  P0 │ K1 │ P1 │ K2 │ P2 │ K3 │ P3 │ ... │  │
└─────────────────────────────────────────────┘
  ↑         ↑         ↑         ↑
указатель  ключ   указатель  ключ
на детей          на детей

Визуализация структуры

graph TD Root["[10 | 20 | 30]"] Root --> C1["[3 | 7]"] Root --> C2["[15 | 17]"] Root --> C3["[25 | 27]"] Root --> C4["[35 | 40]"] C1 --> L1["[1 | 2]"] C1 --> L2["[4 | 5 | 6]"] C1 --> L3["[8 | 9]"] C2 --> L4["[11 | 12]"] C2 --> L5["[16]"] C2 --> L6["[18 | 19]"] C3 --> L7["[21 | 22]"] C3 --> L8["[26]"] C3 --> L9["[28 | 29]"] C4 --> L10["[31 | 33]"] C4 --> L11["[37 | 38]"] C4 --> L12["[42 | 45]"]

Основные операции

🔍 Поиск — O(log n)

  1. Начинаем с корня
  2. В текущем узле ищем первый ключ ≥ target
  3. Если нашли точное совпадение → готово
  4. Если дошли до листа и не нашли → не существует
  5. Иначе → переходим в соответствующего потомка
Поиск 16 в дереве выше:
Корень [10|20|30]: 16 < 20 → идём в P1
Узел [15|17]:     15 < 16 < 17 → идём в P1
Лист [16]:        16 == 16 ✓

➕ Вставка — O(log n)

Ключевое правило: нельзя вставлять в переполненный узел (2t-1 ключей).

Алгоритм (проактивное разбиение):

1. Спускаемся от корня к нужному листу
2. Если встречаем полный узел (2t-1 ключей) — разбиваем ДО входа в него
3. Вставляем ключ в лист

Разбиение (Split) узла:

До:  Родитель[...] → Полный узел [K1 K2 K3 K4 K5]  (t=3, max=5)
                                         ↑
                                   медианный ключ K3

После: Родитель[... K3 ...] 
              ↙           ↘
       [K1 K2]           [K4 K5]

Медиана поднимается в родителя, узел делится на два.

➖ Удаление — O(log n)

Три случая:

Случай Ситуация Действие
1 Ключ в листе Удалить напрямую
2 Ключ во внутреннем узле Заменить на predecessor/successor из листа, удалить оттуда
3 Узел после удаления опустеет Слияние (merge) или перераспределение с соседом

Слияние (Merge):

Родитель [...K...]          Родитель [...]
     ↙        ↘    →              ↓
 [A B]       [D E]          [A B K D E]
(бедный)   (бедный)          (слитый)

Перераспределение (Rotation):

Родитель [...K...]          Родитель [...B...]
     ↙        ↘    →             ↙        ↘
 [A]       [B C D]           [A K]       [C D]
(бедный)   (богатый)

Сложность операций

{
  "title": { "text": "Сложность операций B-Tree" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["O(log n)", "O(n) — худший случай других структур"] },
  "xAxis": {
    "type": "category",
    "data": ["1K", "10K", "100K", "1M", "10M", "100M"]
  },
  "yAxis": {
    "type": "value",
    "name": "Операций"
  },
  "series": [
    {
      "name": "O(log n)",
      "type": "line",
      "data": [10, 13, 17, 20, 23, 27],
      "smooth": true,
      "lineStyle": { "color": "#5cb85c", "width": 3 }
    },
    {
      "name": "O(n) — худший случай других структур",
      "type": "line",
      "data": [1000, 10000, 100000, 1000000, 10000000, 100000000],
      "smooth": true,
      "lineStyle": { "color": "#d9534f", "width": 2, "type": "dashed" }
    }
  ]
}
Операция Среднее Худшее
Поиск O(log n) O(log n)
Вставка O(log n) O(log n)
Удаление O(log n) O(log n)
Обход O(n) O(n)

Высота дерева: h = O(log_t n) — чем больше t, тем ниже дерево

B-Tree vs B+Tree

B-Tree B+Tree
Данные хранятся В любом узле Только в листьях
Листья связаны Нет Да (linked list)
Range queries Медленнее Очень быстро
Применение Файловые системы Большинство СУБД

Где используется