b-plus-tree

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

Предпосылки: оценка сложности в O(…), B-дерево — split/merge, параметр t, инварианты заполнения; связный список — указатели prev/next.

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

Ключевое отличие от B-дерева

B-дерево	B+ дерево
Данные хранятся во всех узлах	Данные хранятся только в листьях
Ключ существует в одном месте	Ключи во внутренних узлах — разделители (копии ключей из листьев)
Поиск может завершиться на любом уровне	Поиск всегда доходит до листа

B-дерево:
            [17]              ← 17 здесь И ТОЛЬКО здесь
           /    \
      [5|13]    [22|30]
 
B+ дерево:
            [17]              ← 17 здесь как разделитель (копия)
           /    \
      [5|13]    [17|22|30]    ← и 17 здесь с данными

В типичном варианте B+ дерева разделитель K выбирают как минимальный ключ правого поддерева: ключи < K идут влево, ключи ≥ K — вправо.

Внутренние узлы без данных

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

Связанные листья

Листья B+ дерева связаны в двусвязный список:

            [17 | 35]
           /    |    \
          ↓     ↓     ↓
      [5|13] ↔ [17|22] ↔ [35|40|48]

Минимально достаточен односвязный список (только next) для обхода слева направо. Но двусвязный (prev + next) позволяет обходить листья в обоих направлениях, что нужно для запросов с обратной сортировкой.

Связанные листья делают эффективным range scan — сканирование диапазона. Запрос SELECT * FROM employees WHERE salary BETWEEN 40000 AND 60000 в B-дереве потребовал бы in-order обхода по внутренним узлам, поднимаясь и спускаясь для каждого следующего ключа. В B+ дереве достаточно одного спуска до листа с первым ключом ≥ 40000, а затем линейного прохода по связному списку вправо до ключа, превышающего 60000. Каждый следующий лист — последовательное чтение соседней страницы, а не случайный доступ по дереву.

Предсказуемость

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

Структура листа

┌─────────────────────────────────────────────────────┐
│ prev | K₁,D₁ | K₂,D₂ | K₃,D₃ | ... | Kₙ,Dₙ | next │
└─────────────────────────────────────────────────────┘

D — либо сами данные, либо указатель на запись в отдельном хранилище. Указатель prev опционален — минимально нужен только next для range scan слева направо.

Вставка: split копирует

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

[B-дерево](b-tree.md) split:
До:     [10 | 20 | 30 | 40]
После:  [10] ← [20] → [30 | 40]
        20 ушёл наверх, в листьях его нет
 
[B+ дерево](b-plus-tree.md) split:
До:     [10 | 20 | 30 | 40]
После:  [10 | 20] ← [30] → [30 | 40]
        30 скопирован наверх И остался в правом листе

При split внутренних узлов — как в обычном B-дереве: медиана перемещается, а не копируется.

Удаление

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

            [20]              ← разделитель остался
           /    \
      [10|15]   [25|30]       ← ключа 20 в листьях нет

Поиск ключа 20 пойдёт вправо (20 ≥ 20), не найдёт его в листе [25|30] и вернёт «не найден».

При merge листьев в B+ дереве разделитель из родителя просто удаляется — все данные уже есть в листьях. В B-дереве разделитель спускается в объединённый узел, потому что он содержит данные, которых нет в детях.

До:        [...| 20 |...]
              /     \
         [10|15]   [25|30]
 
После:     [...]
              |
        [10|15|25|30]         ← 20 просто удалён

При merge внутренних узлов — как в обычном B-дереве (разделитель спускается).

B+ дерево — стандарт для баз данных (PostgreSQL, MySQL, SQLite) и файловых систем. Его split создаёт два узла, заполненных примерно наполовину. В худшем случае дерево может быть заполнено всего на ~50%, а половина дискового пространства под индекс — пустой. B* дерево решает эту проблему, повышая минимальное заполнение до 2/3.

Sources

• Comer, D. (1979). The Ubiquitous B-Tree. https://doi.org/10.1145/356770.356776
• PostgreSQL docs (current): B-tree indexes (PostgreSQL B-tree — вариант B+ дерева). https://www.postgresql.org/docs/current/btree.html
• SQLite docs: The Database File Format (B-tree pages for tables/indexes). https://www.sqlite.org/fileformat.html

Sources

• Comer, D. (1979). The Ubiquitous B-Tree. https://doi.org/10.1145/356770.356776
• PostgreSQL docs (current): B-tree indexes (PostgreSQL B-tree — вариант B+ дерева). https://www.postgresql.org/docs/current/btree.html
• SQLite docs: The Database File Format (B-tree pages for tables/indexes). https://www.sqlite.org/fileformat.html