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.
Мотивация и интуиция
На диске дорого не сравнение, а обращение к странице. Двоичное дерево делает одно сравнение на уровень, но на диске это означает одно чтение страницы на уровень — до [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.
Операции и алгоритмы
Операция: поиск (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).
Операция: вставка (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).
Крайние случаи. Первая вставка — единственный лист. Дубликат — отклоняется.
Операция: удаление (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.
Реализация на 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.
Трассировка примера
Минимальная степень [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.