B+-дерево

Материал из Викиконспекты ПМ-ПУ

TL;DR

B⁺-дерево (B plus tree) — сбалансированное многопутевое дерево поиска, оптимизированное под внешнюю память. Его отличие от обычного B-дерева: все ключи и записи хранятся только в листьях, внутренние узлы содержат лишь разделители для навигации, а все листья связаны в список. Из-за высокого ветвления (сотни ключей на страницу) высота дерева крошечная: для [math]\displaystyle{ 10^9 }[/math] ключей при ветвлении около 100 это примерно 5 уровней, то есть около пяти чтений страниц на поиск. Диапазонные запросы выполняются почти линейно по объёму результата — спуск к началу и последовательный проход по связям листьев. За это B⁺-деревья стали стандартом индексов СУБД (InnoDB, Oracle, PostgreSQL) и файловых систем (NTFS, XFS, ext4, Btrfs).

Свойство Значение
Класс Сбалансированное многопутевое дерево поиска (семейство B-деревьев)
Изобретение Развитие B-дерева (Байер и Маккрейт, 1972 [4]); вариант B⁺ сформировался в 1970-е, популяризован обзором Комера, 1979 [5]
Данные Только в листьях; внутренние узлы — разделители
Листья Все на одной глубине, связаны в список
Ветвление [math]\displaystyle{ B \approx }[/math] (размер страницы) / (размер ключа + указатель), обычно десятки–сотни
Высота [math]\displaystyle{ h \le \log_B N + 1 }[/math] (уровней)
Поиск [math]\displaystyle{ O(\log_B N) }[/math] чтений страниц
Вставка / удаление [math]\displaystyle{ O(\log_B N) }[/math]
Диапазонный запрос [math]\displaystyle{ O(\log_B N + k/B) }[/math] — почти линейно по результату
Память [math]\displaystyle{ O(N) }[/math]; узлы занимают страницы фиксированного размера
Альтернативы B-дерево, LSM-дерево, хеш-индекс, КЧ-дерево (в памяти)
Где встречается индексы СУБД (InnoDB, Oracle, PostgreSQL, SQLite), файловые системы (NTFS, XFS, ext4, Btrfs), key-value хранилища

Определения

B⁺-дерево порядка [math]\displaystyle{ m }[/math] — сбалансированное дерево, в котором:

  1. Внутренние узлы содержат до [math]\displaystyle{ m-1 }[/math] ключей-разделителей и до [math]\displaystyle{ m }[/math] детей; ключей на один меньше, чем детей.
  2. Листья содержат до [math]\displaystyle{ m-1 }[/math] ключей (и связанные с ними записи/указатели на данные) и все лежат на одной глубине.
  3. Листья связаны в список (обычно двунаправленный), что даёт последовательный доступ.
  4. Для внутреннего узла с ключами [math]\displaystyle{ k_1 \lt k_2 \lt \dots }[/math] и детьми [math]\displaystyle{ c_0, c_1, \dots }[/math]: все ключи в поддереве [math]\displaystyle{ c_i }[/math] меньше [math]\displaystyle{ k_{i+1} }[/math], а в поддереве [math]\displaystyle{ c_{i+1} }[/math] — не меньше [math]\displaystyle{ k_{i+1} }[/math].

Узел содержит массив ключей и массив ссылок; лист дополнительно хранит ссылку next (и, при желании, prev) на соседний лист. Разделитель — ключ внутреннего узла; это копия первого ключа правого поддерева, а не отдельная запись.

Занятость (occupancy). Кроме корня, у внутреннего узла от [math]\displaystyle{ \lceil m/2 \rceil }[/math] до [math]\displaystyle{ m }[/math] детей, а у листа от [math]\displaystyle{ \lceil m/2 \rceil - 1 }[/math] до [math]\displaystyle{ m-1 }[/math] ключей. Нижняя граница учитывается при удалении.

Ветвление (fanout) [math]\displaystyle{ B }[/math] — число детей внутреннего узла; на диске [math]\displaystyle{ B \approx \text{page}/\,(\text{key}+\text{ptr}) }[/math]. Высота [math]\displaystyle{ h }[/math] — число уровней (корень — уровень 1); [math]\displaystyle{ h \le \log_B N + 1 }[/math], где [math]\displaystyle{ N }[/math] — число ключей.

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

