b-tree

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

Предпосылки: оценка сложности в O(…), бинарный поиск (поиск в отсортированном диапазоне делением пополам), двоичное дерево поиска (BST) — инвариант порядка, поиск за O(h); ссылки — ячейка, хранящая адрес другого узла; понятие страницы дисковой памяти (блок фиксированного размера, обычно 4–16 KB, который диск читает за одну операцию).

← Двоичное дерево поиска | далее: B+ дерево · B* дерево · Инвертированный индекс →

BST хранит один ключ в узле. В оперативной памяти это работает хорошо, но на диске каждый узел — потенциальная отдельная операция чтения. Представим базу данных с 10 миллионами записей на жёстком диске, который тратит на подвод головки к нужному месту ~5 ms (это время отдельно от собственно чтения данных). Если BST сбалансирован, его высота — около двоичного логарифма числа записей: log₂ 10⁷ ≈ 23 уровня. Значит, один поиск спускается на 23 уровня, и каждый узел лежит в своём месте диска — порядка 23 случайных чтений × 5 ms = 115 ms на один запрос, больше десятой доли секунды.

Корень проблемы в том, что диск читает не отдельные байты, а страницами по несколько KB, и одна такая страница вмещает сотни ключей. Узел BST занимает порядок десятков байт (ключ плюс указатели на двух детей), то есть на каждой странице, ради одного ключа, впустую читаются сотни соседних. Раз чтение всё равно идёт страницами, выгодно набить узел ключами под завязку — столько, сколько помещается на страницу. B-дерево делает именно это: один его узел занимает целую страницу.

У такого размещения есть ещё один выигрыш, уже в оперативной памяти. Узел B-дерева — это плотный отсортированный набор ключей в одном непрерывном блоке. Одно обращение к памяти подтягивает в кеш процессора сразу группу соседних ключей, и дальнейший поиск внутри узла идёт по уже подтянутым данным, без новых дорогих обращений. Это тот же принцип локальности данных, из-за которого плотно упакованные данные обходятся дешевле, чем структуры с разбросанными по памяти узлами.

Название и происхождение

B-дерево предложили Rudolf Bayer и Edward McCreight в 1972 году в Boeing Labs. Буква «B» не имеет официального объяснения от авторов. Популярные интерпретации — Balanced, Bayer, Boeing, Broad — все работают как мнемоника. Главное: B — это не «binary». B-дерево — противоположность бинарному дереву: вместо двух детей у узла могут быть сотни.

Структура узла

В отличие от BST, узел B-дерева содержит много ключей и много указателей на детей:

┌─────────────────────────────────────────────────────┐
│  P₀ │ K₁ │ P₁ │ K₂ │ P₂ │ K₃ │ P₃ │ ... │ Kₙ │ Pₙ  │
└─────────────────────────────────────────────────────┘

K₁, K₂, … Kₙ — ключи, отсортированные по возрастанию. P₀, P₁, … Pₙ — указатели на детей: каждый ведёт в поддерево. Ключей n, указателей n+1 — на один больше, потому что ключи делят числовую ось на n+1 промежутков, и каждому промежутку нужен свой ребёнок. Ключи работают как разделители: P₀ ведёт в поддерево со значениями меньше K₁, P₁ — со значениями между K₁ и K₂, P₂ — между K₂ и K₃, и так далее. Последний указатель Pₙ ведёт в поддерево со значениями больше Kₙ. Сами ключи K₁…Kₙ хранятся здесь, в этом узле; в детях лежат значения из промежутков между ними.

Параметр t

B-дерево определяется параметром t — минимальной степенью (minimum degree). В теории графов степень вершины — количество рёбер, выходящих из неё; для дерева это количество детей. Минимальная степень t означает: у внутреннего узла минимум t детей.

Характеристика	Значение
Минимум ключей в узле	t − 1
Максимум ключей в узле	2t − 1
Минимум детей у внутреннего узла	t
Максимум детей у внутреннего узла	2t

Корень — исключение: он может содержать от 1 до 2t−1 ключей. В маленьком дереве, где корень — единственный узел, требовать в нём минимум t−1 ключей было бы невозможно, поэтому нижняя граница для корня снята.

В разных источниках используют разные параметры. CLRS (Cormen и др.) задаёт минимальную степень t — минимум t детей. Knuth задаёт порядок m — максимум m детей, тогда m = 2t. Это одно и то же дерево с разным именованием параметра.

