Сбалансированные деревья: AVL, красно-чёрные, B-деревья

Обычное бинарное дерево поиска — прекрасная идея с одним фатальным изъяном: его качество зависит от того, в каком порядке приходят данные. Вставьте в BST последовательность 1, 2, 3, ..., n — и вы получите не дерево, а связный список, у которого поиск стоит O(n). А отсортированный вход — это не экзотика, а самый частый случай в реальной жизни: автоинкрементные ID, временные метки, отсортированный CSV, результат предыдущего запроса.

Сбалансированные деревья решают ровно эту проблему: они добавляют к BST инвариант формы, который поддерживается при каждой модификации и гарантирует высоту Θ(log n) в худшем случае, а не «в среднем при случайных данных». Цена — дополнительное поле в узле и немного работы на вставке/удалении.

Эта статья — про три семейства, которые реально используются: AVL (строгий баланс по высоте), красно-чёрные (слабый баланс через цвет) и B/B+ деревья (широкие узлы для дисков и кешей). Разберём инварианты, докажем оценки высоты, напишем работающий код и посмотрим, где каждое из них живёт в продакшене.

Предполагается, что вы знакомы с асимптотикой и моделью памяти, массивами и обычными BST.

Карта семейства

Все они решают одну задачу — держать высоту логарифмической, — но выбирают разные точки на кривой «строгость баланса ↔ стоимость поддержания».

Что вообще значит «сбалансированное»

Формально: дерево из n узлов сбалансировано, если его высота h = O(log n).

Заметьте, что совершенный баланс (все листья на одном уровне) требовать нельзя: такое дерево существует только при n = 2^k − 1, и поддержание его стоило бы Θ(n) на вставку. Поэтому все практические схемы поддерживают приблизительный баланс — достаточно жёсткий, чтобы дать O(log n), и достаточно свободный, чтобы чиниться за O(log n) или даже O(1) поворотов.

Три типовых способа задать инвариант:

Нижняя граница, от которой никуда не деться: дерево с n узлами и ветвлением B имеет высоту не меньше log_B(n+1) − 1. Для двоичного дерева при n = 10⁶ это 20 уровней; идеал — именно к нему все и стремятся с точностью до константы.

Поворот — единственный примитив, который вам нужен

Все двоичные балансировки построены на одной операции: повороте (rotation). Он меняет локальную форму дерева, сохраняя порядок ключей при симметричном обходе, и стоит O(1) — переставляются ровно три указателя.

Ключевая интуиция: поворот «перевешивает» один уровень высоты с одной стороны на другую. Если левое поддерево на 2 выше правого, правый поворот вокруг корня уменьшит эту разницу. Если перевес «внутренний» (левый ребёнок перевешивает вправо), одного поворота мало — он просто зеркально отразит проблему, поэтому нужен двойной поворот.

def rotate_right(z):
    """Правый поворот вокруг z. Возвращает новый корень поддерева.

    Было:      z            Стало:    y
              / \                    / \
             y   T4                 x   z
            / \                     /\  /\
           x   T3                  T1 T2 T3 T4
          / \
        T1   T2
    Порядок in-order (T1 x T2 y T3 z T4) не меняется — BST-свойство сохраняется.
    """
    y = z.left
    z.left = y.right      # T3 переезжает к z слева
    y.right = z           # z становится правым ребёнком y
    update_height(z)      # ВАЖНО: сначала нижний узел...
    update_height(y)      # ...потом верхний
    return y

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

AVL-деревья: строгий баланс

AVL (Адельсон-Вельский и Ландис, 1962) — исторически первая структура с гарантированным O(log n). Инвариант предельно прост:

Для каждого узла высоты его левого и правого поддеревьев отличаются не более чем на 1.

Величину bf(v) = height(v.left) − height(v.right) называют фактором баланса; допустимые значения — только −1, 0, +1.

Почему высота логарифмическая

Пусть N(h) — минимальное число узлов в AVL-дереве высоты h. Минимальное дерево высоты h состоит из корня и двух поддеревьев высот h−1 и h−2 (иначе инвариант нарушен):

N(0) = 1,  N(1) = 2,  N(h) = 1 + N(h−1) + N(h−2)

Это рекуррента Фибоначчи со сдвигом: N(h) = F(h+3) − 1, где F — числа Фибоначчи. Так как F(k) ≈ φ^k/√5 при φ = (1+√5)/2 ≈ 1.618, получаем