Рис. 1. Внутренние узлы — разделители; все ключи в листьях; листья связаны в список.

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

Главное узкое место при работе с диском — не скорость вычислений, а число обращений к страницам: одно чтение с диска на много порядков дороже сравнения в памяти. Поэтому структура для внешней памяти должна минимизировать число страниц на операцию, а не число сравнений.

Отсюда идея B-дерева: держать в одном узле столько ключей, чтобы узел занимал целую страницу. Тогда ветвление [math]\displaystyle{ B }[/math] велико, а высота мала: [math]\displaystyle{ \log_B N }[/math] вместо [math]\displaystyle{ \log_2 N }[/math]. B⁺-дерево доводит эту идею до предела:

  • Все данные на одном уровне. Поиск всегда завершается в листе, число обращений одинаково для любого ключа — предсказуемая стоимость.
  • Внутренние узлы без данных → выше ветвление. Раз в узле только ключи и указатели, он вмещает больше разделителей, чем если бы хранил ещё и записи; дерево получается ниже.
  • Связанные листья. Диапазонные запросы (а их в СУБД большинство) обрабатываются последовательным проходом по листьям, без повторных спусков от корня.

Интуитивно B⁺-дерево — это «оглавление к отсортированному файлу»: внутренние узлы ускоряют поиск нужного места, а сам файл хранится листьями, идя по возрастанию ключей.

Устройство

  • Внутренний узел: ключи [k1, k2, …] и дети [c0, c1, …], где ci отвечает за ключи, попадающие между разделителями. Данных нет.
  • Лист: ключи и записи; ссылка next на следующий лист (при необходимости prev).
  • Корень: либо лист (маленькое дерево), либо внутренний узел; корень может иметь меньше половины детей.

Инварианты, которые поддерживают все операции:

  1. все листья на одной глубине;
  2. ключи в каждом узле отсортированы;
  3. разделители согласованы с поддеревьями (см. определение);
  4. занятость узлов в допустимых пределах (кроме корня).

На диске дерево хранится страницами; корень и верхние уровни обычно кэшируются в памяти, поэтому реально читаются только нижние уровни и листья. Сравнение с B-деревом показано на рис. 2.

Рис. 2. В B-дереве записи есть во всех узлах и ключ уникален; в B⁺-дереве данные только в листьях, разделители дублируют ключи, а листья связаны в список.

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

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

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

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

  1. Пока узел внутренний — сравнить ключ с разделителями и выбрать нужного ребёнка.
  2. Дойдя до листа — найти ключ (бинарным или линейным поиском).
  3. Если ключ есть — вернуть запись; иначе — «не найдено».

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

Псевдокод. 

Алгоритм Search(T, k)
1  cur ← root[T]
2  while not leaf[cur]
3      i ← 0
4      while i < numKeys[cur] and k ≥ key[cur][i]
5          i ← i + 1
6      cur ← child[cur][i]              # спуск в подходящего ребёнка
7  return Leaf-Search(cur, k)          # поиск внутри листа

Сложность: O(log_B N) чтений страниц — ровно высота дерева.
Корректность: разделители направляют k в единственный лист, где он может лежать.

Крайние случаи. Ключ отсутствует — спуск всё равно приводит к «соседнему» листу; сравнение в листе даёт «нет». Малое дерево из одного листа — поиск сразу в корне.

Разбор на примере. Поиск 25: 25 ≥ 20 — в правое поддерево; 25 < 40 — в средний лист [20, 25, 30], где ключ найден (рис. 1).

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

Идея. Вставить ключ в лист; при переполнении расщепить лист и поднять разделитель в родителя (рекурсивно вверх).

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

  1. Спуск до листа.
  2. Вставка ключа в лист (с сохранением порядка); при дубликате — обновление записи.
  3. Если ключей стало больше [math]\displaystyle{ m-1 }[/math] — расщепить лист на два: половина ключей уходит в новый лист, первый ключ правого листа поднимается разделителем, листья перевязываются.
  4. Если переполнился внутренний узел — расщепить и его: средний (по разделителям) ключ уходит вверх, дети делятся.
  5. Если расщепился корень — создать новый корень; высота +1.

