b-tree

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

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

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

При этом одна страница диска/буфера (обычно несколько KB) вмещает сотни ключей, а один узел BST занимает порядок десятков байт (ключ + указатели). Чтение всё равно происходит страницами — значит, выгодно хранить в одном узле столько ключей, сколько помещается на страницу. 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. Ключи работают как разделители диапазонов: P₀ ведёт к значениям меньше K₁, P₁ — к значениям от K₁ (включительно) до K₂, P₂ — от K₂ до K₃, и так далее. Последний указатель Pₙ ведёт к значениям не меньше Kₙ.

Параметр t

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

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

Корень — исключение: он может содержать от 1 до 2t−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 n)	Высота дерева с основанием ~t
Сравнений в узле	O(log t)	Бинарный поиск внутри узла
Итого сравнений	O(log n)
Чтений с диска	O(log n)	Главная метрика для дисковых систем

При t = 128 и 10 миллионах записей поиск требует ~3 чтения с диска (log₁₂₈ 10⁷ ≈ 3.3). На том же HDD с 5 ms seek time это 3 × 5 ms = 15 ms вместо 115 ms в BST — разница почти на порядок.

Вставка

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

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

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

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

B-дерево растёт вверх, а не вниз. В BST новые узлы добавляются как листья и глубина растёт неравномерно. В B-дереве новый уровень появляется только при split корня, все листья всегда на одной глубине.

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

Удаление

Удаление ключа зависит от того, где он находится. Если ключ в листе — просто удаляем. Если во внутреннем узле — заменяем на predecessor (максимальный ключ в поддереве слева от него) или successor (минимальный ключ в поддереве справа), оба всегда в листе. Задача сводится к удалению из листа.

После удаления узел может стать «бедным» — содержать меньше t−1 ключей. Восстановить инвариант можно двумя способами.

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

До:     [...| P |...]
           /     \
      [бедный]  [богатый сосед]
 
После:  [...| Q |...]
           /     \
    [пополнен]  [отдал ключ]

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

До:     [...| P |...]
           /     \
      [t−2]     [t−1]
 
После:  [...]
           |
    [объединённый: 2t−2 ключей]

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

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

Метрика	Значение
Поиск ключа	O(log n)
Поиск predecessor/successor	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-дерево хранит данные (или указатели на данные) во всех узлах — и внутренних, и листовых. Это означает, что внутренние узлы тратят часть страницы на данные вместо ключей-разделителей. Если убрать данные из внутренних узлов и хранить их только в листьях, на страницу поместится больше ключей, дерево станет шире и ниже. Эту идею реализует 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

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