Конспект: 2-3 деревья и B-деревья

Понятия

2-3 дерево - баланс многоключевыми узлами, без вращений. Узел: 2-УЗЕЛ (1 ключ, 2 ребёнка) или 3-УЗЕЛ (2 ключа, 3 ребёнка); дети - диапазоны между ключами. Все листья ВСЕГДА на одном уровне.

Рост вверх - вставка идёт в ЛИСТ; переполненный узел РАСЩЕПЛЯЕТСЯ, СРЕДНИЙ ключ уходит к родителю; расщепление КОРНЯ надстраивает уровень над всем деревом сразу (все листья опускаются одновременно). Высота ≤ log₂(n+1) без поворотов.

B-дерево - 2-3 дерево, выросшее вширь: узел размером с ДИСКОВЫЙ БЛОК на СОТНИ ключей, ветвление в сотни раз.

Цена на диске - число ЧТЕНИЙ БЛОКОВ (одно чтение в миллионы раз дороже сравнения в памяти), то есть ВЫСОТА. Внутри узла ключи ищут в памяти - почти бесплатно.

Высота B-дерева - ≈ log_b(n): ветвление b в основании логарифма. При b ≈ 200 миллиард ключей = 3-4 уровня = 3-4 чтения диска (у двоичного дерева ~30).

Заём - недобравший узел берёт ключ у соседа через родителя: разделитель вниз, ключ соседа вверх, крайний ребёнок соседа переходит. Слияние - узел + разделитель + сосед в один узел на 2t−2 ключа; родитель теряет ключ.

Что унести

Главная мысль: стоимость операции зависит от уровня памяти (кеш / ОЗУ / диск), и структуру подбирают под неё. Для памяти оптимум - двоичное сбалансированное дерево (АВЛ, красно-чёрное); для диска - широкий узел (B-дерево), потому что там цена - чтения блоков.

2-3 дерево - концептуальный мост: красно-чёрное дерево = 2-3(-4) дерево, закодированное цветом (3-узел = чёрный + красный ребёнок); B-дерево = 2-3 дерево с узлами на сотни ключей. Идея «узел растёт вширь, дерево - вверх целиком, листья ровно» даёт баланс без вращений и минимальную высоту в блоках.

Формула на память: высота = log_b(n), ветвление в основании. Хочешь дерево ниже (меньше чтений диска) - увеличивай ветвление, а не глубину.

Удаление - зеркало вставки. Ключ убирают из листа (внутренний - через предшественника); недобор чинят заёмом, а если занять не у кого - слиянием, которое может дойти до корня. Опустевший корень убирают: дерево ниже целиком, листья по-прежнему на одной глубине.

Ловушки джокера

Вставлять не в лист 2-3 дерева - структура сломается. Вставка всегда в лист, баланс - расщеплением снизу вверх.

Поднимать при расщеплении не средний ключ - диапазоны детей перестанут соответствовать ключам.

Останавливать расщепление на первом узле - оно может пойти цепочкой до корня.

Считать цену на диске в сравнениях - тогда B-дерево кажется «медленным» (сотни сравнений в узле), хотя чтений диска у него в разы меньше. Цена - чтения блоков.

Двоичное дерево для дискового индекса - высота ~30 = ~30 чтений диска. Нужен широкий узел.

Считать высоту B-дерева как log₂ - забыл про ветвление; правильно log_b, оно кратно меньше.

Удалил ключ из внутреннего узла и склеил детей как попало. Детей должно быть на одного больше, чем ключей; удаление идёт через предшественника из листа.

Проверь себя

Как 2-3 дерево балансируется без вращений и почему листья всегда ровны?

Что поднимают наверх при расщеплении и что происходит при расщеплении корня?

Почему узел B-дерева делают размером с блок?

Что считают ценой поиска на диске и почему высота B-дерева всего 3-4 на миллиардах ключей?

Почему для дискового индекса берут B-дерево, а не красно-чёрное?

Когда недобравший узел B-дерева занимает у соседа, а когда сливается с ним, и как при этом уменьшается высота?