CS Notes

b-star-tree

3 min read

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

Предпосылки: оценка сложности в O(…), B-дерево — split/merge, инвариант заполнения от 1/2 до полного узла.

После split в B-дереве оба новых узла обычно получаются заполненными примерно наполовину. При t = 128 и индексе на 10 миллионов записей минимальное заполнение 1/2 означает, что в худшем случае индекс может занимать вдвое больше страниц, чем при полном заполнении — сотни мегабайт впустую. При последовательности вставок и удалений узлы могут долго оставаться близко к минимальному заполнению, и значительная часть страниц индекса оказывается наполовину пустой.

Главная идея

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

Вставка

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

Когда узел переполняется, B* дерево проверяет соседний узел (с тем же родителем). Если у соседа есть свободное место, ключи перераспределяются между двумя узлами через родителя:

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

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

До:        [...| 30 |...]
              /     \
    [10|20|25|28]  [35|38|40|45]   ← оба переполнены
 
После:     [...| 25 | 38 |...]
              /    |     \
        [10|20] [28|30|35] [40|45]  ← три узла вместо двух

Удаление

Удаление зеркально вставке. Если узел стал слишком пустым (меньше 2/3), проверяется сосед. Если у соседа есть лишние ключи — перераспределяем (как borrowing в B-дереве). Если соседи тоже на минимуме — merge трёх узлов в два:

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

Сравнение B-дерева, B+ дерева и B* дерева

ХарактеристикаB-деревоB+ деревоB* дерево
Минимальное заполнение1/21/22/3
ДанныеВо всех узлахТолько в листьяхЗависит от варианта
Связь листьевНетСвязный списокЗависит от варианта
Split1 → 2 узла1 → 2 узла2 → 3 узла
Merge2 → 1 узел2 → 1 узел3 → 2 узла
Перераспределение при вставкеНетНетДа (перед split)
Сложность реализацииБазоваяСредняяВысокая

Применение

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

B-дерево и его варианты оптимизируют поиск по ключу целого значения: найти запись, где salary = 50000, или все записи, где salary BETWEEN 40000 AND 60000. Но что если нужно искать внутри составных значений — найти все документы, содержащие слово «ruby», или все строки, где массив тегов содержит элемент «postgresql»? Полный перебор всех записей — O(n). Нужна структура, которая «переворачивает» отношение: от элемента к списку записей, где он встречается. Эту задачу решает инвертированный индекс.

Sources

Sources

Graph View

Backlinks