n ≥ N(h) ≈ φ^(h+3)/√5 − 1   ⇒   h ≤ log_φ(n) ≈ 1.4405 · log₂(n + 2) − 0.3277

То есть AVL-дерево не более чем на 44 % выше идеально сбалансированного. Это самая жёсткая практичная гарантия среди двоичных деревьев (у красно-чёрных — 2·log₂ n).

Четыре случая ребалансировки

После вставки идём вверх по пути от нового узла и чиним первый узел с |bf| = 2.

Важнейший факт: при вставке достаточно одного (одинарного или двойного) поворота. После него высота поддерева становится такой же, какой была до вставки, и выше по пути инварианты не ломаются. При удалении это не так: высота может уменьшиться, и чинить приходится вплоть до корня — до O(log n) поворотов.

Реализация AVL на Python

from dataclasses import dataclass, field
from typing import Optional, Any


@dataclass
class Node:
    key: Any
    value: Any = None
    left: Optional["Node"] = None
    right: Optional["Node"] = None
    height: int = 1          # высота листа = 1, высота пустого поддерева = 0


def h(node: Optional[Node]) -> int:
    return node.height if node else 0


def bf(node: Node) -> int:
    return h(node.left) - h(node.right)


def update(node: Node) -> None:
    node.height = 1 + max(h(node.left), h(node.right))


def rotate_right(z: Node) -> Node:
    y = z.left
    z.left = y.right
    y.right = z
    update(z)
    update(y)
    return y


def rotate_left(z: Node) -> Node:
    y = z.right
    z.right = y.left
    y.left = z
    update(z)
    update(y)
    return y


def rebalance(node: Node) -> Node:
    """Приводит узел в баланс, если |bf| == 2. Возвращает новый корень поддерева."""
    update(node)
    balance = bf(node)

    if balance > 1:                       # перевес влево
        if bf(node.left) < 0:             # LR: сначала выпрямляем ребёнка
            node.left = rotate_left(node.left)
        return rotate_right(node)         # LL

    if balance < -1:                      # перевес вправо
        if bf(node.right) > 0:            # RL
            node.right = rotate_right(node.right)
        return rotate_left(node)          # RR

    return node


def insert(node: Optional[Node], key, value=None) -> Node:
    """Вставка. O(log n) времени, O(log n) стека рекурсии."""
    if node is None:
        return Node(key, value)
    if key < node.key:
        node.left = insert(node.left, key, value)
    elif key > node.key:
        node.right = insert(node.right, key, value)
    else:
        node.value = value                # ключ уже есть — обновляем значение
        return node
    return rebalance(node)


def _min_node(node: Node) -> Node:
    while node.left:
        node = node.left
    return node


def delete(node: Optional[Node], key) -> Optional[Node]:
    """Удаление. O(log n); в отличие от вставки, может потребовать O(log n) поворотов."""
    if node is None:
        return None
    if key < node.key:
        node.left = delete(node.left, key)
    elif key > node.key:
        node.right = delete(node.right, key)
    else:
        # узел найден: три классических случая
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left
        # два ребёнка: заменяем на in-order преемника
        succ = _min_node(node.right)
        node.key, node.value = succ.key, succ.value
        node.right = delete(node.right, succ.key)
    return rebalance(node)


def check_avl(node: Optional[Node]) -> int:
    """Проверка инварианта для тестов. Возвращает высоту или бросает AssertionError."""
    if node is None:
        return 0
    lh, rh = check_avl(node.left), check_avl(node.right)
    assert abs(lh - rh) <= 1, f"нарушен баланс в узле {node.key}: {lh} vs {rh}"
    assert node.height == 1 + max(lh, rh), f"неверная высота в узле {node.key}"
    return node.height

Проверка на патологическом входе, который убивает обычный BST:

root = None
for i in range(1, 100_001):          # строго возрастающая последовательность
    root = insert(root, i)
check_avl(root)
print(root.height)                   # 17, а не 100000
# теоретическая граница: 1.4405 * log2(100002) ≈ 23.9

Сложность AVL: поиск, вставка, удаление — O(log n) времени в худшем случае; O(n) памяти; вставка требует ≤ 2 поворотов, удаление — до O(log n) поворотов. Накладные расходы на узел: одно целое поле высоты (обычно достаточно int8, так как высота никогда не превысит ~92 при 64-битных адресах).

