B*-дерево

TL;DR

B*-дерево (B-star tree) — вариант B-дерева, в котором узлы держат повышенную минимальную занятость: не менее двух третей (у обычного B-дерева — не менее половины). Ключевое отличие в поведении при переполнении: прежде чем расщеплять узел, ключи пытаются перераспределить с соседним узлом (redistribute); расщепление делают только тогда, когда оба соседних узла полны, и тогда делят сразу два узла на три (2-to-3 split), поднимая в родителя два разделителя. Это уменьшает число узлов и расщеплений и снижает высоту дерева (гарантия [math]\displaystyle{ h \le \log_{\lceil 2m/3\rceil} N + 1 }[/math] вместо [math]\displaystyle{ \log_{\lceil m/2\rceil} N + 1 }[/math]), но усложняет реализацию: приходится следить сразу за двумя соседями. B*-политику применяют и к B-деревьям, и к B⁺-деревьям.

Свойство	Значение
Класс	Сбалансированное многопутевое дерево поиска; вариант B-дерева
Изобретение	Обобщение B-дерева (Байер и Маккрейт, 1972 [4]); правило 2/3 описано в 1970-е (Кнут, TAOCP) [3]
Минимальная занятость	у внутреннего узла [math]\displaystyle{ \lceil 2m/3 \rceil }[/math] детей, у листа [math]\displaystyle{ \lceil 2m/3 \rceil-1 }[/math] ключей (у B-дерева — [math]\displaystyle{ \lceil m/2 \rceil }[/math] детей)
Переполнение узла	Сначала redistribute к соседу; иначе 2-to-3 split
Высота	[math]\displaystyle{ h \le \log_{\lceil 2m/3\rceil} N + 1 }[/math] (ниже, чем у B-дерева)
Поиск	[math]\displaystyle{ O(\log_B N) }[/math]
Вставка / удаление	[math]\displaystyle{ O(\log_B N) }[/math]; расщеплений меньше, чем у B-дерева
Память	[math]\displaystyle{ O(N) }[/math]; узлы заполнены плотнее → меньше страниц
Варианты	B*-дерево на основе B-дерева и B⁺-дерева
Где встречается	системы, где важны плотность хранения и редкие расщепления; учебные и СУБД/ФС-реализации

Определения

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

1. занятость: у внутреннего узла, кроме корня, не менее [math]\displaystyle{ \lceil 2m/3 \rceil }[/math] детей; у листа — не менее [math]\displaystyle{ \lceil 2m/3 \rceil-1 }[/math] ключей (то есть узел заполнен примерно на две трети);
2. перераспределение: при переполнении узла ключи сначала пытаются перенести в соседний узел (redistribute / shift) через разделитель родителя;
3. расщепление два-в-три (2-to-3 split): если оба соседних узла полны, два узла вместе с разделителем родителя собирают в один упорядоченный набор и делят на три узла, поднимая в родителя два разделителя.

Занятость (occupancy) — доля заполненных ключей в узле от максимума. Разделитель — ключ внутреннего узла, разделяющий диапазоны соседних поддеревьев.

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

Высота. [math]\displaystyle{ h }[/math] — число уровней (корень — уровень 1). При [math]\displaystyle{ b = \lceil 2m/3 \rceil }[/math] и [math]\displaystyle{ N }[/math] ключах [math]\displaystyle{ h \le \log_b N + 1 }[/math]: листьев не менее [math]\displaystyle{ 2b^{h-2} }[/math], а ключей — не менее [math]\displaystyle{ b^{h-1} }[/math] (каждый лист хранит не менее [math]\displaystyle{ b-1 }[/math] ключей).

Сравнение занятости показано на рис. 1.

Рис. 1. B-дерево держит узел заполненным минимум на половину, B*-дерево — минимум на две трети. Плотнее узлы → меньше страниц и ниже дерево.

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

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

