B-дерево

TL;DR

B-дерево (B-tree) — сбалансированное многопутевое дерево поиска, устроенное под внешнюю память: каждый узел занимает страницу диска; некорневой узел хранит от [math]\displaystyle{ t-1 }[/math] до [math]\displaystyle{ 2t-1 }[/math] ключей, корень — от 1 до [math]\displaystyle{ 2t-1 }[/math] ([math]\displaystyle{ t }[/math] — минимальная степень). Все листья лежат на одной глубине, поэтому дерево идеально сбалансировано. Поиск, вставка и удаление выполняются за [math]\displaystyle{ O(\log_t n) }[/math] чтений страниц и [math]\displaystyle{ O(t\log_t n) }[/math] сравнений. При ветвлении в сотни ключей на страницу высота для [math]\displaystyle{ 10^9 }[/math] ключей — всего несколько уровней. B-дерево описали Байер и Маккрейт в 1972 году; его варианты — B⁺-дерево (данные в листьях, связанные листья) и B*-дерево (занятость [math]\displaystyle{ \ge 2/3 }[/math]) — стали основой индексов СУБД и файловых систем.

Свойство	Значение
Класс	Сбалансированное многопутевое дерево поиска (семейство B-деревьев)
Изобретение	Байер и Маккрейт, 1972 [2]
Ключей в узле	от [math]\displaystyle{ t-1 }[/math] до [math]\displaystyle{ 2t-1 }[/math] (у корня от 1 до [math]\displaystyle{ 2t-1 }[/math])
Детей у узла	у внутреннего: [math]\displaystyle{ k }[/math] ключей → [math]\displaystyle{ k+1 }[/math] детей; у листа детей нет
Балансировка	Идеальная: все листья на одной глубине
Высота	[math]\displaystyle{ h \le \log_t \frac{n+1}{2} + 1 }[/math] (уровней)
Поиск	[math]\displaystyle{ O(\log_t n) }[/math] чтений страниц, [math]\displaystyle{ O(t\log_t n) }[/math] сравнений
Вставка / удаление	[math]\displaystyle{ O(\log_t n) }[/math] чтений страниц
Память	[math]\displaystyle{ O(n) }[/math]; узел = страница диска (сотни ключей)
Варианты	B⁺-дерево, B*-дерево, 2-3 дерево ([math]\displaystyle{ t=2 }[/math])
Где встречается	индексы СУБД, файловые системы, key-value хранилища

Определения

B-дерево с минимальной степенью [math]\displaystyle{ t \ge 2 }[/math] — корневое дерево, в котором:

каждый узел [math]\displaystyle{ x }[/math] хранит [math]\displaystyle{ k }[/math] ключей в возрастающем порядке; у внутреннего узла [math]\displaystyle{ k+1 }[/math] ссылок на детей, у листа детей нет;
у каждого узла, кроме корня, [math]\displaystyle{ k \in [t-1,\; 2t-1] }[/math] ключей; корень хранит от 1 до [math]\displaystyle{ 2t-1 }[/math] ключей;
все листья находятся на одной глубине (дерево идеально сбалансировано);
ключи разделяют поддеревья: если у внутреннего узла ключи [math]\displaystyle{ k_1 \lt k_2 \lt \dots \lt k_m }[/math], то в поддереве [math]\displaystyle{ c_0 }[/math] лежат ключи [math]\displaystyle{ \lt k_1 }[/math], в [math]\displaystyle{ c_i }[/math] — между [math]\displaystyle{ k_i }[/math] и [math]\displaystyle{ k_{i+1} }[/math], в [math]\displaystyle{ c_m }[/math] — [math]\displaystyle{ \gt k_m }[/math].

Полный узел — узел с [math]\displaystyle{ 2t-1 }[/math] ключами (максимум). Минимальная степень [math]\displaystyle{ t }[/math] удобна тем, что максимум и минимум ключей выражаются через неё; «порядок» [math]\displaystyle{ m = 2t }[/math] иногда используют как синоним.

Высота. Число уровней (корень — уровень 1). Так как каждый некорневой узел имеет не менее [math]\displaystyle{ t }[/math] детей, дерево высоты [math]\displaystyle{ h }[/math] содержит не менее [math]\displaystyle{ 2t^{h-1}-1 }[/math] ключей, откуда [math]\displaystyle{ h \le \log_t\frac{n+1}{2}+1 }[/math].