Красно-чёрные деревья: слабый баланс, дешёвая починка

Красно-чёрное дерево (Guibas, Sedgewick, 1978 — развитие «симметричных бинарных B-деревьев» Байера, 1972) ослабляет требование: оно допускает более кривую форму, зато чинится меньшим числом операций.

Инварианты:

1. Каждый узел красный или чёрный.
2. Корень чёрный.
3. Все листья (NIL-узлы) чёрные.
4. У красного узла оба ребёнка чёрные (не бывает двух красных подряд).
5. Для любого узла все пути от него до листьев содержат одинаковое число чёрных узлов («чёрная высота»).

Из 4 и 5 сразу следует оценка: самый длинный путь (чередование красных и чёрных) не более чем вдвое длиннее самого короткого (только чёрные), поэтому

h ≤ 2 · log₂(n + 1)

Хуже, чем 1.44·log₂ n у AVL, но всё ещё логарифм.

Интуиция: это 2-3-4 дерево, притворяющееся двоичным

Самое полезное, что можно понять про RB-деревья: красный узел — это не отдельный узел, а “приклеенный” к чёрному родителю ключ. Схлопните каждый красный узел в его родителя — и получите идеально сбалансированное 2-3-4 дерево, у которого все листья ровно на одном уровне.

чёрный узел без красных детей   → узел-2 (1 ключ,  2 ребёнка)
чёрный узел с одним красным     → узел-3 (2 ключа, 3 ребёнка)
чёрный узел с двумя красными    → узел-4 (3 ключа, 4 ребёнка)

«Чёрная высота» — это ровно высота соответствующего 2-3-4 дерева. Перекраска при вставке — это split узла-4. Как только вы это увидели, все «магические случаи» из учебника перестают быть магией. Sedgewick довёл эту идею до предела в left-leaning red-black trees (LLRB, 2008), где код вставки умещается в 15 строк.

Починка после вставки

Новый узел всегда красный (чтобы не сломать инвариант 5 — чёрную высоту). Если родитель чёрный, мы закончили. Если красный — конфликт, и всё зависит от цвета «дяди».

Ключевое наблюдение: случай 1 — это только перекраска, без поворотов, и он может повторяться до O(log n) раз, но каждое повторение стоит O(1) и не двигает указатели. Случаи 2 и 3 завершают процесс не более чем за 2 поворота. Итог: вставка требует ≤ 2 поворотов, удаление — ≤ 3 поворотов, всегда. Именно в этом главное практическое преимущество RB перед AVL: константное число структурных изменений.

Left-leaning red-black: вставка в 15 строк

RED, BLACK = True, False


class RBNode:
    __slots__ = ("key", "value", "left", "right", "color")

    def __init__(self, key, value):
        self.key, self.value = key, value
        self.left = self.right = None
        self.color = RED           # новый узел всегда красный


def is_red(n) -> bool:
    return n is not None and n.color == RED


def rot_left(h):
    x = h.right
    h.right, x.left = x.left, h
    x.color, h.color = h.color, RED
    return x


def rot_right(h):
    x = h.left
    h.left, x.right = x.right, h
    x.color, h.color = h.color, RED
    return x


def flip_colors(h):
    """split узла-4: отдаём «красный» ключ наверх родителю."""
    h.color = RED
    h.left.color = h.right.color = BLACK


def llrb_insert(h, key, value):
    if h is None:
        return RBNode(key, value)

    if key < h.key:
        h.left = llrb_insert(h.left, key, value)
    elif key > h.key:
        h.right = llrb_insert(h.right, key, value)
    else:
        h.value = value

    # три правила, восстанавливающие «левонаклонность» и отсутствие двух красных подряд
    if is_red(h.right) and not is_red(h.left):
        h = rot_left(h)                       # красное ребро справа — выпрямляем
    if is_red(h.left) and is_red(h.left.left):
        h = rot_right(h)                      # два красных подряд слева
    if is_red(h.left) and is_red(h.right):
        flip_colors(h)                        # временный узел-4 → split
    return h


def put(root, key, value):
    root = llrb_insert(root, key, value)
    root.color = BLACK                        # корень всегда чёрный
    return root

Три if в конце — это буквально «поддерживай изоморфизм с 2-3 деревом». Удаление в LLRB заметно сложнее (нужны move_red_left / move_red_right), и это честный аргумент против LLRB в проде: классическая реализация с родительскими указателями (как в Linux rbtree или OpenJDK TreeMap) многословнее, но её удаление предсказуемее и быстрее.