На практике t подгоняют под размер страницы диска. При странице 4 KB, ключе 8 байт и указателе 8 байт один узел с n ключами занимает n×8 + (n+1)×8 = 16n + 8 байт. Чтобы уместить узел в 4096 байт: n ≤ 255, то есть 2t − 1 ≈ 255, откуда t ≈ 128. Это грубая оценка: часть страницы реальный узел тратит на служебную информацию (сколько ключей в узле, лист он или нет), так что ключей помещается чуть меньше. Типичные значения t — от нескольких десятков до нескольких сотен.

Инварианты

B-дерево держит четыре инварианта — правила, которые остаются верными до и после любой операции; вставка и удаление ниже устроены так, чтобы их не нарушить. Первое: каждый узел, кроме корня, содержит от t−1 до 2t−1 ключей — ограничение заполнения. Второе: узел с n ключами имеет ровно n+1 детей, если он не лист (лист — узел без детей, на нижнем уровне дерева). Третье: все листья находятся на одной глубине — дерево сбалансировано по определению. Четвёртое: ключи внутри каждого узла отсортированы по возрастанию.

Поиск

Поиск начинается с корня. Ключи в узле отсортированы, поэтому искомый находится бинарным поиском — делением диапазона ключей пополам, за O(log t) сравнений. Если найден — поиск завершён. Иначе известно, между какими двумя ключами узла лежит искомый, а значит, известен и указатель в нужное поддерево (поддерево — узел-ребёнок со всем, что под ним); поиск продолжается в нём. Процесс повторяется до нахождения ключа или достижения листа — узла без детей.

Метрика	Значение	Пояснение
Посещённых узлов	O(log n)	Каждый узел ветвится на ~t детей, поэтому высота — логарифм по основанию ~t
Сравнений в узле	O(log t)	Деление отсортированного узла пополам
Итого сравнений	O(log n)
Чтений с диска	O(log n)	Каждый посещённый узел — одна страница, одно чтение; на диске это и есть главная цена

Высота получается логарифмической именно потому, что каждый шаг вниз сужает поиск не вдвое, как в BST, а в ~t раз: уже за один уровень из миллионов записей остаются десятки тысяч. Чем больше t, тем ниже дерево и тем меньше чтений с диска на один поиск.

При t = 128 и 10 миллионах записей высота — log₁₂₈ 10⁷ ≈ 3.3, то есть поиск спускается через ~3 узла и делает ~3 чтения с диска. На том же диске с 5 ms на подвод головки это 3 × 5 ms = 15 ms вместо 115 ms в BST — разница почти на порядок: те самые 23 уровня BST схлопнулись в 3.

Вставка

Вставка спускается до листа так же, как при поиске, и вставляет ключ на его место в отсортированном ряду. Максимум для узла — 2t−1 ключей; если после вставки их стало 2t (на один больше допустимого, узел переполнен), выполняется split — расщепление.

Split берёт средний ключ переполненного узла (медиану — он стоит ровно посередине отсортированного ряда) и разделяет узел на два: левый получает t−1 ключей до медианы, правый — t−1 ключей после неё. Сама медиана не остаётся ни в одной половине — она переходит в родительский узел и встаёт там разделителем между двумя новыми детьми: один указатель родителя, ведший в старый переполненный узел, заменяется на медиану и пару указателей — на левую и правую половины.

До:    [... переполненный узел с 2t ключами ...]
                  v split
После: [левая половина]  [медиана -> в родителя]  [правая половина]

Если у родителя теперь стало 2t ключей — он переполнился, и split повторяется на нём, каскадно вверх. Если split дошёл до корня и корень переполнен, он расщепляется на два узла, и создаётся новый корень с одним ключом (медианой). Два узла становятся его детьми — дерево вырастает на один уровень.

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

Метрика	Значение
Спуск до листа	O(log n) узлов
Каскадный split (худший случай)	O(log n) узлов
Работа на каждом уровне	O(t), при фиксированном t — константа, не зависящая от числа записей n
Итого	O(log n)
Операций записи на диск	O(log n), на практике обычно 3–4 страницы

Удаление