Обозначения. [math]\displaystyle{ n }[/math] — число ключей; [math]\displaystyle{ h }[/math] — высота; [math]\displaystyle{ t }[/math] — минимальная степень; страница — блок диска, вмещающий узел.

Строение узлов и уровней показано на рис. 1.

Рис. 1. Многоключевые узлы: ключи разделяют диапазоны детей; все листья на одной глубине. При [math]\displaystyle{ t=2 }[/math] допустимы 1–3 ключа на узел.

Мотивация и интуиция

На диске дорого не сравнение, а обращение к странице. Двоичное дерево делает одно сравнение на уровень, но на диске это означает одно чтение страницы на уровень — до [math]\displaystyle{ \log_2 n \approx 30 }[/math] чтений. B-дерево уменьшает число уровней, упаковывая в один узел (страницу) сотни ключей: ветвление становится огромным, а высота — логарифмом по большому основанию.

Интуиция балансировки тоже иная, чем у двоичных деревьев: вместо поворотов B-дерево держит все листья на одной глубине и поддерживает её через расщепление переполненных узлов и слияние опустевших. Переполненный узел делится ровно посередине, средний ключ поднимается в родителя; этот процесс может дойти до корня, увеличив высоту на 1 сразу для всех листьев. Обратная операция — слияние при удалении — уменьшает высоту.

Итог: мало чтений страниц, предсказуемая стоимость, естественная работа с блоками диска. Именно поэтому B-деревья и их варианты живут в ядрах СУБД и файловых систем.

Устройство

Узел B-дерева — это небольшая запись:

массив ключей keys[0..k-1] в порядке возрастания;
массив детей child[0..k] (у листа пуст);
признак листа.

Инварианты (поддерживаются всеми операциями):

порядок: ключи узла отсортированы, поддеревья разделены ими;
степень: [math]\displaystyle{ t-1 \le k \le 2t-1 }[/math] (у корня [math]\displaystyle{ 1 \le k \le 2t-1 }[/math]);
одна глубина листьев.

Узел рассчитан на страницу: число ключей [math]\displaystyle{ 2t-1 }[/math] подбирают так, чтобы узел вместе со ссылками занимал блок. Верхние уровни обычно держат в кэше, поэтому реально читаются нижние уровни и листья. Путь поиска по разделителям показан на рис. 2.

Рис. 2. Поиск спускается по разделителям; на каждом узле выбирается подходящий ребёнок. В примере число прочитанных узлов равно высоте (числу уровней).

Операции и алгоритмы

Операция: поиск (Search)

Идея. Спуск от корня: сравнить ключ с ключами узла и выбрать ребёнка; при совпадении — успех.

Пошаговое описание.

В текущем узле линейным (или бинарным) поиском найти позицию ключа.
Если ключ совпал — найдено.
Иначе, если узел лист — не найдено; иначе — спуститься в выбранного ребёнка.

Инвариант. Искомый ключ, если он есть, лежит в поддереве текущего узла.

Псевдокод.

Алгоритм B-Tree-Search(x, k)
1  i ← 0
2  while i < num[x] and k > key[x][i]
3      i ← i + 1
4  if i < num[x] and k = key[x][i]
5      return (x, i)
6  if leaf[x]
7      return NIL
8  return B-Tree-Search(child[x][i], k)

Сложность: O(высота) чтений страниц = O(log_t n); сравнений O(t log_t n).
Корректность: разделители направляют k в единственного ребёнка, где он может лежать.

Крайние случаи. Ключ меньше всех — спуск в child[0]; больше всех — в последнего ребёнка.

Разбор на примере. Поиск 26: в корне 26 > 20 — вправо; в узле [25, 30] выполняется 25 < 26 < 30 — в среднего ребёнка; в листе [26] ключ найден (рис. 2).

Операция: расщепление полного узла (Split-Child)

Идея. Полный узел ([math]\displaystyle{ 2t-1 }[/math] ключей) делится посередине: средний ключ уходит в родителя, крайние образуют два узла по [math]\displaystyle{ t-1 }[/math] ключей.

Пошаговое описание.

