b-plus-tree

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

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

← B-дерево

В 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]
           /    |    \
          v     v     v
      [5|13] <-> [17|22] <-> [35|40|48]

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

Связанные листья делают эффективным range scan — выборку всех ключей в заданном диапазоне, например всех ключей от 40000 до 60000. Без связанных листьев такая выборка идёт обходом дерева по возрастанию: дойдя до последнего ключа в листе, чтобы взять следующий, приходится подниматься к родителю и спускаться в соседний лист — отдельный путь сверху вниз на каждый переход между листьями. В B+ дереве достаточно одного спуска до листа с первым ключом ≥ 40000, а затем линейного прохода по связному списку вправо до ключа, превышающего 60000. Каждый следующий лист — последовательное чтение соседней страницы, а не случайный доступ по дереву, а последовательное чтение страниц диск выполняет заметно быстрее разрозненных.

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

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

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

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

Лист хранит пары ключ–данные: Kᵢ — ключ, Dᵢ — данные при этом ключе, по краям — указатели prev/next на соседние листья. D — либо сами данные, лежащие прямо в листе, либо указатель на них, если данные хранятся отдельно от индекса. Указатель prev опционален — минимально нужен только next для range scan слева направо.

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

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

B-дерево split:
До:     [10 | 20 | 30 | 40]
После:  [10] <- [20] -> [30 | 40]
        20 ушёл наверх, в листьях его нет
 
B+ дерево 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-дереве (разделитель спускается).

Сочетание компактных внутренних узлов, предсказуемой глубины и дешёвого range scan и сделало 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

---

← B-дерево