Лишь когда соседи тоже полны, расщепление неизбежно — но тогда его выгодно сделать сразу двух узлов в три: собрав два полных узла и разделитель, получаем почти два «полных эквивалента» ключей, которые делятся на три узла примерно по [math]\displaystyle{ \tfrac23 m }[/math] ключей каждый. Это и удерживает занятость на уровне двух третей.

Интуиция выгоды: больше ключей на страницу → меньше страниц на тот же объём → меньше высота → меньше обращений к диску. Плата — усложнение: вставка и удаление должны смотреть на двух соседей и уметь сдвигать ключи через родителя.

Устройство

Узел B*-дерева устроен так же, как у B-дерева (или B⁺-дерева): массив ключей и массив детей (или, в B⁺-варианте, ключи и записи в листьях). Отличие — в политике заполнения и в операциях:

• Порог занятости: не менее [math]\displaystyle{ \lceil 2m/3 \rceil }[/math] детей у каждого некорневого узла.
• Redistribute: при переполнении — сдвиг ключей между соседями через разделитель.
• 2-to-3 split: при полных соседях — деление двух узлов на три с двумя разделителями вверх.

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

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

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

Поиск не отличается от B-дерева: спуск от корня по разделителям до листа (или до узла с ключом в B-варианте).

Алгоритм Search(T, k)
1  cur ← root[T]
2  while не найден в key[cur] и cur не лист
3      i ← выбрать ребёнка по разделителям
4      cur ← child[cur][i]
5  return найден ли key[cur]

Сложность: O(log_B N) чтений страниц (h = O(log_{⌈2m/3⌉} N)).

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

Идея. Вставить ключ; при переполнении — сначала перераспределить с соседом, иначе выполнить 2-to-3 split; при переполнении родителя — повторить.

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

1. Спуск до листа; вставка ключа (при дубликате — обновление).
2. Пока узел переполнен:
   • если левый сосед имеет свободное место — сдвинуть к нему ключ через разделитель;
   • иначе если правый сосед имеет место — сдвинуть вправо;
   • иначе (оба соседа полны) — 2-to-3 split: объединить узел, соседа и разделитель, разделить на три узла, поднять два разделителя в родителя; перейти к родителю.
3. Если переполнился корень — разделить его (высота +1).

Инвариант. Листья на одной глубине, порядок и разделители согласованы; занятость узлов не ниже двух третей (кроме корня).

Псевдокод.

Алгоритм Insert(T, k)
1  вставить k в соответствующий лист
2  node ← лист
3  while numKeys[node] > m − 1                     # переполнение
4      if node = root[T]
5          Split-Root(T)                         # высота +1
6          return
7      p ← parent[node];  i ← позиция node среди детей p
8      if есть левый сосед и в нём есть место
9          Redistribute-Left(node, p, i)        # ключи «перетекают» влево
10     else if есть правый сосед и в нём есть место
11         Redistribute-Right(node, p, i)       # ключи «перетекают» вправо
12     else
13         if i > 0 then Split-2-to-3(p, i − 1) else Split-2-to-3(p, i)   # два узла → три
14         node ← p                              # переполнение поднялось

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

Разбор на примере. Узел [50 | 60 | 70 | 80 | 90] переполняется; у левого соседа [10 | 20 | 30] есть место → разделитель 40 уходит влево, а 50 поднимается в родителя; сосед становится [10 | 20 | 30 | 40], узел — [60 | 70 | 80 | 90] (рис. 2). Если сосед полон, а текущий узел переполнен, например [10 | 20 | 25 | 30 | 40] и [60 | 70 | 80 | 90] с разделителем 50, то после 2-to-3 split получаются [10 | 20 | 25], [40 | 50 | 60], [80 | 90], а разделители 30 и 70 уходят вверх (рис. 3). При малом [math]\displaystyle{ m }[/math] один из трёх узлов может получить меньше двух третей — это особенность малого порядка, а не ошибка split.

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