У родителя [math]\displaystyle{ x }[/math] и полного ребёнка [math]\displaystyle{ y = \text{child}[x][i] }[/math] создать нового ребёнка [math]\displaystyle{ z }[/math].
Медиану [math]\displaystyle{ y.\text{key}[t-1] }[/math] поднять в [math]\displaystyle{ x }[/math].
Ключи после медианы перенести в [math]\displaystyle{ z }[/math]; при внутреннем [math]\displaystyle{ y }[/math] так же разделить детей.

Инвариант. Оба новых узла имеют [math]\displaystyle{ t-1 }[/math] ключей (минимум), порядок сохранён, глубина листьев не меняется.

Псевдокод.

Алгоритм B-Tree-Split-Child(x, i)
1  y ← child[x][i];  z ← новый узел
2  leaf[z] ← leaf[y]
3  key[x] ← вставить key[y][t−1] в позицию i
4  key[z] ← key[y][t .. 2t−2]            # t−1 ключей
5  если y не лист
6      child[z] ← child[y][t .. 2t−1]    # t детей
7  key[y] ← key[y][0 .. t−2]             # t−1 ключей
8  child[x] ← вставить z в позицию i+1

Сложность: O(t) работы, O(1) записей страниц (кроме самого узла).
Корректность: узел делится ровно посередине; медиана сохраняет порядок,
оба результата имеют минимально допустимое число ключей.

Крайний случай. Расщепление корня — единственный способ увеличить высоту.

Разбор на примере. При [math]\displaystyle{ t = 2 }[/math] полный узел [10, 20, 30] делится на [10] и [30], а медиана 20 поднимается в родителя (рис. 3).

Рис. 3. Полный узел делится на два по [math]\displaystyle{ t-1 }[/math] ключей; медиана поднимается в родителя.

Операция: вставка (Insert)

Идея. Вставку делают за один проход сверху вниз: упреждающе расщепляя полные узлы, прежде чем войти в них. Тогда вставка всегда попадает в неполный лист.

Пошаговое описание.

Если корень полон — расщепить корень (создав новый корень): высота +1.
Insert-Nonfull(x, k): если [math]\displaystyle{ x }[/math] лист — вставить ключ по порядку.
Иначе найти нужного ребёнка; если он полон — расщепить его и выбрать ребёнка по обновлённому разделителю; рекурсивно спуститься.

Инвариант. При входе в Insert-Nonfull(x, k) узел [math]\displaystyle{ x }[/math] неполон, поэтому вставка не переполнит его без предварительного расщепления ребёнка.

Псевдокод.

Алгоритм B-Tree-Insert(T, k)
1  if root[T] = NIL
2      root[T] ← новый лист с ключом k;  return
3  if num[root[T]] = 2t − 1
4      s ← новый внутренний узел;  child[s][0] ← root[T];  root[T] ← s
5      B-Tree-Split-Child(s, 0)
6      B-Tree-Insert-Nonfull(s, k)
7  else
8      B-Tree-Insert-Nonfull(root[T], k)

Алгоритм B-Tree-Insert-Nonfull(x, k)
9  if leaf[x]
10     if k уже есть в key[x]  return          # дубликат
11     вставить k в key[x] по порядку
12 else
13     i ← выбрать ребёнка по k
14     if i < num[x] and k = key[x][i]  return # дубликат во внутреннем узле
15     if num[child[x][i]] = 2t − 1
16         B-Tree-Split-Child(x, i)
17         if k = key[x][i]  return            # дубликат — поднятая медиана
18         if k > key[x][i]  i ← i + 1
19     B-Tree-Insert-Nonfull(child[x][i], k)

Сложность: O(log_t n) чтений страниц; по пути — O(1) расщеплений на уровень.
Корректность: упреждающее расщепление гарантирует, что спуск идёт по неполным узлам,
и вставка завершается в листе без рекурсии вверх; проверки равенства не дают вставить
дубликат.

Разбор на примере. Вставка 12 при полном ребёнке [5 | 10 | 15]: расщепляем ребёнка (медиана 10 поднимается в корень), затем спускаемся и вставляем 12 в лист (рис. 4).

Крайние случаи. Первая вставка — единственный лист. Дубликат — отклоняется.

Рис. 4. Полный узел расщепляется по пути вниз; вставка идёт сверху вниз за один проход.

Операция: удаление (Delete)

Идея. Удалить ключ и, если у узла стало меньше [math]\displaystyle{ t-1 }[/math] ключей, заимствовать ключ у соседа или слить узлы; при удалении из внутреннего узла заменять ключ предшественником/преемником.

Пошаговое описание.

