2-3-4-дерево

TL;DR

2-3-4 дерево (2-3-4 tree) — сбалансированное дерево поиска, в котором у каждого внутреннего узла два, три или четыре ребёнка и соответственно 1, 2 или 3 ключа, а все листья лежат на одной глубине. Это B-дерево минимальной степени [math]\displaystyle{ t = 2 }[/math] и прямое обобщение 2-3 дерева. Вставка добавляет ключ и при переполнении 4-узла (третий ключ уже есть, добавляется четвёртый) расщепляет его: медиана (третий ключ) поднимается в родителя, крайние образуют два узла. Главная причина популярности 2-3-4 дерева — изоморфизм красно-чёрному дереву: 2-узел кодируется чёрным узлом, 3-узел — чёрным с одним красным ребёнком, 4-узел — чёрным с двумя красными детьми. Поэтому все операции выполняются за [math]\displaystyle{ O(\log n) }[/math], а высота не превосходит [math]\displaystyle{ \log_2(n+1) }[/math] — как у красно-чёрного дерева.

Свойство	Значение
Класс	Сбалансированное многопутевое дерево поиска; B-дерево степени [math]\displaystyle{ t=2 }[/math]
Изобретение	Обобщение B-дерева (Байер и Маккрейт, 1972 [4]); связь с КЧ-деревом — Гийба и Седжвик, 1978 [5]
Типы узлов	2-узел (1 ключ, 2 ребёнка), 3-узел (2 ключа, 3 ребёнка), 4-узел (3 ключа, 4 ребёнка)
Балансировка	Идеальная: все листья на одной глубине
Высота	[math]\displaystyle{ \le \log_2(n+1) }[/math]
Поиск	[math]\displaystyle{ O(\log n) }[/math]
Вставка / удаление	[math]\displaystyle{ O(\log n) }[/math]; не более [math]\displaystyle{ O(1) }[/math] расщеплений на уровень
Память	[math]\displaystyle{ O(n) }[/math]; узлы хранят 1–3 ключа и 2–4 ссылки
Изоморфизм	Красно-чёрное дерево (3/4-узлы ↔ красные рёбра)
Соответствие	2-3 дерево (только 2/3-узлы), B-дерево, КЧ-дерево
Где встречается	учебный мост к КЧ-деревьям; идеи — в СУБД и файловых системах (через B-деревья)

Определения

2-3-4 дерево — дерево поиска, в котором:

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

2-узел — 1 ключ, 2 ребёнка. 3-узел — 2 ключа, 3 ребёнка. 4-узел — 3 ключа, 4 ребёнка (максимум). Полный узел — 4-узел.

Степень и порядок. 2-3-4 дерево — это B-дерево минимальной степени [math]\displaystyle{ t=2 }[/math] (ключей в узле от [math]\displaystyle{ t-1=1 }[/math] до [math]\displaystyle{ 2t-1=3 }[/math]) или B-дерево порядка [math]\displaystyle{ m=4 }[/math] (детей от 2 до 4).

Высота. [math]\displaystyle{ h }[/math] — число уровней (корень — уровень 1). Каждый внутренний узел имеет не менее двух детей, поэтому на уровне [math]\displaystyle{ i }[/math] не менее [math]\displaystyle{ 2^{i-1} }[/math] узлов, а всего узлов не менее [math]\displaystyle{ 2^h-1 }[/math]. Так как каждый узел хранит хотя бы один ключ, [math]\displaystyle{ n \ge 2^h-1 }[/math], откуда [math]\displaystyle{ h \le \log_2(n+1) }[/math].

Обозначения. [math]\displaystyle{ n }[/math] — число ключей; [math]\displaystyle{ h }[/math] — высота; [math]\displaystyle{ \log }[/math] — двоичный.

Типы узлов показаны на рис. 1.

Рис. 1. Узлы с 1–3 ключами и 2–4 детьми; все листья на одной глубине.

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

2-3 дерево уже даёт идеальную балансировку без полей баланса, но операции над 3-узлами содержат много случаев. 2-3-4 дерево добавляет 4-узлы — и это упрощает картину: 4-узел можно расщепить на два 2-узла одним действием. Более того, разрешив узлам временно «переполняться» до 4 ключей, можно делать вставку сверху вниз: по пути к листу заранее расщеплять все встреченные 4-узлы — тогда вставка всегда попадает в узел, где есть место.