Рис. 2. При свободном соседе ключи «перетекают» через разделитель родителя; расщепления нет.

Рис. 3. При полных соседях два узла и разделитель делятся на три, поднимая два разделителя.

Схема вставки — на рис. 4.

Рис. 4. Вставка: переполнение → redistribute или 2-to-3 split → при необходимости подъём к родителю.

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

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

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

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

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

Алгоритм Delete(T, k)
1  найти и удалить k (при необходимости — через предшественника/преемника)
2  L ← затронутый узел
3  while L недогружен (занятость < ⌈2m/3⌉) и L ≠ root[T]
4      if у соседа есть запас
5          перераспределить;  обновить разделитель;  break
6      else
7          слить L с соседом;  убрать разделитель из родителя
8          L ← parent[L]
9  скорректировать корень (пустой корень → его ребёнок; высота −1)

Сложность: O(log_B N); перераспределение/слияние — O(1).

Крайние случаи. Удаление первого ключа требует обновления разделителя. Пустой корень заменяется ребёнком.

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

Учебная реализация B*-дерева (ключи-целые, без связанных данных) с политикой redistribute → 2-to-3 split, поиском и проверкой структурных инвариантов validate (одна глубина листьев, порядок, согласованность разделителей, отсутствие пустых некорневых узлов).

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

class BStarTree {
    static constexpr int MAXK = 3;      // максимум ключей в узле (порядок 4)
    static constexpr int MINK = 2;      // целевая минимальная занятость (≈ 2/3)

    struct Node {
        bool leaf = true;
        std::vector<int> keys;
        std::vector<Node*> ch;          // дети (для внутренних узлов)
        Node* parent = nullptr;
    };

    Node* root_ = nullptr;

    static int indexOfChild(Node* p, Node* c) {
        for (int i = 0; i < static_cast<int>(p->ch.size()); ++i)
            if (p->ch[i] == c) return i;
        return -1;
    }

    void splitRoot() {                  // расщепление корня на два уровня
        Node* old = root_;
        Node* right = new Node();
        right->leaf = old->leaf;
        int mid = static_cast<int>(old->keys.size()) / 2;
        int sep = old->keys[mid];
        right->keys.assign(old->keys.begin() + mid + 1, old->keys.end());
        old->keys.resize(mid);
        if (!old->leaf) {
            right->ch.assign(old->ch.begin() + mid + 1, old->ch.end());
            old->ch.resize(mid + 1);
            for (Node* c : right->ch) c->parent = right;
        }
        Node* nr = new Node();
        nr->leaf = false;
        nr->keys = {sep};
        nr->ch = {old, right};
        old->parent = nr;
        right->parent = nr;
        root_ = nr;
    }

    void redistributeLeft(Node* node, Node* p, int idx) {   // сдвиг в левого соседа
        Node* sib = p->ch[idx - 1];
        while (static_cast<int>(node->keys.size()) > MAXK &&
               static_cast<int>(sib->keys.size()) < MAXK) {
            sib->keys.push_back(p->keys[idx - 1]);
            p->keys[idx - 1] = node->keys.front();
            node->keys.erase(node->keys.begin());
            if (!node->leaf) {
                Node* moved = node->ch.front();
                node->ch.erase(node->ch.begin());
                sib->ch.push_back(moved);
                moved->parent = sib;
            }
        }
    }

    void redistributeRight(Node* node, Node* p, int idx) {  // сдвиг в правого соседа
        Node* sib = p->ch[idx + 1];
        while (static_cast<int>(node->keys.size()) > MAXK &&
               static_cast<int>(sib->keys.size()) < MAXK) {
            sib->keys.insert(sib->keys.begin(), p->keys[idx]);
            p->keys[idx] = node->keys.back();
            node->keys.pop_back();
            if (!node->leaf) {
                Node* moved = node->ch.back();
                node->ch.pop_back();
                sib->ch.insert(sib->ch.begin(), moved);
                moved->parent = sib;
            }
        }
    }