Найти ключ.
Если он во внутреннем узле: заменить предшественником (максимум левого поддерева) или преемником; далее удалять из листа.
Если в листе после удаления меньше [math]\displaystyle{ t-1 }[/math] ключей:
- у соседа есть запас — заимствовать (ключ через родителя);
- иначе слить с соседом, опустив разделитель из родителя.
Если родитель теряет ключ и «недогружается» — повторить выше.
Если корень остался без ключей — его единственный ребёнок становится новым корнем (высота −1).

Инвариант. Порядок, одна глубина листьев и границы [math]\displaystyle{ [t-1, 2t-1] }[/math] восстанавливаются на каждом уровне.

Псевдокод (схема).

Алгоритм B-Tree-Delete(T, k)
1  найти ключ k
2  if k во внутреннем узле
3      заменить k предшественником/преемником;  перейти к листу
4  удалить k из листа
5  while узел недогружен (num < t−1) и узел ≠ root[T]
6      if у соседа есть запас
7          заимствовать ключ через родителя;  break
8      else
9          слить узел с соседом, опустив разделитель
10         узел ← родитель
11 if корень пуст
12     root[T] ← его единственный ребёнок      # высота −1

Сложность: O(log_t n) чтений страниц.
Корректность: заимствование и слияние сохраняют порядок и одну глубину листьев.

Крайние случаи. Удаление единственного ключа корня-листа — дерево пустеет. Удаление отсутствующего ключа — no-op.

Разбор на примере. При [math]\displaystyle{ t = 2 }[/math] удаление 20 из корня [20] заменяет его преемником 30, после чего 30 удаляется из правого листа; шаги 5–6 трассировки показывают дальнейшее слияние. Оба способа восстановления показаны на рис. 5.

Рис. 5. Недогруженный узел восстанавливают заимствованием у соседа или слиянием; слияние может уменьшить высоту.

Реализация на C++

Реализация с поиском, вставкой (упреждающее расщепление) и проверкой инвариантов validate (порядок, границы ключей, одна глубина листьев). Удаление опущено — оно объёмнее, но структурно повторяет вставку.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

class BTree {
    int t_;                             // минимальная степень
    struct Node {
        bool leaf = true;
        std::vector<int> keys;
        std::vector<Node*> ch;          // дети (k+1, только у внутренних)
        explicit Node(bool l) : leaf(l) {}
    };
    Node* root_ = nullptr;

    void splitChild(Node* x, int i) {
        Node* y = x->ch[i];
        Node* z = new Node(y->leaf);
        int med = y->keys[t_ - 1];
        z->keys.assign(y->keys.begin() + t_, y->keys.end());   // t-1 ключей
        y->keys.resize(t_ - 1);
        if (!y->leaf) {
            z->ch.assign(y->ch.begin() + t_, y->ch.end());     // t детей
            y->ch.resize(t_);
        }
        x->keys.insert(x->keys.begin() + i, med);
        x->ch.insert(x->ch.begin() + i + 1, z);
    }

    void insertNonfull(Node* x, int k) {
        if (x->leaf) {
            auto it = std::lower_bound(x->keys.begin(), x->keys.end(), k);
            if (it != x->keys.end() && *it == k) return;       // дубликат
            x->keys.insert(it, k);
            return;
        }
        int i = 0;
        while (i < static_cast<int>(x->keys.size()) && k > x->keys[i]) ++i;
        if (i < static_cast<int>(x->keys.size()) && x->keys[i] == k) return;
        if (static_cast<int>(x->ch[i]->keys.size()) == 2 * t_ - 1) {
            splitChild(x, i);
            if (k == x->keys[i]) return;
            if (k > x->keys[i]) ++i;
        }
        insertNonfull(x->ch[i], k);
    }

    bool check(const Node* n, bool isRoot, int depth, int& leafDepth,
               const int* lo, const int* hi) const {
        int K = static_cast<int>(n->keys.size());
        if (K > 2 * t_ - 1) return false;                       // слишком много ключей
        if (!isRoot && K < t_ - 1) return false;               // слишком мало ключей
        if (isRoot && K < 1) return false;
        for (int j = 0; j < K; ++j) {
            if (lo && !(*lo < n->keys[j])) return false;
            if (hi && !(n->keys[j] < *hi)) return false;
            if (j > 0 && !(n->keys[j - 1] < n->keys[j])) return false;
        }
        if (n->leaf) {
            if (!n->ch.empty()) return false;
            if (leafDepth == -1) leafDepth = depth;
            return depth == leafDepth;
        }
        if (static_cast<int>(n->ch.size()) != K + 1) return false;
        for (int j = 0; j <= K; ++j) {
            const int* l = (j == 0) ? lo : &n->keys[j - 1];
            const int* h = (j == K) ? hi : &n->keys[j];
            if (!check(n->ch[j], false, depth + 1, leafDepth, l, h)) return false;
        }
        return true;
    }