AVL против красно-чёрных: как выбирать

Практический вывод: разница между ними на реальных данных обычно в пределах 10–20 %, и почти всегда её перекрывают эффекты кеша. Если вы выбираете между AVL и RB, значит, вы уже в той зоне, где нужно мерить, а не рассуждать. Если же вы просто пишете код — берите RB (то есть встроенный map/TreeMap вашего языка) и не думайте.

Гораздо важнее другой вопрос: а нужно ли вообще двоичное дерево?

B-деревья: когда единица стоимости — не сравнение, а страница

Двоичные деревья оптимизируют число сравнений. Но на реальном железе сравнение стоит ~1 нс, а промах кеша — ~100 нс, обращение к SSD — ~100 мкс. Спуск по двоичному дереву на 27 уровней при n = 10⁸ — это 27 случайных обращений к памяти, каждое из которых почти наверняка промах кеша. Ужасно.

Идея B-дерева (Bayer, McCreight, 1970 — оригинальная статья): раз минимальная единица чтения всё равно блок (кеш-линия 64 байта, страница 4/8/16 КБ), давайте набьём в один узел столько ключей, сколько влезает в блок.

Определение

B-дерево порядка t (минимальная степень, t ≥ 2):

1. Каждый узел хранит от t−1 до 2t−1 ключей в отсортированном порядке (корень — от 1).
2. Внутренний узел с k ключами имеет ровно k+1 детей.
3. Все листья находятся на одном уровне — это и есть инвариант баланса.
4. Ключи внутри узла разделяют диапазоны детей: все ключи i-го ребёнка лежат между keys[i-1] и keys[i].

Высота дерева с n ключами: h ≤ log_t((n+1)/2). При t = 200 (типично для страницы 16 КБ с 8-байтовым ключом и 8-байтовым указателем) и n = 10⁸ высота равна 3–4.

Обратите внимание: баланс здесь достигается не поворотами, а изменением ширины узлов. Дерево растёт и уменьшается только через корень, поэтому все листья автоматически на одном уровне. Это принципиально более простой в реализации инвариант, чем цвета RB.

Вставка: расщепление полного узла

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

class BTreeNode:
    __slots__ = ("keys", "children", "leaf")

    def __init__(self, leaf: bool):
        self.keys: list = []
        self.children: list["BTreeNode"] = []
        self.leaf = leaf


class BTree:
    def __init__(self, t: int = 64):
        assert t >= 2
        self.t = t                       # минимальная степень
        self.root = BTreeNode(leaf=True)

    def search(self, key, node=None):
        """O(log_t n) обращений к узлам, внутри узла — бинарный поиск O(log t)."""
        node = node or self.root
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and key == node.keys[i]:
            return node, i
        if node.leaf:
            return None
        return self.search(key, node.children[i])

    def _split_child(self, parent: BTreeNode, i: int) -> None:
        """Расщепляет полного ребёнка parent.children[i] на два узла,
        медианный ключ поднимается в parent."""
        t = self.t
        full = parent.children[i]
        new = BTreeNode(leaf=full.leaf)

        median = full.keys[t - 1]                 # ключ, который уедет наверх
        new.keys = full.keys[t:]                  # правая половина
        full.keys = full.keys[: t - 1]            # левая половина
        if not full.leaf:
            new.children = full.children[t:]
            full.children = full.children[:t]

        parent.keys.insert(i, median)
        parent.children.insert(i + 1, new)

    def insert(self, key) -> None:
        root = self.root
        if len(root.keys) == 2 * self.t - 1:      # корень полон — дерево растёт вверх
            new_root = BTreeNode(leaf=False)
            new_root.children.append(root)
            self.root = new_root
            self._split_child(new_root, 0)
            self._insert_non_full(new_root, key)
        else:
            self._insert_non_full(root, key)

    def _insert_non_full(self, node: BTreeNode, key) -> None:
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:  # сдвигаем вправо, как в сортировке вставками
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
            return

        while i >= 0 and key < node.keys[i]:
            i -= 1
        i += 1
        if len(node.children[i].keys) == 2 * self.t - 1:
            self._split_child(node, i)
            if key > node.keys[i]:
                i += 1
        self._insert_non_full(node.children[i], key)

