Удаление из B-дерева: заём у соседа и слияние узлов

Если ты умеешь удалять ключ из внутреннего узла через предшественника и знаешь, когда узел занимает у соседа, а когда сливается с ним, листай до «Теперь сам».

Как думаешь, что делать с дырой в узле

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

Удаление может сделать узел слишком маленьким. Прежде чем читать дальше, попробуй угадать: если в узле остался 0 ключей при минимуме 1, можно ли просто выбросить узел? Что тогда станет с поддеревьями под ним и с глубиной листьев? И почему нельзя оставить его пустым?

На что это похоже

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

Механизм: предшественник, заём, слияние

удалить k:
1. найти узел с k
   если узел внутренний: заменить k предшественником (самый правый
   ключ в левом поддереве - он всегда в листе) и удалять его из листа
2. убрать ключ из листа
3. пока узел u (не корень) содержит < t−1 ключей:
     ЗАЁМ  - есть сосед с ≥ t ключами:
             разделитель из родителя спускается в u,
             крайний ключ соседа поднимается на его место,
             крайний ребёнок соседа переходит к u
     СЛИЯНИЕ - у соседей ровно по t−1:
             u + разделитель + сосед → один узел
             (t−2) + 1 + (t−1) = 2t−2 ключей - помещается
             родитель потерял ключ → u = родитель, проверить снова
4. корень остался без ключей, но с ребёнком → ребёнок становится корнем

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

Почему все листья остаются на одной глубине: заём и слияние перекладывают ключи и детей между соседями ОДНОГО уровня, а высота уменьшается только убиранием корня - сразу для всех листьев.

Правило

Из B-дерева ключ удаляют из листа (внутренний ключ сначала меняют на предшественника). Узел, в котором стало меньше t−1 ключей, занимает у соседа с ≥ t ключами через родителя: разделитель спускается вниз, ключ соседа поднимается. Если занять не у кого, узел сливается с соседом и разделителем в узел на 2t−2 ключа, родитель теряет ключ - и проверка повторяется на нём. Опустевший корень убирают: дерево становится ниже целиком. Стоимость - O(t · h) работы и O(h) чтений блоков, как у вставки.

Разбор: пять удалений из 2-3-4 дерева

t = 2: в узле от одного до трёх ключей.

           [10 20]
     [3 5]  [12]  [25 28]

удалить 12: лист пуст. Левый сосед [3 5] - два ключа ≥ t → ЗАЁМ:
    10 спускается, 5 поднимается
           [5 20]
     [3]  [10]  [25 28]

удалить 10: лист пуст. Левый [3] - один ключ, правый [25 28] - два → ЗАЁМ
    справа: 20 спускается, 25 поднимается
           [5 25]
     [3]  [20]  [28]

удалить 3: лист пуст, сосед [20] - один ключ → СЛИЯНИЕ: [] + 5 + [20]
           [25]
     [5 20]  [28]

удалить 25: ключ во внутреннем узле → предшественник 20 (правый в левом
    поддереве) встаёт на его место, удаляется из листа
           [20]
     [5]  [28]

удалить 28: лист пуст, сосед [5] - один ключ → СЛИЯНИЕ: [5] + 20 + []
    корень остался без ключей → его единственный ребёнок - новый корень
     [5 20]                          высота уменьшилась на 1

Все четыре случая встретились: заём слева, заём справа, слияние и убирание корня, плюс замена внутреннего ключа предшественником.

Разбор: тысяча ключей и проверка всех свойств

Программа строит 2-3-4 дерево из тысячи случайных ключей, удаляет 990 из них и после КАЖДОГО удаления проверяет все обещания B-дерева: размеры узлов, порядок ключей, число ключей и одну глубину у всех листьев.

import bisect
import random

T = 2                                  # узел: от T−1 до 2T−1 ключей
stat = {"заём": 0, "слияние": 0, "корень ушёл": 0}


class Uzel:
    def __init__(self, keys=None, deti=None):
        self.keys = keys or []
        self.deti = deti or []         # пусто у листа


def vstavit(koren, k):
    if len(koren.keys) == 2 * T - 1:   # полный корень - расщепить
        koren = Uzel([], [koren])
        rasshepit(koren, 0)
    u = koren
    while u.deti:
        i = bisect.bisect(u.keys, k)
        if len(u.deti[i].keys) == 2 * T - 1:
            rasshepit(u, i)
            i = bisect.bisect(u.keys, k)
        u = u.deti[i]
    bisect.insort(u.keys, k)
    return koren


def rasshepit(otec, i):
    y = otec.deti[i]
    z = Uzel(y.keys[T:], y.deti[T:])
    otec.keys.insert(i, y.keys[T - 1])
    otec.deti.insert(i + 1, z)
    y.keys, y.deti = y.keys[:T - 1], y.deti[:T]