    static void destroy(Node* n) {
        if (!n) return;
        for (Node* c : n->ch) destroy(c);
        delete n;
    }

public:
    explicit BTree(int t) : t_(t) { assert(t >= 2); }
    ~BTree() { destroy(root_); }
    BTree(const BTree&) = delete;
    BTree& operator=(const BTree&) = delete;

    void insert(int k) {
        if (!root_) { root_ = new Node(true); root_->keys = {k}; return; }
        if (static_cast<int>(root_->keys.size()) == 2 * t_ - 1) {   // корень полон
            Node* s = new Node(false);
            s->ch.push_back(root_);
            root_ = s;
            splitChild(s, 0);
            insertNonfull(s, k);
        } else {
            insertNonfull(root_, k);
        }
    }

    bool contains(int k) const {
        const Node* cur = root_;
        while (cur) {
            int i = 0;
            while (i < static_cast<int>(cur->keys.size()) && k > cur->keys[i]) ++i;
            if (i < static_cast<int>(cur->keys.size()) && cur->keys[i] == k) return true;
            if (cur->leaf) return false;
            cur = cur->ch[i];
        }
        return false;
    }

    bool validate() const {
        if (!root_) return true;
        int leafDepth = -1;
        return check(root_, true, 0, leafDepth, nullptr, nullptr);
    }
};

int main() {
    BTree t(3);                                 // до 5 ключей в узле
    for (int i = 1; i <= 200; ++i) t.insert((i * 37) % 200);
    assert(t.validate());
    for (int x = 0; x < 200; ++x) assert(t.contains(x));
    assert(!t.contains(999));

    BTree u(2);                                 // t = 2: 1–3 ключа в узле
    for (int i = 0; i < 5000; ++i)
        u.insert(static_cast<int>((i * 2654435761u) % 100000));
    assert(u.validate());

    std::cout << "ok\n";
    return 0;
}

Замечания по реализации.

Минимальная степень [math]\displaystyle{ t }[/math] задаёт максимум ключей [math]\displaystyle{ 2t-1 }[/math]; на диске [math]\displaystyle{ t }[/math] подбирают под размер страницы.
Упреждающее расщепление делает вставку однонаправленной (нет рекурсии вверх).
validate проверяет границы ключей, порядок и одну глубину листьев.
Удаление реализуется отдельно (заимствование/слияние); идейно это «обратная» вставка.

Сводная таблица сложности

Операция	Чтений страниц	Сравнений	Замечание
Search	[math]\displaystyle{ O(\log_t n) }[/math]	[math]\displaystyle{ O(t\log_t n) }[/math]	не более высоты; в примере — ровно
Insert	[math]\displaystyle{ O(\log_t n) }[/math]	[math]\displaystyle{ O(t\log_t n) }[/math]	[math]\displaystyle{ O(1) }[/math] расщеплений на уровень
Delete	[math]\displaystyle{ O(\log_t n) }[/math]	[math]\displaystyle{ O(t\log_t n) }[/math]	заимствование/слияние за [math]\displaystyle{ O(1) }[/math]
Min / Max	[math]\displaystyle{ O(\log_t n) }[/math]	[math]\displaystyle{ O(1) }[/math]	спуск по крайним детям, без сравнений ключей
Height	—	—	[math]\displaystyle{ h \le \log_t\frac{n+1}{2}+1 }[/math]; [math]\displaystyle{ h }[/math] — число уровней

Примечание. Оценки даны в чтениях страниц (главный ресурс на диске). Высокое ветвление делает [math]\displaystyle{ \log_t n }[/math] крошечным: при [math]\displaystyle{ t = 50 }[/math] и [math]\displaystyle{ n = 10^9 }[/math] высота около 6 уровней против [math]\displaystyle{ \approx 30 }[/math] у двоичного дерева. Внутри узла поиск ключа — линейный или бинарный, отсюда множитель [math]\displaystyle{ t }[/math].

