Красно-чёрное дерево держит баланс за счёт цветов и поворотов. Дерево 2-3-4 добивается того же другим способом — разрешая узлу хранить несколько ключей и иметь несколько потомков. Оно всегда идеально сбалансировано, а его идея напрямую ведёт к B-деревьям, на которых стоят индексы почти всех баз данных.

Узел с несколькими ключами

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

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

Всегда сбалансировано благодаря разбиению

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

При вставке мы спускаемся к листу и по пути разбиваем каждый полный узел (тот, где уже три ключа): средний ключ поднимается в родителя, а оставшиеся два ключа расходятся в два отдельных узла. Разбивая полные узлы заранее, на спуске, мы гарантируем, что всегда есть место для нового ключа, и что дерево при необходимости подрастает от корня вверх — а значит, все ветви остаются одной длины. Никаких поворотов не нужно.

Поскольку дерево всегда сбалансировано, поиск, вставка и удаление стоят O(log N) при любом порядке данных.

Родство с красно-чёрными деревьями

Интересный факт: дерево 2-3-4 и красно-чёрное дерево — это, по сути, две записи одной идеи. Любое дерево 2-3-4 можно механически превратить в красно-чёрное и обратно: узел с несколькими ключами разворачивается в маленькую группу красных и чёрных узлов. Операции разбиения соответствуют перекраскам и поворотам. Поэтому по эффективности они эквивалентны, а выбор между ними — вопрос удобства реализации.

B-деревья: 2-3-4 для диска

А теперь главное практическое продолжение. Если узлу разрешить не три ключа, а сотни или тысячи, получится B-дерево. Зачем так много? Из-за того, как устроено внешнее хранение — работа с диском.

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

Именно поэтому индексы в базах данных и файловых системах — это B-деревья (точнее, их вариант B+). Когда вы создаёте индекс в PostgreSQL, под капотом строится B-дерево; быстрый поиск по индексу — это спуск по нему за считанные обращения к диску. Так теория 2-3-4 из учебника оказывается тем, что каждый день ускоряет реальные запросы.

Коротко

  • В дереве 2-3-4 узел хранит до 3 ключей и до 4 потомков; поиск — многопутевой спуск.
  • Дерево всегда идеально сбалансировано благодаря разбиению полных узлов на спуске: оно растёт от корня вверх, все листья на одном уровне. Отсюда гарантированный O(log N).
  • Дерево 2-3-4 эквивалентно красно-чёрному — это две формы одной идеи.
  • Увеличив число ключей в узле до размера дискового блока, получаем B-дерево — основу индексов баз данных и файловых систем, где цель — минимум обращений к диску.

Дальше — хеш-таблицы: структура, которая ищет ещё быстрее деревьев — за O(1), — но ценой потери порядка.