Но главная ценность 2-3-4 дерева — мост к красно-чёрным деревьям. Многоключевой узел можно закодировать двоичными узлами и «красными» рёбрами: тогда:

• 2-узел → один чёрный узел;
• 3-узел → чёрный узел с одним красным ребёнком;
• 4-узел → чёрный узел с двумя красными детьми.

Расщепление 4-узла превращается в перекраску (color flip), а перераспределение ключей — в повороты красно-чёрного дерева. Так «многоключевая» интуиция объясняет, почему красно-чёрное дерево сбалансировано и как работают его операции.

Устройство

Узел 2-3-4 дерева хранит массив ключей (1–3) и массив детей (2–4; у листа пусто). Инварианты:

1. порядок: ключи узла возрастают, поддеревья разделены ими;
2. степень: у внутреннего узла 2–4 ребёнка, значит, 1–3 ключа;
3. одна глубина листьев.

Никаких полей баланса/цвета нет — балансировка следует из формы. Дерево эквивалентно B-дереву степени 2 и красно-чёрному дереву (см. §10).

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

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

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

Алгоритм Search(T, k)
1  cur ← root[T]
2  while cur ≠ NIL
3      i ← 0
4      while i < num[cur] and key[cur][i] < k
5          i ← i + 1
6      if i < num[cur] and key[cur][i] = k
7          return cur
8      if leaf[cur]  return NIL
9      cur ← child[cur][i]

Сложность: O(log n) — не длиннее высоты. Память O(1).

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

Идея. Вставить ключ; при переполнении 4-узла — расщепить его, подняв медиану. Расщепление может подняться вверх; расщепление корня повышает высоту.

Пошаговое описание (снизу вверх).

1. Спуск до листа; вставка ключа по порядку.
2. Если в узле стало 4 ключа (переполнение) — расщепить: медиана уходит в родителя, крайние образуют два узла.
3. Если переполнился родитель — повторить; если расщепился корень — высота +1.

Вариант сверху вниз. Спускаясь, расщеплять каждый встреченный 4-узел до входа в него. Тогда вставка идёт за один проход и не поднимается обратно (это схема Седжвика).

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

Псевдокод (снизу вверх).

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

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

Сложность: O(log n) времени; расщеплений не более высоты.
Корректность: расщепление заменяет 4-узел двумя узлами на той же глубине, сохраняя
порядок; медиана поднимается на уровень выше.

Разбор на примере. Вставка 30 в 4-узел [10|15|20] даёт [10|15|20|30]; медиана 20 поднимается, крайние образуют [10|15] и [30] (рис. 2).

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

Рис. 2. 4-узел переполняется; медиана (третий ключ) поднимается в родителя, крайние образуют два узла.

Схема сверху вниз — на рис. 3.

Рис. 3. Упреждающее расщепление: 4-узлы делятся по пути вниз, вставка — за один проход.

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

Идея. Удалить ключ; чтобы узел «не опустел», по пути вниз следят, что у следующего узла не меньше двух ключей: если меньше — заимствовать у соседа или слить с ним через разделитель родителя. Ключ из внутреннего узла заменяют предшественником/преемником.

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

1. Спускаясь к ключу, на каждом шаге обеспечивать у ребёнка достаточно ключей (≥ 2), иначе заимствование/слияние.
2. Удалить ключ из листа.
3. Если родитель стал недогружен — повторить выше.
4. Если корень остался без ключей — его единственный ребёнок становится новым корнем (высота −1).

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

Сложность: O(log n).

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

Заимствование и слияние — на рис. 4.

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

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

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

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

class TwoThreeFourTree {
    struct Node {
        bool leaf = true;
        std::vector<int> keys;          // 1..3
        std::vector<Node*> ch;          // 2..4 (для внутренних)
        explicit Node(bool l) : leaf(l) {}
    };
    Node* root_ = nullptr;
    struct Split { bool split; int med; Node* right; };

