CS Notes

b-star-tree

7 min read

B* дерево (B* tree)

Предпосылки: оценка сложности в O(…); B-дерево — узел как страница фиксированного размера; параметр t и инвариант заполнения от t−1 до 2t−1 ключей; split: переполненный узел расщепляется на два, медиана поднимается в родителя как разделитель; merge и заимствование у соседа через родителя при удалении.

← B-дерево

После split в B-дереве узел делится надвое, и каждая половина получается заполненной примерно наполовину. Это и есть нижняя граница: узел остаётся законным, пока в нём не меньше t−1 ключей — почти половина вместимости 2t−1. Половина страницы под узлом может стоять пустой.

Цена этой пустоты видна на масштабе индекса. Узел занимает целую дисковую страницу; если узлы держатся у нижней границы, индекс на 10 миллионов записей занимает почти вдвое больше страниц, чем при плотной упаковке, — лишние сотни мегабайт на диске. И это не редкий случай: при чередующихся вставках и удалениях узлы подолгу остаются у минимума, и заметная часть страниц индекса стоит наполовину пустой.

Плотнее половины

B дерево* поднимает нижнюю границу заполнения узла с 1/2 до 2/3: вместо «не меньше половины» — «не меньше двух третей». Звёздочка (*) обозначает вариант B-дерева с более плотной упаковкой узлов.

Поднять границу нельзя простым декретом: обычный split B-дерева делит один переполненный узел на два по половине — это даёт ровно 1/2, ниже новой цели. Чтобы узлы держались на 2/3, меняются обе операции, которые управляют заполнением: вставка (что делать с переполнением) и удаление (что делать с недозаполнением). Дальше — как именно.

Вставка: сначала поделиться, потом расщеплять

В B-дереве переполненный узел сразу расщепляется на два половинных. B дерево* добавляет шаг раньше split: прежде чем плодить новый полупустой узел, попробовать пристроить лишний ключ к соседу — другому ребёнку того же родителя, стоящему рядом по порядку. Если у соседа есть место, расщепление вообще не нужно.

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

До:        [...| 30 |...]
              /          \
   [10|20|25|28|29]   [35|40]    <- левый переполнен: 5 ключей при вместимости 4, у правого место есть
 
После:     [...| 29 |...]
              /          \
    [10|20|25|28]   [30|35|40]   <- 29 поднялся в родителя, 30 спустился к соседу

Разделителем стал 29 — крайний правый ключ переполненного узла; он поднялся в родителя. Старый разделитель 30 спустился в правый узел и встал перед 35. Порядок сохранён: слева от 29 всё меньше 29, справа — больше, как и требует дерево. Переполнение рассосалось без нового узла.

Если у соседа тоже нет места — он тоже полон, — делиться некому, и тогда выполняется split, но не один-в-два, а два узла в три. В дело идут переполненный узел (в нём на один ключ больше предельного), полный сосед и разделитель между ними — всего 2·(2t−1) + 2 ключа — и раскладываются поровну по трём новым узлам. Каждый получает около 2/3 вместимости — ровно новая нижняя граница. Два ключа-разделителя поднимаются в родителя:

До:        [...| 30 |...]
              /            \
   [10|20|25|28|29]  [35|38|40|45]   <- левый переполнен, сосед полон — делиться некому
 
После:     [...| 28 | 38 |...]
              /     |      \
      [10|20|25] [29|30|35] [40|45]  <- три узла вместо двух

Все ключи обоих узлов плюс разделитель 30 — это 10 20 25 28 29 30 35 38 40 45, десять штук в порядке возрастания. Их режут на три узла двумя ключами-разделителями 28 и 38, и эти двое уходят в родителя. В каждом из трёх узлов оказывается по 2–3 ключа — заметно плотнее, чем оставил бы обычный split B-дерева, который раскидал бы те же ключи по двум полупустым узлам. В этом и смысл правила B*: заполнение держат ближе к 2/3, а не к 1/2.

Удаление: зеркало вставки

Удаление обедняет узел так же, как вставка его переполняет, и чинится теми же двумя ходами в обратную сторону. Если после удаления в узле стало меньше 2/3 — он опустился ниже новой нижней границы. Сначала смотрят на соседа: если у того ключей с запасом, недостающий ключ перетекает через родителя — то же заимствование, что в B-дереве, только порог теперь 2/3, а не 1/2.

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

До:        [...| 20 | 40 |...]
              /    |     \
          [10]  [25|30]  [45]    <- три соседа, все у минимума
 
После:     [...| 30 |...]
              /      \
        [10|20|25]  [40|45]      <- два узла на 2/3, один разделитель

Все ключи трёх узлов плюс оба разделителя 20 и 40 — это 10 20 25 30 40 45, шесть штук. Их раскладывают на два узла одним новым разделителем 30, который поднимается в родителя; второй из старых разделителей лишний и пропадает вместе с третьим узлом. Получаются два узла на 2/3 — узлов стало меньше, плотность держится.

B-дерево, B+ дерево и B* дерево рядом

Таблица сводит три варианта по тем же признакам. B+ дерево — родственный вариант, который хранит данные только в листьях и связывает листья в связный список для диапазонных обходов; здесь оно даёт точку отсчёта по плотности и устройству узлов.

ХарактеристикаB-деревоB+ деревоB* дерево
Минимальное заполнение1/21/22/3
Где лежат данныеВо всех узлахТолько в листьяхВо всех узлах
Связь листьевНетСвязный списокНет
Split при переполнении1 узел → 21 узел → 22 узла → 3
Merge при недозаполнении2 узла → 12 узла → 13 узла → 2
Заимствование у соседа до splitНетНетДа
Сложность реализациибазоваясредняявысокая

Звёздочка ставит акцент на плотности упаковки, а не на том, где лежат данные. Поэтому 2/3-заполнение можно совместить и с раскладкой B+ дерева — получится «B*+ дерево» с данными в листьях и плотными внутренними узлами. В таблице B* показано в простом варианте — с данными во всех узлах, как у B-дерева, — но сам приём плотной упаковки от этого выбора не зависит.

Строка «сложность реализации» суммирует разницу в коде: B* добавляет к обычному split случай заимствования у соседа и расщепление два-в-три (и зеркальное слияние три-в-два) — больше веток и больше операций с родителем на каждую перестройку, чем у B-дерева.

Что это даёт и чем платится

B дерево* поднимает нижнюю границу заполнения с 1/2 до 2/3. Для индекса на 10 миллионов записей это меняет худший случай впустую занятого места: в наполовину пустом узле зря лежит до 1/2 страницы, в узле на 2/3 — до 1/3. Пустой запас на узел падает с 50% до 33% — те самые лишние сотни мегабайт сжимаются до десятков.

Плотнее упакованные узлы выгодны и поиску. Чем больше ключей на странице, тем больше детей у каждого узла, тем меньше узлов нужно на те же 10 миллионов записей — и тем ниже дерево. Каждый уровень дерева — это одно чтение страницы с диска при спуске от корня к листу; дерево на уровень ниже экономит одно дисковое чтение на каждый поиск.

Цена — более дорогие обновления. Там, где B-дерево при переполнении трогает один узел и его родителя, B дерево* сперва читает соседа, а в худшем случае перестраивает три узла вместо двух. Каждая такая перестройка — лишние чтения и записи страниц на операцию вставки или удаления. B* выгодно там, где индекс читают намного чаще, чем меняют: экономия места и чтений окупает дорогую запись.

Sources

← B-дерево

Graph View

Backlinks