def udalit(koren, k):
    put, u = [], koren                 # путь (узел, номер ребёнка)
    while k not in u.keys:
        i = bisect.bisect(u.keys, k)
        put.append((u, i))
        u = u.deti[i]
    j = u.keys.index(k)
    if u.deti:                         # внутренний - предшественник
        put.append((u, j))
        v = u.deti[j]
        while v.deti:
            put.append((v, len(v.deti) - 1))
            v = v.deti[-1]
        u.keys[j] = v.keys.pop()
        u = v
    else:
        u.keys.pop(j)
    while put and len(u.keys) < T - 1: # недобор: заём или слияние
        otec, i = put.pop()
        levyj = otec.deti[i - 1] if i > 0 else None
        pravyj = otec.deti[i + 1] if i + 1 < len(otec.deti) else None
        if levyj and len(levyj.keys) >= T:
            u.keys.insert(0, otec.keys[i - 1])
            otec.keys[i - 1] = levyj.keys.pop()
            if levyj.deti:
                u.deti.insert(0, levyj.deti.pop())
            stat["заём"] += 1
        elif pravyj and len(pravyj.keys) >= T:
            u.keys.append(otec.keys[i])
            otec.keys[i] = pravyj.keys.pop(0)
            if pravyj.deti:
                u.deti.append(pravyj.deti.pop(0))
            stat["заём"] += 1
        else:                          # слить с соседом и разделителем
            if levyj:
                i -= 1
            a, b = otec.deti[i], otec.deti[i + 1]
            a.keys += [otec.keys.pop(i)] + b.keys
            a.deti += b.deti
            otec.deti.pop(i + 1)
            stat["слияние"] += 1
        u = otec
    if not koren.keys and koren.deti: # пустой корень - дерево ниже
        stat["корень ушёл"] += 1
        return koren.deti[0]
    return koren


def proverit(u, lo, hi, glub, listya):
    assert glub == 0 or T - 1 <= len(u.keys) <= 2 * T - 1
    assert u.keys == sorted(u.keys)
    assert all(lo < x < hi for x in u.keys)
    if not u.deti:
        listya.add(glub)
        return len(u.keys)
    assert len(u.deti) == len(u.keys) + 1
    granicy = [lo] + u.keys + [hi]
    return len(u.keys) + sum(
        proverit(d, granicy[i], granicy[i + 1], glub + 1, listya)
        for i, d in enumerate(u.deti))


def vysota(u):
    return 1 + (vysota(u.deti[0]) if u.deti else 0)


rng = random.Random(5)
klyuchi = rng.sample(range(100000), 1000)
koren = Uzel()
for k in klyuchi:
    koren = vstavit(koren, k)
print("после вставок: ключей 1000, высота", vysota(koren))
rng.shuffle(klyuchi)
for n, k in enumerate(klyuchi[:990]):
    koren = udalit(koren, k)
    listya = set()
    assert proverit(koren, -1, 10**9, 0, listya) == 1000 - n - 1
    assert len(listya) == 1            # все листья на одной глубине
print("после 990 удалений: высота", vysota(koren))
print(stat)

после вставок: ключей 1000, высота 7
после 990 удалений: высота 3
{'заём': 305, 'слияние': 553, 'корень ушёл': 4}

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

Что ломается без этого

Самая частая ошибка - удалить ключ прямо из внутреннего узла и «как-нибудь» склеить двух детей, которые остались без разделителя: число детей перестаёт быть на единицу больше числа ключей, и поиск уходит не в то поддерево. Вторая - при заёме у соседа перенести ключ, но забыть перенести крайнего ребёнка: у одного узла ребёнком больше, у другого меньше, и следующая операция падает. Третья - вообще не чинить недобор: дерево остаётся «правильным» для поиска, но после массовых удалений в нём полно почти пустых узлов, высота не падает, и каждое чтение блока приносит один ключ вместо сотен. Базы данных именно так и «пухнут» - отсюда команды вроде VACUUM и REINDEX.

Зачем это в работе

Индексы баз данных и файловые системы удаляют ключи постоянно, и реальные реализации идут на компромисс. Многие СУБД не сливают узлы сразу: узел помечается как частично пустой, а уплотнение делается фоновым процессом или при перестройке индекса - так удаление не трогает соседние блоки и не держит лишних блокировок. Знание механики объясняет, почему индекс после удаления половины строк не уменьшился на диске, почему после массовой чистки помогает перестройка индекса и почему у B-деревьев на диске ставят минимальное заполнение ниже половины.

Теперь сам

t = 2. Дерево: корень [30], листья [10 20] и [40]. Удали 40. Что произойдёт - заём или слияние, и как будет выглядеть дерево? А если бы левый лист был [10]?