    Split insertRec(Node* n, int k) {
        if (n->leaf) {
            auto it = std::lower_bound(n->keys.begin(), n->keys.end(), k);
            if (it != n->keys.end() && *it == k) return {false, 0, nullptr};   // дубликат
            n->keys.insert(it, k);
            if (static_cast<int>(n->keys.size()) <= 3) return {false, 0, nullptr};
            // переполнение: 4 ключа → медиана (индекс 2) вверх
            Node* right = new Node(true);
            int med = n->keys[2];
            right->keys.assign(n->keys.begin() + 3, n->keys.end());
            n->keys.resize(2);
            return {true, med, right};
        }
        int i = 0;
        while (i < static_cast<int>(n->keys.size()) && k > n->keys[i]) ++i;
        if (i < static_cast<int>(n->keys.size()) && n->keys[i] == k) return {false, 0, nullptr};
        Split s = insertRec(n->ch[i], k);
        if (!s.split) return {false, 0, nullptr};
        n->keys.insert(n->keys.begin() + i, s.med);
        n->ch.insert(n->ch.begin() + i + 1, s.right);
        if (static_cast<int>(n->keys.size()) <= 3) return {false, 0, nullptr};
        // переполнение внутреннего узла
        Node* right = new Node(false);
        int med = n->keys[2];
        right->keys.assign(n->keys.begin() + 3, n->keys.end());
        right->ch.assign(n->ch.begin() + 3, n->ch.end());
        n->keys.resize(2);
        n->ch.resize(3);
        return {true, med, right};
    }

    bool check(const Node* n, int depth, int& leafDepth,
               const int* lo, const int* hi) const {
        int K = static_cast<int>(n->keys.size());
        if (K < 1 || K > 3) return false;                       // 1..3 ключа
        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;   // 2..4 ребёнка
        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], 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:
    TwoThreeFourTree() = default;
    ~TwoThreeFourTree() { destroy(root_); }
    TwoThreeFourTree(const TwoThreeFourTree&) = delete;
    TwoThreeFourTree& operator=(const TwoThreeFourTree&) = delete;

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

    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_, 0, leafDepth, nullptr, nullptr);
    }
};