Инвариант. Листья остаются на одной глубине; разделители согласованы; нарушением может быть лишь временное переполнение одного узла.

Псевдокод (рекурсивный). 

Алгоритм Insert(T, k)
1  (split, sep, right) ← Insert-Rec(root[T], k)
2  if split                                 # расщепился корень
3      newRoot ← внутренний узел с ключом sep и детьми (root[T], right)
4      root[T] ← newRoot                    # высота +1

Алгоритм Insert-Rec(node, k)                # возвращает (split, sep, right)
5  if leaf[node]
6      вставить k в key[node] (если дубликат — обновить запись и вернуть (false, NIL, NIL))
7      if numKeys[node] ≤ m − 1
8          return (false, NIL, NIL)
9      right ← новый лист с правой половиной ключей
10     next[right] ← next[node];  next[node] ← right
11     return (true, key[right][0], right)      # разделитель — первый ключ справа
12 i ← выбрать ребёнка по k
13 (split, sep, right) ← Insert-Rec(child[node][i], k)
14 if not split
15     return (false, NIL, NIL)
16 вставить sep и right в node (позиция i)
17 if numKeys[node] ≤ m − 1
18     return (false, NIL, NIL)
19 mid ← средний разделитель
20 right ← новый внутренний узел с разделителями после mid и их детьми
21 обрезать node до mid (ключи и дети)
22 return (true, mid, right)

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

Разбор на примере. Вставка 28 в полный лист [25 | 30 | 35] (максимум 3) даёт четыре ключа; лист расщепляется на [25 | 28] и [30 | 35], разделитель 30 поднимается в родителя (рис. 3). При переполнении родителя расщепление продолжается вверх; расщепление корня повышает высоту.

Крайние случаи. Пустое дерево — единственный лист. Дубликат — обновление записи без роста числа ключей (в «множестве» — игнорирование).

Рис. 3. Переполненный лист делится на два; копия первого ключа правого листа становится разделителем в родителе.

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

Идея. Удалить ключ из листа; при недостаче (меньше половины) перераспределить ключи с соседним листом или слить листья, убрав разделитель из родителя.

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

  1. Найти лист и удалить ключ.
  2. Если занятость в норме — обновить разделитель (если удалён первый ключ) и закончить.
  3. Если лист «недогружен»:
    • у соседа есть запас — перераспределить ключи и обновить разделитель;
    • иначе слить лист с соседом и убрать разделитель из родителя.
  4. Если родитель потерял ребёнка и стал недогружен — повторить пункт 3 выше.
  5. Если корень остался без детей — сделать его единственного ребёнка новым корнем (высота −1).

Инвариант. Порядок, одна глубина листьев и занятость восстанавливаются на каждом уровне.

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

Алгоритм Delete(T, k)
1  найти лист L с ключом k;  если ключа нет — выйти;  удалить k из L
2  while L недогружен и L ≠ root[T]   # корень с одним ребёнком свернуть до слияния
3      p ← parent[L];  sib ← сосед L справа или слева
4      if sib имеет запас
5          перераспределить ключи между L и sib;  обновить разделитель в p
6          break
7      else
8          слить L и sib;  убрать разделитель из p   # лист: удалить; внутренний: sep в merged.keys
9          L ← p                              # недостача поднялась выше
10 if root[T] лист и пуст
11     root[T] ← NIL
12 else if корень внутренний с одним ребёнком
13     root[T] ← единственный ребёнок            # высота −1

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

Для листа слияние объединяет ключи L и соседа, а разделитель p удаляется: он дублирует первый ключ правого листа. Здесь sep — разделитель p между L и sib; для левого соседа направления зеркальны. Для внутреннего узла merged.keys = L.keys + [sep] + sib.keys, merged.children = L.children + sib.children; разделитель sep входит в merged.keys, иначе получится children = keys + 2. При перераспределении внутренних узлов sep переносится вниз, граничный ключ соседа поднимается в p, а соответствующий ребёнок переносится. При удалении первого ключа листа разделитель обновляется в ближайшем предке, где это поддерево является правым. Если у корня остался один ребёнок, корень сворачивается до попытки слияния.