Удаление ключа зависит от того, где он находится. Если ключ в листе — просто убираем его из отсортированного ряда. Если во внутреннем узле — его нельзя выдернуть напрямую: он разделяет двух детей, и без него поддеревья «слипнутся». Поэтому ключ заменяют ближайшим соседом по значению — предшественником (predecessor, наибольший ключ в поддереве слева от удаляемого) или преемником (successor, наименьший ключ в поддереве справа). Такой сосед всегда лежит в листе: чтобы найти наибольший ключ поддерева, спускаются по самым правым указателям до конца, до узла без детей, — это и есть лист. Замена ставит сосед на место удаляемого ключа, а сам сосед убирают из его листа. Так удаление из любого узла сводится к удалению из листа.

Удаление убирает из листа ровно один ключ. Если до этого ключей было минимально допустимые t−1, после станет t−2 — на один меньше нижней границы, узел «обеднел». Инвариант заполнения нарушен, и его восстанавливают одним из двух способов; оба берут недостающий ключ от соседа — узла с тем же родителем.

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

До:     [...| разделитель |...]        <- родитель
              /          \
        [бедный]    [сосед, ключей с запасом]
 
После:  [...| ключ соседа |...]        <- родитель: новый разделитель
              /          \
   [пополнен старым      [отдал крайний
    разделителем]         ключ]

Слияние (merge): если у соседа ровно минимум, t−1 ключей, заимствовать не у кого — отдав ключ, он сам обеднеет. Тогда бедный узел и сосед сливают в один, а между ними вставляют разделитель, который их разделял в родителе. Считаем ключи нового узла: t−2 (бедный) + 1 (разделитель) + t−1 (сосед) = 2t−2. Это не превышает максимум 2t−1, так что узел получается законным.

До:     [...| разделитель |...]        <- родитель
              /          \
        [t−2]          [t−1]
 
После:  [...]                          <- родитель: разделителя больше нет
           |
    [объединённый: (t−2) + разделитель + (t−1) = 2t−2 ключей]

При merge внутренних узлов объединяются не только ключи, но и дети обоих узлов — инвариант «n ключей → n+1 детей» сохраняется.

Каскадный merge: при слиянии родитель отдал вниз один ключ-разделитель, и его собственное число ключей упало на единицу. Если оно опустилось ниже минимума, теперь обеднел уже родитель — заимствование или слияние повторяется на нём, и так каскадом вверх. Корень — особый случай: у него нет минимума и нет соседа, заимствовать или сливаться не с кем. Если слияние ниже забрало у корня последний ключ, корень остаётся пустым с единственным ребёнком (двое детей слились в одного). Пустой корень убирают, и этот единственный ребёнок становится новым корнем — высота дерева уменьшается на единицу. Это зеркало роста: дерево росло, поднимая медиану в новый корень, и сжимается, убирая опустевший.

Метрика	Значение
Поиск ключа	O(log n)
Поиск предшественника/преемника	O(log n)
Каскадный merge (худший случай)	O(log n)
Итого	O(log n)
Операций записи на диск	O(log n), на практике обычно 3–4 страницы

Симметрия вставки и удаления

Вставка	Удаление
Переполнение (> 2t−1)	Недозаполнение (< t−1)
Split (расщепление)	Merge (слияние)
Ключ поднимается в родителя	Ключ спускается из родителя
Дерево растёт вверх при split корня	Дерево сжимается при пустом корне

Все три операции — поиск, вставка, удаление — выполняются за O(log n) с основанием ~t. При t = 128 это означает 3–4 обращения к диску на 10 миллионов записей вместо 23 у BST.

До сих пор речь шла о ключах, по которым идёт поиск. Но у каждого ключа есть и полезная нагрузка — сама запись (или указатель на неё). B-дерево хранит эту нагрузку во всех узлах, и внутренних, и листовых: ключ-разделитель, по которому маршрутизируется поиск, тащит с собой и данные. Значит, внутренние узлы тратят часть страницы на нагрузку — а место на странице и есть то, что определяет ветвление t и высоту дерева. Если убрать данные из внутренних узлов и держать их только в листьях, на страницу внутреннего узла поместится больше ключей-разделителей, ветвление вырастет, дерево станет шире и ниже — а значит, поиск потребует ещё меньше чтений с диска. Эту идею реализует B+ дерево.

Sources

• Bayer, R., McCreight, E. (1972). Organization and Maintenance of Large Ordered Indices. https://doi.org/10.1007/BF00288683
• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
• Knuth, D. The Art of Computer Programming, Vol. 3: Sorting and Searching. https://www-cs-faculty.stanford.edu/~knuth/taocp.html

---

← Двоичное дерево поиска | далее: B+ дерево · B* дерево · Инвертированный индекс →