Зависимость высоты от [math]\displaystyle{ t }[/math] показана на рис. 6.

Рис. 6. Высота [math]\displaystyle{ h \le \log_t\frac{n+1}{2}+1 }[/math] (в уровнях); при большом [math]\displaystyle{ t }[/math] это единицы чтений страниц.

Трассировка примера

Минимальная степень [math]\displaystyle{ t = 2 }[/math] (1–3 ключа на узел). Вставим [math]\displaystyle{ 10, 20, 30, 40 }[/math], затем удалим [math]\displaystyle{ 20 }[/math] и [math]\displaystyle{ 10 }[/math], после чего найдём [math]\displaystyle{ 40 }[/math].

Шаг	Операция	Состояние (ключи по уровням)	Что произошло
1	insert 10	[10]	корень-лист
2	insert 20	[10, 20]	—
3	insert 30	[10, 20, 30]	узел полон (2t−1 = 3)
4	insert 40	корень [20]; дети [10], [30, 40]	корень расщеплён: 20 поднялось; высота +1
5	delete 20	корень [30]; дети [10], [40]	20 заменён преемником 30; удаление из листа
6	delete 10	корень-лист [30, 40]	лист [10] опустел; слияние с [40] и разделителем 30; пустой корень заменён ребёнком (высота −1)
7	search 40	найдено в корне-листе [30, 40]	путь длины 0

На шаге 4 впервые сработало расщепление корня: дерево выросло на уровень. На шаге 5 ключ 30 хранится во внутреннем узле, а на шаге 6 слияние возвращает дерево к одному корню-листу; все листья при этом остаются на одной глубине. validate() подтверждает инварианты.

Корректность и оценка сложности

Лемма 1 (граница высоты). B-дерево с [math]\displaystyle{ n }[/math] ключами, минимальной степенью [math]\displaystyle{ t }[/math] и высотой [math]\displaystyle{ h }[/math] (в уровнях) удовлетворяет [math]\displaystyle{ h \le \log_t\frac{n+1}{2}+1 }[/math].

Доказательство. Корень — уровень 1; на уровне 1 не менее одного узла, на уровне 2 — не менее двух, на уровне 3 — не менее [math]\displaystyle{ 2t }[/math], ..., на уровне [math]\displaystyle{ h }[/math] — не менее [math]\displaystyle{ 2t^{h-2} }[/math] узлов ([math]\displaystyle{ h \ge 2 }[/math]). Каждый узел, кроме корня, хранит не менее [math]\displaystyle{ t-1 }[/math] ключей, корень — не менее одного, поэтому [math]\displaystyle{ n \ge 1 + (t-1)(2 + 2t + \dots + 2t^{h-2}) = 2t^{h-1} - 1 }[/math], откуда [math]\displaystyle{ h \le \log_t\frac{n+1}{2}+1 }[/math]. [math]\displaystyle{ \blacksquare }[/math]

Лемма 2 (корректность расщепления). Split-Child для полного узла даёт два узла по [math]\displaystyle{ t-1 }[/math] ключей, сохраняя порядок и глубину листьев.

Доказательство. Из [math]\displaystyle{ 2t-1 }[/math] ключей медиана [math]\displaystyle{ t }[/math]-й (индекс [math]\displaystyle{ t-1 }[/math]) уходит в родителя; слева остаётся [math]\displaystyle{ t-1 }[/math] ключей, справа — [math]\displaystyle{ t-1 }[/math]. Дети делятся так, что у каждого нового узла ровно на одного ребёнка больше, чем ключей. Порядок сохраняется, листья остаются на прежней глубине. [math]\displaystyle{ \blacksquare }[/math]

Теорема 3 (корректность вставки). После Insert дерево остаётся корректным B-деревом. Если ключа не было, он добавлен; если ключ уже был, набор ключей не меняется, хотя структура может измениться из-за упреждающего расщепления.

Доказательство. Упреждающее расщепление гарантирует, что спуск идёт по неполным узлам: у каждого узла на пути после расщепления ребёнка есть место для ключа. В листе вставка не переполняет узел; порядок и границы сохраняются. При дубликате псевдокод возвращает управление, не добавляя ключ; уже выполненные расщепления сохраняют корректность и одну глубину листьев. Расщепление корня увеличивает глубину всех листьев на 1, сохраняя идеальную балансировку. Индукция по высоте. [math]\displaystyle{ \blacksquare }[/math]