Крайние случаи. Удаление первого ключа листа требует обновить разделитель в ближайшем предке, где это поддерево является правым. Удаление последнего ключа дерева — дерево пустеет.

Разбор на примере. При порядке 4 удаление 15 из листа [15] оставляет его пустым. Если у соседа [30, 45] есть запас, ключ 30 переходит влево, а разделитель становится 45. Если сосед [30] без запаса, листья сливаются в [30], разделитель 30 убирается, и корень становится листом [30] — высота уменьшается на 1 (рис. 4).

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

Операция: диапазонный запрос (Range Scan)

Идея. Спуститься к листу с началом диапазона, затем последовательно пройти по связям листьев, собирая ключи. Find-Leaf(T, a) — спуск по разделителям до листа, в который попадает [math]\displaystyle{ a }[/math], без поиска внутри листа.

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

  1. Find-Leaf(T, a) нижней границы → лист, где начинается диапазон.
  2. Идти по next, собирая ключи в [math]\displaystyle{ [a, b] }[/math], пока не выйдем за верхнюю границу.

Инвариант. Листья содержат ключи в возрастающем порядке, поэтому обход по связям даёт именно диапазон.

Псевдокод. 

Алгоритм Range-Scan(T, a, b)
1  leaf ← Find-Leaf(T, a)
2  result ← пустой список
3  while leaf ≠ NIL
4      for each key k в leaf по возрастанию
5          if k < a  continue
6          if k > b  return result
7          result.добавить(k)
8      leaf ← next[leaf]
9  return result

Сложность: O(log_B N + k/B) чтений страниц, где k — число ключей в ответе (почти линейно).
Корректность: ключи листьев возрастают, и связи охватывают их все, поэтому результат —
ровно множество ключей в [a, b].

Крайние случаи. Пустой диапазон — результат пуст. Границы вне множества — просто нет совпадающих ключей.

Разбор на примере. Для диапазона [12, 45] спуск приводит в лист [8, 11, 15]; после пропуска 8 и 11 собираются 15, 20, 25, 30, 40, 45, а 50 уже выходит за границу (рис. 5).

Рис. 5. Спуск к началу диапазона, далее последовательный проход по связям листьев — без повторных спусков от корня.

Операции: минимум, максимум и обход

Min/Max — спуск к левому/правому листу, [math]\displaystyle{ O(\log_B N) }[/math]. Полный обход по возрастанию — найти левый лист и пройти по связям, [math]\displaystyle{ O(N/B) }[/math] чтений страниц.

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

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

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

class BPlusTree {
    static constexpr int MAX_KEYS = 3;      // порядок 4: не более 3 ключей в узле

    struct Node {
        bool leaf = true;
        std::vector<int> keys;              // листья: ключи; внутренние: разделители
        std::vector<Node*> children;        // только для внутренних
        Node* next = nullptr;               // только для листьев
        explicit Node(bool l) : leaf(l) {}
    };

    Node* root_ = nullptr;

    struct SplitResult { bool split; int sep; Node* right; };

    SplitResult insertRec(Node* node, int k) {
        if (node->leaf) {
            auto it = std::lower_bound(node->keys.begin(), node->keys.end(), k);
            if (it != node->keys.end() && *it == k) return {false, 0, nullptr};   // дубликат
            node->keys.insert(it, k);
            if (static_cast<int>(node->keys.size()) <= MAX_KEYS)
                return {false, 0, nullptr};
            // расщепление листа
            Node* right = new Node(true);
            int mid = static_cast<int>(node->keys.size()) / 2;
            right->keys.assign(node->keys.begin() + mid, node->keys.end());
            node->keys.resize(mid);
            right->next = node->next;
            node->next = right;
            return {true, right->keys.front(), right};       // разделитель — 1-й ключ справа
        }
        int i = 0;
        while (i < static_cast<int>(node->keys.size()) && k >= node->keys[i]) ++i;
        SplitResult s = insertRec(node->children[i], k);
        if (!s.split) return {false, 0, nullptr};
        node->keys.insert(node->keys.begin() + i, s.sep);
        node->children.insert(node->children.begin() + i + 1, s.right);
        if (static_cast<int>(node->keys.size()) <= MAX_KEYS)
            return {false, 0, nullptr};
        // расщепление внутреннего узла
        Node* right = new Node(false);
        int mid = static_cast<int>(node->keys.size()) / 2;
        right->keys.assign(node->keys.begin() + mid + 1, node->keys.end());
        right->children.assign(node->children.begin() + mid + 1, node->children.end());
        int sep = node->keys[mid];
        node->keys.resize(mid);
        node->children.resize(mid + 1);
        return {true, sep, right};
    }

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