Сложность: поиск и вставка — O(log_t n) обращений к узлам и O(t · log_t n) сравнений (или O(log n) при бинарном поиске внутри узла). Число дисковых операций — O(log_t n), и это та величина, ради которой всё затевалось.

Удаление сложнее вставки: если у ребёнка ровно t−1 ключей, перед спуском нужно либо «занять» ключ у соседа (rotation/redistribution), либо слить два узла в один (merge). Симметрично расщеплению, это делают упреждающе на пути вниз.

B+ деревья: то, что реально в базах

Практически все СУБД используют не B, а B+ дерево:

• все данные (или указатели на строки) лежат только в листьях;
• внутренние узлы содержат лишь разделители-ключи → в узел влезает больше ветвлений;
• листья связаны в двусвязный список → range-scan (WHERE id BETWEEN 100 AND 200, ORDER BY ... LIMIT) идёт последовательным проходом без возврата вверх.

Именно последний пункт делает B+ незаменимым для баз: OLTP-нагрузка — это не только точечные get, но и диапазонные сканы, а диапазонный скан по двоичному дереву или по хеш-таблице невозможен либо катастрофически медленный.

Где это работает прямо сейчас:

• PostgreSQL — B+ дерево (nbtree) с алгоритмом Lehman-Yao для конкурентного доступа; см. README в исходниках.
• MySQL/InnoDB — кластерный индекс: сама таблица физически хранится как B+ дерево по первичному ключу, страница 16 КБ.
• SQLite — B-дерево для таблиц, B+ для индексов.
• Файловые системы — ext4 (htree), XFS, Btrfs, NTFS, APFS.
• In-memory коллекции — std::collections::BTreeMap в Rust, absl::btree_map в C++. Здесь узел подгоняют под кеш-линии (t ≈ 6–32), а не под страницы диска, но идея та же: меньше указателей, лучше локальность, меньше промахов кеша.

Для in-memory нагрузок B-дерево с маленьким t обычно обгоняет RB-дерево в 1.5–3 раза на поиске просто за счёт кеша, при этом расходуя меньше памяти (нет двух указателей и цвета на каждый ключ). Если вам нужна отсортированная map в Rust или C++ — берите B-дерево по умолчанию.

Альтернатива B+ для write-heavy нагрузок — LSM-деревья (RocksDB, Cassandra, ClickHouse): они меняют случайные записи на последовательные, платя за это амплификацией чтения. Подробный обзор компромиссов — в Modern B-Tree Techniques Гётца Грефе, это лучшая существующая работа по теме.

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

Альтернативы, которые стоит знать

Treap — BST по ключу и куча по случайному приоритету. Форма дерева совпадает с формой BST при случайном порядке вставки, поэтому высота O(log n) с высокой вероятностью. Код короче AVL, а split/merge за O(log n) делают treap идеальным для задач вроде «вставить подотрезок в середину массива» — часто это самый быстрый способ решить задачу на соревновании. См. также дерево отрезков.

Skip list — вероятностная многоуровневая структура на связных списках. Проще конкурентизируется (нет поворотов, только CAS на указателях), поэтому применяется в ConcurrentSkipListMap в Java, в memtable RocksDB и в Redis (ZSET). Подробнее — в статье про персистентные и конкурентные структуры.

Splay — не поддерживает никакого инварианта формы, но после каждого обращения поднимает узел в корень. Даёт O(log n) амортизированно и обладает свойством адаптивности: часто запрашиваемые ключи оказываются близко к корню. Плох для конкурентного доступа (чтение мутирует структуру) и для гарантий latency.

Scapegoat — не хранит вообще ничего в узлах: при нарушении weight-баланса полностью перестраивает виновное поддерево за O(размера). Амортизированно O(log n), нулевые накладные расходы на узел.

WAVL (rank-balanced) — гибрид: ведёт себя как AVL при нагрузке только на вставку и как RB при удалениях, гарантируя ≤ 2 поворотов на удаление и высоту ≤ 2·log n. Статья Haeupler, Sen, Tarjan.

Типичные ошибки