Теорема 4 (корректность удаления). После Delete дерево остаётся корректным B-деревом без удалённого ключа. (Доказательство аналогично: заимствование и слияние сохраняют порядок, границы ключей и одну глубину листьев; пустой корень заменяется ребёнком.)

Оценка сложности. Путь до листа — длина [math]\displaystyle{ h = O(\log_t n) }[/math]; на каждом узле [math]\displaystyle{ O(t) }[/math] работы (поиск ключа и перераспределение), отсюда [math]\displaystyle{ O(t\log_t n) }[/math] сравнений и [math]\displaystyle{ O(\log_t n) }[/math] чтений страниц.

Сравнение с альтернативами

Структура	Данные	Мин. занятость	Расщепление	Диапазон	Когда выбирать
B-дерево	во всех узлах	[math]\displaystyle{ \approx 1/2 }[/math]	1 → 2	дороже	наборы без диапазонов, меньше дублирования
B⁺-дерево	только в листьях	[math]\displaystyle{ \approx 1/2 }[/math]	1 → 2	быстрое (связи листьев)	индексы СУБД и файловые системы
B*-дерево	во всех узлах	[math]\displaystyle{ 2/3 }[/math]	2 → 3	дороже	плотность хранения и минимум расщеплений
2-3 дерево	во всех узлах	—	—	—	учебная модель ([math]\displaystyle{ t=2 }[/math])
КЧ-дерево	в узлах (в памяти)	—	повороты	[math]\displaystyle{ O(\log n + k) }[/math]	данные целиком в оперативной памяти
LSM-дерево	уровни, слияние	—	слияние уровней	быстро на запись	write-heavy нагрузки

Минимальная занятость B-дерева и B⁺-дерева — [math]\displaystyle{ (t-1)/(2t-1) }[/math]; при больших [math]\displaystyle{ t }[/math] она близка к [math]\displaystyle{ 1/2 }[/math].

Вердикт. Для диска B-дерево и его варианты вне конкуренции: высокое ветвление и одна глубина листьев дают мало чтений страниц. В памяти чаще берут двоичные деревья (компактнее на узел). Среди вариантов B: B⁺ — когда важны диапазоны (СУБД, ФС); B* — когда важна плотность и редкие расщепления; классическое B-дерево — когда нужны и точечные запросы, и минимальное дублирование ключей.

Где применяется

Индексы реляционных СУБД. B-деревья и B⁺-деревья лежат в основе индексов (InnoDB, Oracle, PostgreSQL) — точечные и диапазонные запросы, упорядоченный обход [1], [4].
Файловые системы. NTFS, XFS, ext4, Btrfs, HFS+ хранят метаданные и каталоги в B-деревьях и их вариантах: нужен быстрый поиск по имени и обход каталога без полного сканирования [6].
Встраиваемые и key-value БД. SQLite, Berkeley DB, LMDB используют B-деревья/B⁺-деревья для упорядоченных наборов на диске, когда важен и точечный поиск, и диапазонный обход [4], [6].
Пространственные и многомерные индексы. R-деревья и их варианты развивают идеи B-деревьев для диапазонных запросов по нескольким измерениям [6].

Историческая справка

1972. Р. Байер и Э. Маккрейт описали B-деревья (Bayer–McCreight) как структуру для больших индексов на диске [2].
1970-е. Появились варианты: B⁺ (данные в листьях, связи листьев) и B* (занятость [math]\displaystyle{ \ge 2/3 }[/math], расщепление «два-в-три») [3], [5].
1979. Д. Комер в обзоре «The Ubiquitous B-Tree» систематизировал семейство и его применения [5].
1980-е–наст. B-деревья стали стандартом индексов СУБД и ФС; конкуренцию им составили LSM-деревья для записи-ориентированных нагрузок [1], [4], [5].

Типичные ошибки и подводные камни