    static int minKey(Node* n) { while (!n->leaf) n = n->children.front(); return n->keys.front(); }
    static int maxKey(Node* n) { while (!n->leaf) n = n->children.back();  return n->keys.back();  }

    bool check(Node* n, int depth, int& leafDepth) const {
        if (n->leaf) {
            if (static_cast<int>(n->keys.size()) > MAX_KEYS) return false;
            for (std::size_t i = 1; i < n->keys.size(); ++i)
                if (!(n->keys[i - 1] < n->keys[i])) return false;
            if (leafDepth == -1) leafDepth = depth;
            return depth == leafDepth;
        }
        if (static_cast<int>(n->keys.size()) > MAX_KEYS) return false;
        if (n->children.size() != n->keys.size() + 1) return false;
        for (std::size_t i = 0; i < n->keys.size(); ++i) {
            if (!(maxKey(n->children[i]) < n->keys[i])) return false;
            if (!(n->keys[i] <= minKey(n->children[i + 1]))) return false;
        }
        for (Node* c : n->children)
            if (!check(c, depth + 1, leafDepth)) return false;
        return true;
    }

    Node* findLeaf(int k) const {
        Node* cur = root_;
        while (cur && !cur->leaf) {
            int i = 0;
            while (i < static_cast<int>(cur->keys.size()) && k >= cur->keys[i]) ++i;
            cur = cur->children[i];
        }
        return cur;
    }

public:
    BPlusTree() = default;
    ~BPlusTree() { destroy(root_); }
    BPlusTree(const BPlusTree&) = delete;
    BPlusTree& operator=(const BPlusTree&) = delete;

    void insert(int k) {
        if (!root_) {
            root_ = new Node(true);
            root_->keys.push_back(k);
            return;
        }
        SplitResult s = insertRec(root_, k);
        if (s.split) {
            Node* nr = new Node(false);
            nr->keys.push_back(s.sep);
            nr->children.push_back(root_);
            nr->children.push_back(s.right);
            root_ = nr;
        }
    }

    bool contains(int k) const {
        Node* leaf = findLeaf(k);
        return leaf && std::binary_search(leaf->keys.begin(), leaf->keys.end(), k);
    }