int main() {
    TwoThreeFourTree t;
    for (int i = 1; i <= 300; ++i) t.insert((i * 37) % 300);
    assert(t.validate());
    for (int x = 0; x < 300; ++x) assert(t.contains(x));
    assert(!t.contains(999));

    TwoThreeFourTree u;
    for (int i = 0; i < 5000; ++i)
        u.insert(static_cast<int>((i * 2654435761u) % 100000));
    assert(u.validate());

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

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

• Узел хранит 1–3 ключа; расщепление срабатывает при четвёртом ключе.
• Медиана — ключ с индексом 2; крайние образуют два узла с сохранением порядка.
• validate проверяет порядок, степени (1–3 ключа, 2–4 ребёнка) и одну глубину листьев.
• Вставка «сверху вниз» (предварительное расщепление) требует иной организации, но даёт один проход.

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

Операция	Худший	Замечание
Search	[math]\displaystyle{ O(\log n) }[/math]	не длиннее высоты
Insert	[math]\displaystyle{ O(\log n) }[/math]	[math]\displaystyle{ O(1) }[/math] расщеплений на уровень
Delete	[math]\displaystyle{ O(\log n) }[/math]	заимствование/слияние за [math]\displaystyle{ O(1) }[/math]
Min / Max	[math]\displaystyle{ O(\log n) }[/math]	спуск к листу
Height	[math]\displaystyle{ h \le \log_2(n+1) }[/math]	идеальная балансировка
Память	[math]\displaystyle{ O(n) }[/math]	1–3 ключа и 2–4 ссылки на узел

Высота и сложность — на рис. 5.

Рис. 5. Высота [math]\displaystyle{ \le \log_2(n+1) }[/math] — как у красно-чёрного дерева; операции логарифмические.

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

Вставим [math]\displaystyle{ 10, 20, 30, 40, 50 }[/math] (расщепления при переполнении 4-узла).

Шаг	Ключ	Действие	Дерево (по возрастанию)
1	10	первый узел	[10]
2	20	—	[10, 20]
3	30	—	[10, 20, 30] (4-узел)
4	40	переполнение → split	корень [30]; дети [10, 20], [40]
5	50	в правый лист	корень [30]; дети [10, 20], [40, 50]

На шаге 4 сработало расщепление: из [10,20,30] при вставке 40 получился узел с 4 ключами (переполнение), медиана 30 поднялась, а 10,20 и 40 разделились; высота выросла на 1. Все листья на одной глубине, validate() подтверждает инварианты.

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

Лемма 1 (граница высоты). 2-3-4 дерево с [math]\displaystyle{ n }[/math] ключами имеет высоту [math]\displaystyle{ h \le \log_2(n+1) }[/math].

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

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

Доказательство. Расщепление 4-узла заменяет узел двумя (или, для корня, добавляет уровень), сохраняя порядок и глубину листьев: медиана поднимается, крайние ключи остаются на прежней глубине. Если родитель переполняется, расщепление повторяется вверх. Индукция по высоте. [math]\displaystyle{ \blacksquare }[/math]

Теорема 3 (изоморфизм красно-чёрному дереву). 2-3-4 дерево взаимно однозначно (по существу) соответствует красно-чёрному дереву: 2-узлы — чёрные, а ключи 3/4-узлов изображаются красными детьми.

Идея доказательства. 2-узел — один чёрный узел. 3-узел — чёрный узел с одним красным ребёнком (ключи слева/справа). 4-узел — чёрный узел с двумя красными детьми. При таком кодировании:

• «чёрная высота» всех путей одинакова (свойство 5 КЧ) — она равна глубине листьев 2-3-4 дерева;
• красные узлы не соседствуют (4-узел даёт максимум двух красных детей одного чёрного родителя) — свойство 4 КЧ;
• расщепление 4-узла соответствует перекраске (color flip), а перераспределение ключей — поворотам.

Обратное кодирование строится сворачиванием красных детей в чёрного родителя. [math]\displaystyle{ \blacksquare }[/math]

Оценка сложности. Высота [math]\displaystyle{ O(\log n) }[/math]; на каждом уровне [math]\displaystyle{ O(1) }[/math] работы (сравнения, расщепление или слияние одного узла) — операции за [math]\displaystyle{ O(\log n) }[/math]. Память — [math]\displaystyle{ O(n) }[/math].

Изоморфизм — на рис. 6.

Рис. 6. 2-узел → чёрный узел; 3-узел → чёрный + один красный; 4-узел → чёрный + два красных. Так 2-3-4 дерево превращается в красно-чёрное.

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

Структура	Ключей в узле	Высота	Изоморфизм	Особенность
2-3-4 дерево	1–3	[math]\displaystyle{ \le \log_2(n+1) }[/math]	красно-чёрное (LLRB)	многоключевые узлы, top-down вставка
2-3 дерево	1–2	[math]\displaystyle{ \le \log_2(n+1) }[/math]	LLRB без 4-узлов	проще узлы, больше случаев
B-дерево	[math]\displaystyle{ t-1..2t-1 }[/math]	[math]\displaystyle{ \le \log_t n }[/math]	—	обобщение на большие [math]\displaystyle{ t }[/math], диск
Красно-чёрное	1 (двоичное)	[math]\displaystyle{ \le 2\log_2(n+1) }[/math]	2-3-4	компактно в памяти, стандарт STL
АВЛ-дерево	1	[math]\displaystyle{ \le 1.44\log_2(n+2) }[/math]	—	строгий баланс, больше поворотов

Вердикт. 2-3-4 дерево — лучший учебный мост от многоключевых деревьев к красно-чёрным: оно объясняет КЧ-балансировку и операции «на пальцах». В памяти чаще реализуют именно КЧ-дерево (компактнее на узел), а на диске — B/B⁺-деревья больших порядков; 2-3-4 дерево ценно как модель.

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

1. Обучение красно-чёрным деревьям. Изоморфизм 2-3-4 → КЧ делает понятными свойства КЧ-дерева и его операции [5].
2. Реализация красно-чёрных деревьев. Лево-ориентированное КЧ-дерево (LLRB) — это кодировка 2-3-4 дерева; 2-3 получается при дополнительном запрете двух красных детей.
3. Символьные таблицы и отображения в памяти. Многоключевые узлы дают хорошую локальность и меньше уровней.
4. Индексы СУБД и файловых систем (через обобщение). B-деревья/B⁺-деревья — прямое развитие идеи многоключевых узлов; 2-3-4 — их простейший случай.
5. Функциональные структуры. Многоключевые деревья применяются в неизменяемых упорядоченных множествах (например, 2-3 finger trees).

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

• 1972. Р. Байер и Э. Маккрейт ввели B-деревья [4]; 2-3-4 дерево — их частный случай ([math]\displaystyle{ t=2 }[/math]).
• 1978. Л. Гийба и Р. Седжвик показали дихроматическую связь многоключевых деревьев и красно-чёрных деревьев [5] — так 2-3-4 дерево стало объяснением КЧ-балансировки.
• 1970-е–1980-е. Схема top-down 2-3-4 (упреждающее расщепление) широко вошла в учебники; Седжвик развил её в лево-ориентированные красно-чёрные деревья (LLRB) в 2008 г.

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

• Путаница с 2-3 деревом. У 2-3-4 есть 4-узлы (3 ключа, 4 ребёнка); у 2-3 — максимум 3 ребёнка.
• Неверное расщепление 4-узла. Медиана поднимается, крайние образуют два узла; неправильный выбор медианы ломает баланс.
• Не попытаться расщепить родителя. Переполнение должно подниматься вверх или расщепляться заранее при спуске.
• Забыть про «перекраску» в КЧ-эквиваленте. Расщепление 4-узла — это color flip + возможный поворот, а не просто перестановка ключей.
• Некорректное удаление. Нужно гарантировать ≥ 2 ключей у следующего узла (заимствование/слияние).
• Потеря «одной глубины» листьев. Расщепление/слияние обязаны сохранять глубину.
• Дубликаты. Обычное 2-3-4 дерево хранит уникальные ключи.
• Рекурсия. Вставка/удаление рекурсивны по высоте [math]\displaystyle{ O(\log n) }[/math] — безопасно.

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

1. Реализация вставки. Реализуйте расщепление 4-узлов; проверьте инварианты на [math]\displaystyle{ 10^5 }[/math] вставках. Подсказка: validate с проверкой одной глубины листьев.
2. Вставка сверху вниз. Реализуйте предварительное расщепление по пути. Подсказка: делить 4-узлы до входа в них.
3. Удаление. Реализуйте заимствование и слияние; проверьте уменьшение высоты. Подсказка: ≥ 2 ключей у следующего узла.
4. Изоморфизм. Закодируйте 2-3-4 дерево красно-чёрным и проверьте свойства КЧ. Подсказка: 3/4-узлы — красные рёбра.
5. Высота. Докажите [math]\displaystyle{ h \le \log_2(n+1) }[/math] и постройте деревья, дающие крайние высоты. Подсказка: все узлы 2-узлы против 4-узлов.
6. Сравнение с 2-3. Реализуйте оба дерева и сравните число операций на одинаковых данных. Подсказка: 4-узлы упрощают вставку.
7. Связь с RB. Покажите, что расщепление 4-узла соответствует color flip в КЧ-дереве. Подсказка: чёрный узел с двумя красными детьми → три чёрных.
8. Параметры. Обобщите до B-дерева степени [math]\displaystyle{ t }[/math] и посмотрите, как меняется высота. Подсказка: [math]\displaystyle{ \log_t n }[/math].

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

• 2-3 дерево — родственная структура без 4-узлов.
• Красно-черное дерево — двоичная кодировка 3/4-узлов.
• B-дерево — обобщение на большие [math]\displaystyle{ t }[/math].
• B+-дерево и B*-дерево — варианты для дисков.
• Асимптотическая сложность — нотация [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. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 3 (сбалансированные деревья поиска, 2-3 деревья, LLRB).
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. Guibas L. J., Sedgewick R. A Dichromatic Framework for Balanced Trees // FOCS. — 1978.
6. Wikipedia: 2–3–4 tree. URL: https://en.wikipedia.org/wiki/2–3–4_tree.