Неверные границы ключей. У некорневого узла должно быть от [math]\displaystyle{ t-1 }[/math] до [math]\displaystyle{ 2t-1 }[/math] ключей; ошибки в границах ломают баланс.
Расщепление не посередине. Медиана — ключ с индексом [math]\displaystyle{ t-1 }[/math]; смещение даёт недопустимые узлы.
Забыть про корень. Корень — исключение: может иметь один ключ; его расщепление — единственный способ поднять высоту.
Путаница B-дерева и B⁺. У B-дерева ключи во всех узлах; у B⁺ — только в листьях.
Потеря порядка при вставке в неполный узел. Ключ нужно вставлять в отсортированную позицию.
Некорректное удаление из внутреннего узла. Замена предшественником/преемником обязательна.
Занятость при слиянии. Объединение должно опустить разделитель родителя; забытый разделитель теряет ключ.
Слишком малый [math]\displaystyle{ t }[/math]. Тогда узел не заполняет страницу и теряется весь смысл; [math]\displaystyle{ t }[/math] подбирают под размер блока.
Рекурсия вверх при вставке. Классическая схема использует упреждающее расщепление и не возвращается вверх; смешение двух схем — источник ошибок.
Дубликаты. Для множества ключ хранится один раз; для мультимножества нужны счётчики.

Задачи для практики

Поиск. Реализуйте contains с бинарным поиском в узле; проверьте на больших наборах. Подсказка: для линейного поиска в узле — [math]\displaystyle{ O(t\log_t n) }[/math] сравнений, для бинарного — [math]\displaystyle{ O(\log t\cdot\log_t n) }[/math].
Вставка. Реализуйте Split-Child и Insert-Nonfull; проверьте инварианты. Подсказка: упреждающее расщепление.
Удаление. Реализуйте заимствование и слияние; проверьте уменьшение высоты. Подсказка: границы [math]\displaystyle{ t-1 }[/math].
Высота. Докажите [math]\displaystyle{ h \le \log_t\frac{n+1}{2}+1 }[/math] и постройте деревья, дающие крайние высоты. Подсказка: все узлы полны против всех минимальны.
Размер страницы. Для [math]\displaystyle{ t=50 }[/math] оцените высоту при [math]\displaystyle{ n=10^9 }[/math] и число сравнений на поиск. Подсказка: [math]\displaystyle{ 2t-1 = 99 }[/math] ключей.
B против B⁺. На одном множестве сравните число чтений страниц при точечном и диапазонном запросе. Подсказка: диапазон — сильная сторона B⁺.
B против двоичного. Сравните высоту и число чтений при [math]\displaystyle{ n=10^6 }[/math] для [math]\displaystyle{ t=2,3,10,50 }[/math]. Подсказка: зависимость от [math]\displaystyle{ \log_t }[/math].
Занятость. Измерьте среднюю занятость узлов при случайных вставках. Подсказка: у B-дерева она заметно выше минимума [math]\displaystyle{ (t-1)/(2t-1) }[/math].

Связанные темы

B⁺-дерево — вариант с данными в листьях и диапазонным обходом.
B*-дерево — вариант с занятостью [math]\displaystyle{ \ge 2/3 }[/math].
2-3 дерево — минимальный случай [math]\displaystyle{ t=2 }[/math].
Красно-чёрное дерево — двоичная структура для памяти.
Асимптотическая сложность — нотация [math]\displaystyle{ O }[/math], [math]\displaystyle{ \Omega }[/math], [math]\displaystyle{ \Theta }[/math].

Источники

Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 18 «B-Trees» (минимальная степень, поиск, расщепление, вставка, удаление).
Bayer R., McCreight E. Organization and Maintenance of Large Ordered Indexes // Acta Informatica. — 1972. — Vol. 1, No. 3. — P. 173–189.
Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §6.2.4 «Multiway Trees».
Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts. — McGraw-Hill, 6th ed., 2011. — Гл. 11 «Indexing and Hashing».
Comer D. The Ubiquitous B-Tree // ACM Computing Surveys. — 1979. — Vol. 11, No. 2. — P. 121–137.
Wikipedia: B-tree. URL: https://en.wikipedia.org/wiki/B-tree.

Поиск

Навигация

B-дерево

Содержание

TL;DR

Определения

Мотивация и интуиция

Устройство

Операции и алгоритмы

Операция: поиск (Search)

Операция: расщепление полного узла (Split-Child)

Операция: вставка (Insert)

Операция: удаление (Delete)

Реализация на C++

Сводная таблица сложности

Трассировка примера

Корректность и оценка сложности

Сравнение с альтернативами

Где применяется

Историческая справка

Типичные ошибки и подводные камни

Задачи для практики

Связанные темы

Источники