B-Дерево и B+Tree & B+-Tree

B-дерево порядка (минимальной степени) t хранит в каждом узле от t-1 до 2t-1 ключей (кроме корня, у которого минимум 1) и, если узел не лист, от t до 2t детей — на 1 больше числа ключей, по одному ребёнку между и по краям от каждой пары соседних ключей, как в обычном BST, только "растянутом" по горизонтали. Ключевой структурный инвариант — все листья находятся на одной и той же глубине: дерево растёт не удлинением одной ветки, а расщеплением переполненного узла и подъёмом среднего ключа в родителя, что увеличивает высоту сразу и равномерно по всему дереву, а не локально.A B-tree of order (minimum degree) t stores t-1 to 2t-1 keys per node (except the root, which needs at least 1), and, if the node isn't a leaf, t to 2t children — one more than the key count, one child between and on either side of each pair of adjacent keys, just like an ordinary BST, only "stretched" horizontally. The key structural invariant is every leaf sits at the same depth: the tree grows not by lengthening one branch but by splitting an overflowing node and lifting its middle key into the parent, which increases height instantly and uniformly across the whole tree, not locally.

Вставка ключа спускается от корня, на каждом шаге выбирая ребёнка между двумя ключами, между которыми должен оказаться новый ключ, — но, в отличие от бинарного дерева, если узел на пути уже заполнен (2t-1 ключей), он превентивно расщепляется на два узла по t-1 ключей, а средний (t-й) ключ поднимается в родителя, прежде чем спуск продолжится. Такое "расщепление по пути вниз" гарантирует, что родитель расщепляемого узла никогда сам не окажется переполненным в момент, когда в него нужно что-то вставить, — вся операция выполняется за один проход сверху вниз, без отдельного прохода обратно вверх, как в AVL/RB-деревьях.Inserting a key descends from the root, at each step choosing the child between the two keys the new key should fall between — but, unlike a binary tree, if a node along the path is already full (2t-1 keys), it's preemptively split into two nodes of t-1 keys each, and the middle (t-th) key is lifted into the parent, before the descent continues. This "split on the way down" guarantees that the parent of a node being split is never itself full at the moment something needs to be inserted into it — the whole operation runs in a single top-down pass, with no separate bottom-up pass like in AVL/red-black trees.

struct BNode {
    std::vector<int> keys;              // t-1 .. 2t-1 ключей// t-1 .. 2t-1 keys
    std::vector<BNode*> children;    // пусто, если лист// empty if a leaf
    bool leaf = true;
};

// разбить переполненного ребёнка parent->children[i] на два, поднять средний ключ// split the overflowing child parent->children[i] in two, lift the middle key
void split_child(BNode* parent, int i, int t) {
    BNode* child = parent->children[i];
    BNode* sibling = new BNode{}; sibling->leaf = child->leaf;
    int mid = child->keys[t - 1];
    sibling->keys.assign(child->keys.begin() + t, child->keys.end());
    child->keys.resize(t - 1);
    if (!child->leaf) {
        sibling->children.assign(child->children.begin() + t, child->children.end());
        child->children.resize(t);
    }
    parent->children.insert(parent->children.begin() + i + 1, sibling);
    parent->keys.insert(parent->keys.begin() + i, mid);
}

void insert_nonfull(BNode* node, int key, int t) {
    if (node->leaf) {
        auto pos = std::upper_bound(node->keys.begin(), node->keys.end(), key);
        node->keys.insert(pos, key);
    } else {
        int i = std::upper_bound(node->keys.begin(), node->keys.end(), key) - node->keys.begin();
        if ((int)node->children[i]->keys.size() == 2 * t - 1) {   // расщепить превентивно, до спуска// split preemptively, before descending
            split_child(node, i, t);
            if (key > node->keys[i]) i++;
        }
        insert_nonfull(node->children[i], key, t);
    }
}

Дерево с t=2 (не больше 3 ключей в узле). insert проигрывается автоматически: спуск, и если узел на пути заполнен — расщепление прямо перед спуском в него, подсвеченное отдельным шагом.A tree with t=2 (at most 3 keys per node). insert auto-plays: descend, and if a node on the path is full — a split right before descending into it, highlighted as its own step.

Обычное B-дерево хранит значения (не только ключи) во внутренних узлах — если искомый ключ найден на полпути, поиск завершается раньше. B+Tree меняет это намеренно: значения (или указатели на строки таблицы) хранятся только в листьях, а внутренние узлы содержат исключительно ключи-разделители для навигации, без данных. Это увеличивает fanout внутренних узлов (они компактнее, значит помещают больше ключей на ту же страницу — а значит и высота дерева меньше) и, что более важно на практике, позволяет связать все листья в односвязный список слева направо: последовательный обход диапазона (range scan) — "найти всё между X и Y" — становится линейным проходом по листьям, без единого лишнего обращения к внутренним узлам после первого спуска.A plain B-tree stores values (not just keys) in internal nodes too — if the target key is found halfway down, the search ends early. A B+Tree deliberately changes this: values (or pointers to table rows) live only in the leaves, while internal nodes hold exclusively separator keys for navigation, no data. This increases the fanout of internal nodes (they're more compact, so more keys fit on the same page — hence a shorter tree), and, more importantly in practice, lets all the leaves be linked into a singly linked list left to right: a sequential range scan — "find everything between X and Y" — becomes a linear walk over the leaves, with not a single extra internal-node access after the initial descent.

Это ровно тот компромисс, который нужен базе данных: точечный поиск по ключу всё ещё O(log n), но диапазонный запрос (крайне частый в SQL — BETWEEN, ORDER BY с LIMIT, JOIN по диапазону) на B+Tree — это одно приведение к листу плюс последовательное чтение, а не O(log n) отдельных спусков от корня. Именно поэтому InnoDB (MySQL), PostgreSQL, Oracle и большинство файловых систем с B-tree-подобными индексами (NTFS, ext4's htree, XFS) используют вариант B+, а не классический B-Tree Байера-МакКрейта.This is exactly the trade-off a database needs: a point lookup by key is still O(log n), but a range query (extremely common in SQL — BETWEEN, ORDER BY with LIMIT, a range JOIN) on a B+Tree is one descent to a leaf plus a sequential read, not O(log n) separate descents from the root. This is exactly why InnoDB (MySQL), PostgreSQL, Oracle, and most filesystems with B-tree-like indexes (NTFS, ext4's htree, XFS) use the B+ variant rather than the classic Bayer-McCreight B-Tree.