    // два соседних ребёнка p->ch[i], p->ch[i+1] и разделитель p->keys[i] → три узла
    void split2to3(Node* p, int i) {
        Node* a = p->ch[i];
        Node* b = p->ch[i + 1];
        std::vector<int> all;
        all.insert(all.end(), a->keys.begin(), a->keys.end());
        all.push_back(p->keys[i]);
        all.insert(all.end(), b->keys.begin(), b->keys.end());

        std::vector<Node*> kids;
        if (!a->leaf) {
            kids.insert(kids.end(), a->ch.begin(), a->ch.end());
            kids.insert(kids.end(), b->ch.begin(), b->ch.end());
        }
        int T = static_cast<int>(all.size());
        int inner = T - 2, base = inner / 3, rem = inner % 3;
        int s1 = base + (rem > 0 ? 1 : 0);
        int s2 = base + (rem > 1 ? 1 : 0);

        std::vector<int> g1(all.begin(), all.begin() + s1);
        int sep1 = all[s1];
        std::vector<int> g2(all.begin() + s1 + 1, all.begin() + s1 + 1 + s2);
        int sep2 = all[s1 + 1 + s2];
        std::vector<int> g3(all.begin() + s1 + 1 + s2 + 1, all.end());

        Node* mid = new Node();
        mid->leaf = a->leaf;
        a->keys = g1;
        mid->keys = g2;
        b->keys = g3;
        if (!a->leaf) {
            a->ch.assign(kids.begin(), kids.begin() + s1 + 1);
            mid->ch.assign(kids.begin() + s1 + 1, kids.begin() + s1 + 1 + s2 + 1);
            b->ch.assign(kids.begin() + s1 + 1 + s2 + 1, kids.end());
            for (Node* c : a->ch) c->parent = a;
            for (Node* c : mid->ch) c->parent = mid;
            for (Node* c : b->ch) c->parent = b;
        }
        mid->parent = p;
        p->keys[i] = sep1;
        p->keys.insert(p->keys.begin() + i + 1, sep2);
        p->ch.insert(p->ch.begin() + i + 1, mid);
    }

    void fix(Node* node) {
        while (static_cast<int>(node->keys.size()) > MAXK) {
            if (node == root_) { splitRoot(); return; }
            Node* p = node->parent;
            int idx = indexOfChild(p, node);
            if (idx > 0 && static_cast<int>(p->ch[idx - 1]->keys.size()) < MAXK) {
                redistributeLeft(node, p, idx);
                continue;
            }
            if (idx + 1 < static_cast<int>(p->ch.size()) &&
                static_cast<int>(p->ch[idx + 1]->keys.size()) < MAXK) {
                redistributeRight(node, p, idx);
                continue;
            }
            if (idx > 0) split2to3(p, idx - 1);
            else         split2to3(p, idx);
            node = p;                       // переполнение поднялось к родителю
        }
    }

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

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

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

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

    void insert(int k) {
        if (!root_) { root_ = new Node(); root_->keys = {k}; return; }
        Node* cur = root_;
        while (!cur->leaf) {
            int i = 0;
            while (i < static_cast<int>(cur->keys.size()) && k > cur->keys[i]) ++i;
            cur = cur->ch[i];
        }
        auto it = std::lower_bound(cur->keys.begin(), cur->keys.end(), k);
        if (it != cur->keys.end() && *it == k) return;      // без дубликатов
        cur->keys.insert(it, k);
        fix(cur);
    }

    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;
    }

    int minOccupancy() const {          // минимальное число ключей среди некорневых узлов
        int m = MAXK;
        walk(root_, true, m);
        return m;
    }
    bool validate() const {
        if (!root_) return true;
        int leafDepth = -1;
        return check(root_, 0, leafDepth);
    }