    std::vector<int> range(int a, int b) const {
        std::vector<int> out;
        Node* leaf = findLeaf(a);
        while (leaf) {
            for (int k : leaf->keys) {
                if (k < a) continue;
                if (k > b) return out;
                out.push_back(k);
            }
            leaf = leaf->next;
        }
        return out;
    }

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

int main() {
    BPlusTree t;
    for (int i = 0; i < 50; ++i) t.insert((i * 37) % 50);   // ключи 0..49 вперемешку
    assert(t.validate());
    for (int x = 0; x < 50; ++x) assert(t.contains(x));
    assert(!t.contains(1000));

    std::vector<int> r = t.range(10, 30);
    std::vector<int> expect;
    for (int x = 10; x <= 30; ++x) expect.push_back(x);
    assert(r == expect);

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

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

  • MAX_KEYS = 3 — учебный порядок; на практике узел заполняют под размер страницы (сотни ключей), тогда высота становится единицами.
  • Разделитель — копия первого ключа правого узла; ключ остаётся и в листе как данные.
  • Верхние уровни обычно держат в памяти; «число операций» здесь считайте чтениями страниц.
  • Удаление реализуется тем же рекурсивным приёмом с перераспределением/слиянием.

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

Операция Число чтений страниц Замечание
Search [math]\displaystyle{ O(\log_B N) }[/math] ровно высота; одинаково для всех ключей
Insert [math]\displaystyle{ O(\log_B N) }[/math] плюс [math]\displaystyle{ O(1) }[/math] записей при расщеплении
Delete [math]\displaystyle{ O(\log_B N) }[/math] перераспределение/слияние за [math]\displaystyle{ O(1) }[/math]
Min / Max [math]\displaystyle{ O(\log_B N) }[/math] спуск к крайнему листу
Range-Scan [math]\displaystyle{ (k) }[/math] [math]\displaystyle{ O(\log_B N + k/B) }[/math] почти линейно по результату
Full scan [math]\displaystyle{ O(N/B) }[/math] последовательный проход по листьям
Память [math]\displaystyle{ O(N) }[/math] узлы = страницы фиксированного размера

Примечание. Оценки даны в обращениях к страницам, а не в сравнениях: именно ввод-вывод определяет стоимость на диске. Из-за большого [math]\displaystyle{ B }[/math] логарифм мал: [math]\displaystyle{ \log_{100} 10^9 \approx 4{,}5 }[/math], поэтому [math]\displaystyle{ h \le 5{,}5 }[/math], то есть не более 5 уровней при фактическом B; при минимальной занятости около 50 худшая оценка даёт до 6 уровней, тогда как [math]\displaystyle{ \log_2 10^9 \approx 30 }[/math]. Поэтому в индексах СУБД B⁺-дерево на порядки выгоднее двоичного дерева поиска.

Зависимость высоты от ветвления показана на рис. 6.

Рис. 6. Высокое ветвление снижает высоту: [math]\displaystyle{ h \le \log_B N + 1 }[/math] вместо [math]\displaystyle{ \log_2 N }[/math]; для [math]\displaystyle{ 10^9 }[/math] ключей это около пяти чтений страниц.

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

Дерево порядка 4 (не более 3 ключей на узел). Вставим [math]\displaystyle{ 10, 20, 30, 40, 50, 60 }[/math] и выполним диапазонный запрос [math]\displaystyle{ [25, 55] }[/math].

Шаг Операция Ключи в листьях (слева направо) Что произошло
1 insert 10 [10] первый лист
2 insert 20 [10, 20] —
3 insert 30 [10, 20, 30] узел заполнен
4 insert 40 [10, 20], [30, 40] расщепление листа; разделитель 30 в корень
5 insert 50 [10, 20], [30, 40, 50] во второй лист
6 insert 60 [10, 20], [30, 40], [50, 60] расщепление; разделитель 50 в корень
7 range 25..55 30, 40, 50 спуск к [10,20], проход по связям: 30, 40, 50

Диапазонный запрос нашёл начало в первом «подходящем» листе и далее просто шёл по списку листьев, собирая 30, 40, 50 (ключи 25 и 55 отсутствуют). validate() подтверждает порядок ключей, согласованность разделителей и одну глубину листьев.

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

Лемма 1 (граница высоты). B⁺-дерево с [math]\displaystyle{ N }[/math] ключами, высотой [math]\displaystyle{ h }[/math] (в уровнях) и ветвлением не менее [math]\displaystyle{ B_0 }[/math] удовлетворяет [math]\displaystyle{ h \le \log_{B_0} N + 1 }[/math].

Доказательство. Все листья находятся на уровне [math]\displaystyle{ h }[/math]; каждый внутренний узел, кроме корня, имеет не менее [math]\displaystyle{ B_0 }[/math] детей, а корень — не менее двух. Поэтому листьев не менее [math]\displaystyle{ 2B_0^{\,h-2} }[/math]. Каждый лист хранит хотя бы один ключ, значит [math]\displaystyle{ N \ge 2B_0^{\,h-2} }[/math], откуда [math]\displaystyle{ h \le \log_{B_0}(N/2) + 2 = \log_{B_0} N + 1 }[/math]. [math]\displaystyle{ \blacksquare }[/math]

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

Доказательство. Расщепление листа делит его на два на той же глубине и поднимает минимальный ключ правого листа как разделитель — это сохраняет порядок и условие разделителей. Расщепление внутреннего узла выносит средний разделитель наверх, а детей делит между двумя узлами на одном уровне; при расщеплении корня новый корень добавляет уровень сразу всем листьям. При дубликате Insert-Rec обновляет запись и возвращает split = false, поэтому структура не меняется. Индукция по высоте доказывает корректность. [math]\displaystyle{ \blacksquare }[/math]

Теорема 3 (корректность диапазонного запроса). Range-Scan(a, b) возвращает в точности ключи множества, лежащие в [math]\displaystyle{ [a, b] }[/math], в возрастающем порядке.

Доказательство. Find-Leaf(a) возвращает лист, в который попадает [math]\displaystyle{ a }[/math]; в нём могут быть ключи меньше [math]\displaystyle{ a }[/math], они пропускаются условием [math]\displaystyle{ k \ge a }[/math]. Ключи листьев возрастают и связаны в порядке, поэтому проход по next перебирает все ключи подряд, а условие [math]\displaystyle{ k \le b }[/math] останавливает на верхней границе. Вместе условия отбирают ровно диапазон. [math]\displaystyle{ \blacksquare }[/math]

Оценка сложности. Поиск и изменение идут по одному пути длиной [math]\displaystyle{ h = O(\log_B N) }[/math], делая [math]\displaystyle{ O(1) }[/math] работы на уровне; расщепления/слияния локальны. Диапазонный запрос добавляет [math]\displaystyle{ O(k/B) }[/math] чтений на выдачу результата. Память — [math]\displaystyle{ O(N) }[/math] страниц.

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

Структура Данные Диапазон Поиск (страниц) Обновление Когда выбирать
B⁺-дерево только в листьях, листья связаны [math]\displaystyle{ O(\log_B N + k/B) }[/math] [math]\displaystyle{ O(\log_B N) }[/math] [math]\displaystyle{ O(\log_B N) }[/math] индексы БД и файловые системы
B-дерево во всех узлах дороже (нет связей) [math]\displaystyle{ O(\log_B N) }[/math] [math]\displaystyle{ O(\log_B N) }[/math] наборы без диапазонов; меньше дублирование
LSM-дерево несколько уровней, слияние быстро на запись дороже на чтение запись [math]\displaystyle{ O(1) }[/math] аморт. write-heavy нагрузки (например, RocksDB, Cassandra)
Хеш-индекс — нет [math]\displaystyle{ O(1) }[/math] [math]\displaystyle{ O(1) }[/math] точечные запросы равенства
КЧ-дерево в узлах (в памяти) [math]\displaystyle{ O(\log n + k) }[/math] [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(\log n) }[/math] данные в оперативной памяти

Вердикт. Для диска B⁺-дерево почти всегда выигрывает: высокое ветвление, предсказуемая стоимость, дешёвые диапазоны. Хеш-индекс быстрее для точечных запросов, но не умеет диапазоны; LSM-дерево лучше там, где запись преобладает; деревья «в памяти» (КЧ, АВЛ) хороши, пока данные целиком помещаются в RAM.

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

  1. Индексы реляционных СУБД. InnoDB (MySQL/MariaDB) хранит таблицу как кластерный B⁺-индекс по первичному ключу; вторичные индексы ссылаются на первичный ключ. Oracle, PostgreSQL и SQLite также используют B-деревья/B⁺-деревья для индексов [2], [6].
  2. Файловые системы. NTFS, XFS, ext4 и Btrfs применяют B-деревья/B⁺-деревья для метаданных и каталогов, извлекая выгоду из высокого ветвления и диапазонных обходов [2], [6].
  3. Ключ-значение хранилища и встраиваемые БД. Berkeley DB, LMDB и подобные используют B⁺-деревья для упорядоченных наборов на диске [6].
  4. Пространственные и многомерные индексы. R-деревья и их варианты развивают идеи B⁺-деревьев для диапазонных запросов по нескольким измерениям [6].
  5. Упорядоченные in-memory индексы. При больших объёмах и страничном подкачивании модель B⁺-дерева применяют и к памяти (например, для батч-запросов и SSDs с блочным доступом) [2].

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

  • 1972. Р. Байер и Э. Маккрейт ввели B-деревья — основу семейства [4].
  • 1970-е. В практике индексов сформировался вариант B⁺-дерева: все данные в листьях, внутренние узлы — разделители, листья связаны. В обзоре Комера (1979) он уже описан как самостоятельный вариант [5].
  • 1979. Д. Комер в обзоре «The Ubiquitous B-Tree» популяризовал терминологию и сравнение вариантов B-деревьев [5].
  • 1980–2000-е. B⁺-деревья стали стандартом индексов СУБД и файловых систем; появились конкурирующие LSM-деревья для записи-ориентированных нагрузок [2], [5], [6].

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

  • Путаница B-дерева и B⁺-дерева. В B-дереве данные и ключи во всех узлах; в B⁺ — только в листьях, а внутренние узлы лишь дублируют разделители.
  • Забыть связать листья. Без ссылок next диапазонный запрос вырождается в повторные спуски и теряет главное преимущество.
  • Неверный разделитель. Разделитель — минимальный ключ правого поддерева; произвольный ключ ломает поиск.
  • Не обновить разделитель при удалении первого ключа листа. Нарушится инвариант «разделитель — копия первого ключа правого поддерева»; поиск может остаться корректным, но каноническая модель будет нарушена.
  • Off-by-one в порядке. Ключей на один меньше, чем детей; при расщеплении средний ключ поднимается, а не остаётся в обоих узлах (для внутреннего).
  • Слишком маленький порядок. Если узел не заполняет страницу, дерево высокое и теряет смысл; порядок подбирают под размер блока.
  • Занятость при удалении. Забытая нижняя граница приводит к «тощим» узлам и росту высоты.
  • Дубликаты. Точечное множество хранит ключ один раз; для мультимножества нужны счётчики или разные записи с одинаковым ключом.
  • Сравнение в листе линейно. При больших узлах используйте бинарный поиск.
  • Кэширование корня. Верхние уровни держат в памяти; не стоит считать каждое сравнение обращением к диску — считайте страницы.

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

  1. Поиск. Реализуйте спуск и поиск в листе; проверьте на больших наборах. Подсказка: бинарный поиск среди разделителей.
  2. Вставка с расщеплением. Реализуйте расщепление листа и внутреннего узла; проверьте инварианты. Подсказка: validate с проверкой одной глубины листьев.
  3. Диапазон. Реализуйте range(a, b) через спуск и связи листьев; проверьте на случайных данных. Подсказка: не спускайтесь от корня для каждого ключа.
  4. Удаление. Реализуйте перераспределение и слияние; проверьте уменьшение высоты. Подсказка: обновляйте разделитель при удалении первого ключа.
  5. Двунаправленные листья. Добавьте prev и реализуйте обход диапазона в убывающем порядке. Подсказка: симметрично обычному.
  6. Оценка ветвления. Для размера страницы 4 КБ и ключа 8 байт посчитайте ветвление и высоту для [math]\displaystyle{ 10^9 }[/math] ключей. Подсказка: [math]\displaystyle{ B \approx 4096/(8+8) }[/math].
  7. Кластерный индекс. Смоделируйте таблицу как B⁺-индекс по ключу и вторичный индекс; сравните число чтений страниц для точечного и диапазонного запроса.
  8. B⁺ против B-дерева. На одном множестве ключей сравните число страниц при поиске и диапазоне. Подсказка: диапазон — сильная сторона B⁺.

Ответы (кратко). 1. Спуск и поиск в листе: [math]\displaystyle{ O(\log_B N) }[/math] страниц, сравнений [math]\displaystyle{ O(\log m\cdot\log_B N) }[/math] при бинарном поиске. 2. Расщепление листа и внутреннего узла: [math]\displaystyle{ O(\log_B N) }[/math] страниц. 3. Диапазон: [math]\displaystyle{ O(\log_B N + k/B) }[/math], без повторных спусков. 4. Удаление: перераспределение/слияние; высота уменьшается при пустом корне или корне с одним ребёнком. 5. Обратный обход симметричен прямому. 6. [math]\displaystyle{ B \approx 256 }[/math], [math]\displaystyle{ h \le \log_{256}10^9+1 \approx 5 }[/math]. 7. Кластерный индекс хранит строки, вторичный — ключ первичного индекса. 8. Поиск у B и B⁺ сопоставим, диапазон у B⁺ дешевле.

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

Источники

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