1. Не обновить высоту/размер после поворота или обновить в неверном порядке. Классика. Всегда пересчитывайте снизу вверх и покрывайте тестом check_avl.
2. Забыть, что удаление в AVL требует ребалансировки до корня. Многие реализации в интернете чинят только один уровень — дерево тихо деградирует.
3. Реализовать вставку в RB и не осилить удаление. Удаление с «двойной чернотой» — это шесть случаев, и написать его без ошибок с первого раза почти невозможно. Если вам действительно нужно RB-дерево — возьмите готовое.
4. Использовать сбалансированное дерево там, где хватило бы отсортированного массива. Если данные меняются редко, а читаются часто, sorted array + bisect быстрее дерева в разы за счёт локальности и отсутствия указателей.
5. Ждать от дерева производительности хеш-таблицы. O(log n) с промахами кеша против O(1) с одним-двумя обращениями — разница на порядок. Дерево берут ради порядка: range-запросы, floor/ceiling, обход по возрастанию, k-й элемент.
6. Нестабильный компаратор. Ключ, который меняется после вставки, или компаратор, нарушающий строгий слабый порядок (NaN в ключах, сравнение по мутабельному полю), ломает дерево бесшумно: элемент «есть», но не находится.
7. Слишком маленький узел B-дерева. Ради t = 2 смысла нет: вы получите 2-3-4 дерево с накладными расходами массивов. Подбирайте t так, чтобы узел занимал целое число кеш-линий (in-memory) или ровно страницу (на диске).
8. Рекурсия на глубину дерева при недоверенном вводе. Для сбалансированного дерева глубина ≤ 60, это безопасно. Но если вы пишете обычный BST — рекурсивный обход упадёт по стеку на отсортированном входе.

Как выбирать: короткий алгоритм

Мини-итог

• Балансировка нужна не «для красоты», а чтобы убрать зависимость производительности от порядка поступления данных — самая частая причина деградации BST в проде.
• Поворот — единственный примитив двоичных балансировок: O(1), сохраняет in-order.
• AVL держит высоту ≤ 1.44·log₂ n. Быстрее на поиске, дороже на удалении (O(log n) поворотов). Хорош при read-heavy нагрузке.
• Красно-чёрное держит высоту ≤ 2·log₂ n, но чинится за ≤ 2 поворота на вставку и ≤ 3 на удаление. Стандарт де-факто в библиотеках и ядре Linux. Мысленно это 2-3-4 дерево, закодированное двоичными узлами.
• B/B+ деревья меняют оптимизируемую метрику: не число сравнений, а число обращений к блоку. Ветвление B = 100…400 даёт высоту 3–4 на сотнях миллионов записей и делает их основой всех дисковых индексов. In-memory версии с узлом под кеш-линию бьют RB за счёт локальности.
• Практическое правило: нужен порядок — берите готовую отсортированную map; нужен диск или нужны кеш-эффекты — берите B-дерево; нужна конкурентность — смотрите на skip list.

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4-е изд., гл. 13 (Red-Black Trees) и 18 (B-Trees) — mitpress.mit.edu
• Sedgewick, Wayne. Algorithms, 4th ed., гл. 3.3 — algs4.cs.princeton.edu/33balanced
• Sedgewick. Left-Leaning Red-Black Trees (2008) — sedgewick.io
• Bayer, McCreight. Organization and Maintenance of Large Ordered Indices (1972) — doi.org/10.1007/BF00288683
• Comer. The Ubiquitous B-Tree (1979) — dl.acm.org/doi/10.1145/356770.356776
• Guibas, Sedgewick. A Dichromatic Framework for Balanced Trees (1978) — doi.org/10.1109/SFCS.1978.3
• Haeupler, Sen, Tarjan. Rank-Balanced Trees (WAVL, 2015) — dl.acm.org/doi/10.1145/2689412
• Graefe. Modern B-Tree Techniques (2011) — w6113.github.io/files/papers/btreesurvey-graefe.pdf
• Sleator, Tarjan. Self-Adjusting Binary Search Trees (1985) — cs.cmu.edu/~sleator/papers/self-adjusting.pdf
• Linux kernel: Red-black Trees (rbtree) — kernel.org/doc/html/latest/core-api/rbtree.html
• PostgreSQL: nbtree README — github.com/postgres/postgres
• Kleppmann. Designing Data-Intensive Applications, гл. 3 — про B-деревья против LSM

Что дальше

Мы разобрали структуры, которые поддерживают полный порядок ключей. Но огромный класс задач требует меньшего: доступа только к минимуму или максимуму — планировщики, алгоритм Дейкстры, слияние отсортированных потоков, top-k. Для них полный порядок избыточен, и есть структура проще и быстрее дерева, живущая в обычном массиве без единого указателя.

Следующая статья: Кучи и приоритетные очереди.