private:
    void walk(const Node* n, bool isRoot, int& m) const {
        if (!n) return;
        if (!isRoot && static_cast<int>(n->keys.size()) < m) m = static_cast<int>(n->keys.size());
        for (const Node* c : n->ch) walk(c, false, m);
    }
};

int main() {
    BStarTree t;
    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));

    BStarTree u;                        // много вставок с redistribute и 2-to-3 split
    std::vector<int> v;
    for (int i = 0; i < 5000; ++i) {
        int x = static_cast<int>((i * 2654435761u) % 100000);
        u.insert(x);
        v.push_back(x);
    }
    assert(u.validate());
    std::sort(v.begin(), v.end());
    v.erase(std::unique(v.begin(), v.end()), v.end());
    for (int x : v) assert(u.contains(x));

    std::cout << "ok, min keys (non-root) = " << u.minOccupancy() << "\n";
    return 0;
}

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

• Порядок выбран учебным (MAXK = 3); на практике узел заполняют под размер страницы, тогда целевая занятость 2/3 даёт заметный выигрыш по высоте и числу страниц.
• При малом порядке после 2-to-3 split отдельный узел может получить всего один ключ — гарантия двух третей устойчиво проявляется при больших [math]\displaystyle{ m }[/math].
• validate проверяет структурные инварианты (одна глубина, порядок, число детей, отсутствие пустых некорневых узлов); minOccupancy показывает фактическую минимальную занятость.
• Удаление реализуется тем же приёмом с перераспределением/слиянием при недостаче.

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

Операция	Худший	Замечание
Search	[math]\displaystyle{ O(\log_B N) }[/math]	спуск по разделителям
Insert	[math]\displaystyle{ O(\log_B N) }[/math]	redistribute / 2-to-3 split; меньше расщеплений, чем у B-дерева
Delete	[math]\displaystyle{ O(\log_B N) }[/math]	перераспределение/слияние
Min / Max	[math]\displaystyle{ O(\log_B N) }[/math]	спуск к крайнему листу
Память	[math]\displaystyle{ O(N) }[/math]	узлы заполнены не менее чем на две трети (кроме корня)

Примечание. Высота B*-дерева ограничена [math]\displaystyle{ h \le \log_{\lceil 2m/3\rceil} N + 1 }[/math] против [math]\displaystyle{ \log_{\lceil m/2\rceil} N + 1 }[/math] у B-дерева: при [math]\displaystyle{ m = 8 }[/math] это [math]\displaystyle{ \log_6 N + 1 }[/math] против [math]\displaystyle{ \log_4 N + 1 }[/math]. Меньшая высота и плотные узлы сокращают число чтений страниц; ценой становится более сложная вставка и удаление.

Зависимость высоты от занятости — на рис. 5.

Рис. 5. Гарантированная занятость 2/3 против 1/2 снижает высоту (например, [math]\displaystyle{ \log_6 N+1 }[/math] против [math]\displaystyle{ \log_4 N+1 }[/math] при [math]\displaystyle{ m=8 }[/math]).

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

Порядок 5 (до 4 ключей на узел). Начнём с дерева из двух листьев и выполним вставки, вызывающие сначала redistribute, затем 2-to-3 split.

Шаг	Операция	Состояние (ключи листьев слева направо)	Что произошло
0	старт	[10, 20, 30], [50, 60, 70, 80]	разделитель 40; левый лист на минимуме
1	insert 90	[10, 20, 30], [50, 60, 70, 80, 90]	правый лист переполнен
2	redistribute	[10, 20, 30, 40], [60, 70, 80, 90]	40 ушёл влево, 50 поднялся в родителя; слева есть место (рис. 2)
3	insert 25	[10, 20, 25, 30, 40], [60, 70, 80, 90]	левый лист переполнен, правый полон
4	2-to-3 split	[10, 20, 25], [40, 50, 60], [80, 90]	разделители 30 и 70 подняты в родителя

На шаге 2 сработал redistribute (расщепления не было), на шаге 4 — 2-to-3 split: два полных узла и разделитель 50 превратились в три узла, а в родителя ушли два ключа. При [math]\displaystyle{ m=5 }[/math] правый узел получает 2 ключа — это следствие малого порядка; при больших [math]\displaystyle{ m }[/math] доли близки к двум третям. validate() подтверждает одну глубину листьев и согласованность разделителей.

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

Лемма 1 (граница высоты). Если каждый внутренний некорневой узел имеет не менее [math]\displaystyle{ b = \lceil 2m/3 \rceil }[/math] детей, корень — не менее двух, а каждый лист — не менее [math]\displaystyle{ b-1 }[/math] ключей, то высота [math]\displaystyle{ h }[/math] (в уровнях) удовлетворяет [math]\displaystyle{ h \le \log_b N + 1 }[/math].

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

Теорема 2 (корректность вставки). После Insert дерево остаётся корректным B*-деревом.

Доказательство. Redistribute переносит ключ из переполненного узла в соседа через разделитель родителя: порядок сохраняется, а суммарное число ключей в двух узлах и родителе не меняется, поэтому переполнение устраняется без роста дерева. 2-to-3 split объединяет два узла и разделитель, упорядочивает [math]\displaystyle{ T }[/math] ключей и делит их на три группы с двумя разделителями: дети распределяются между тремя узлами в прежнем порядке, глубина листьев не меняется, разделители согласованы. Родитель получает на один ключ больше; если он переполнится, процедура повторяется вверх. Расщепление корня добавляет уровень сразу всем листьям. Индукция по высоте завершает доказательство. [math]\displaystyle{ \blacksquare }[/math]

Оценка сложности. Каждая вставка/удаление проходит путь высотой [math]\displaystyle{ O(\log_b N) }[/math], выполняя на уровне [math]\displaystyle{ O(1) }[/math] работы (сдвиг или раскол локальны). Число расщеплений меньше, чем у B-дерева, так как узлы заполняются плотнее. Память — [math]\displaystyle{ O(N) }[/math] страниц.

Оценка занятости. Для B-варианта при 2-to-3 split объединяются два полных узла и разделитель, то есть [math]\displaystyle{ T = 2(m-1)+1 = 2m-1 }[/math] ключей; для B⁺-листьев — [math]\displaystyle{ 2(m-1) }[/math] ключей, а два разделителя являются копиями. Три группы получают около [math]\displaystyle{ T/3 }[/math] ключей; поэтому узлы B*-дерева в среднем плотнее, чем у B-дерева. Точная гарантия 2/3 — свойство политики redistribute-then-2-to-3 при достаточно большом [math]\displaystyle{ m }[/math].

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

Критерий	B-дерево	B⁺-дерево	B*-дерево
Минимальная занятость	1/2	1/2 (листья)	2/3
Где данные	во всех узлах	только в листьях	во всех узлах (или в листьях для B⁺-варианта)
Диапазонный обход	дороже	быстрый (связи листьев)	дороже
Расщепление	1 → 2	1 → 2	2 → 3
Число разбиений	больше	больше	меньше
Высота при [math]\displaystyle{ m=8 }[/math]	[math]\displaystyle{ \le \log_4 N+1 }[/math]	[math]\displaystyle{ \le \log_4 N+1 }[/math]	[math]\displaystyle{ \le \log_6 N+1 }[/math]
Сложность реализации	низкая	средняя	высокая

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

Сводное сравнение — на рис. 6.

Рис. 6. B*-дерево отличается повышенной занятостью (2/3) и расщеплением «два-в-три», из-за чего узлы плотнее и разбиений меньше, но реализация сложнее.

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

1. Индексы и хранение с приоритетом плотности. B*-заполнение (2/3) уменьшает число страниц и расщеплений; применяют в системах, где дороги записи страниц и важно компактное хранение.
2. Улучшение B⁺-индексов СУБД. Политику redistribute/2-to-3 добавляют к B⁺-деревьям, чтобы повысить занятость листьев и сократить число разбиений.
3. Файловые системы и метаданные. Плотные узлы уменьшают объём служебных структур; идеи B* используются в реализациях B-деревьев для ФС.
4. Учебные и исследовательские реализации. B*-дерево — естественный следующий шаг после B-дерева и B⁺-дерева, демонстрирующий, как политика заполнения влияет на высоту и число расщеплений.

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

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

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

• Путаница с B⁺-деревом. B* задаёт занятость и способ расщепления; B⁺ — где лежат данные. Их можно совместить.
• Расщеплять раньше времени. Сначала нужно попробовать redistribute с соседом; расщепление — только когда оба соседа полны.
• Неверный 2-to-3 split. Объединяются два узла и разделитель, делятся на три; в родителя уходят два разделителя — легко забыть второй.
• Потеря детей при делении. Для внутренних узлов дети распределяются ровно по размеру групп (по [math]\displaystyle{ s_i+1 }[/math]); ошибка рвёт порядок.
• Обновление parent. После сдвига и раскола родительские ссылки переназначаются — иначе validate и навигация ломаются.
• Порог занятости при удалении. Граница [math]\displaystyle{ \lceil 2m/3\rceil }[/math] выше, чем у B-дерева; недостача наступает чаще, и удаление обязано её обрабатывать.
• Слишком малый порядок. При малом [math]\displaystyle{ m }[/math] гарантия 2/3 нестабильна; смысл появляется при больших размерах узла.
• Неверный счёт переполнения родителя. 2-to-3 поднимает два разделителя вместо одного старого, поэтому у родителя становится на один ключ больше; нужно продолжить подъём при переполнении.
• Дубликаты. Для множества ключ хранится один раз; для мультимножества нужны счётчики.
• Сравнение «в лоб» с B-деревом. Выигрыш по высоте достигается ценой более сложной и дорогой вставки/удаления — не всегда оправдан.

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

1. Реализация вставки. Реализуйте redistribute и 2-to-3 split; проверьте инварианты на [math]\displaystyle{ 10^5 }[/math] вставках. Подсказка: validate с проверкой одной глубины и числа детей.
2. Занятость. Измерьте минимальную и среднюю занятость узлов B- и B*-дерева при одинаковых данных. Подсказка: сравните minOccupancy.
3. Удаление. Реализуйте перераспределение и слияние при недостаче. Подсказка: порог [math]\displaystyle{ \lceil 2m/3\rceil }[/math].
4. Высота. Постройте деревья, дающие крайние высоты; сравните с оценками [math]\displaystyle{ \log_4 N+1 }[/math] и [math]\displaystyle{ \log_6 N+1 }[/math] при [math]\displaystyle{ m=8 }[/math]. Подсказка: все узлы по 3 ключа против всех по 5.
5. B*-политика на B⁺. Добавьте redistribute/2-to-3 к B⁺-дереву и измерьте занятость листьев. Подсказка: разделители — копии.
6. Число расщеплений. Сравните суммарное число расщеплений у B и B* для [math]\displaystyle{ n=10^6 }[/math]. Подсказка: считайте вызовы split.
7. Большой порядок. Повторите измерение занятости при [math]\displaystyle{ m = 32, 64, 128 }[/math] и покажите сходимость к 2/3. Подсказка: малый [math]\displaystyle{ m }[/math] искажает гарантию.
8. Оценка страниц. Для размера страницы 4 КБ и ключа 8 байт посчитайте высоту B и B* при [math]\displaystyle{ N=10^9 }[/math]. Подсказка: [math]\displaystyle{ B }[/math]-ветвление ≈ 100, минимальные — 50 и 67.

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

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

Источники

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».
3. Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §6.2.4 «Multiway Trees» (варианты B-деревьев, в т. ч. с повышенной занятостью).
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 (варианты B*). URL: https://en.wikipedia.org/wiki/B-tree.