llmdocsсправочник разработчика

B-дерево

Материал из llmdocs — справочник разработчика
Портал: Базы данных
B-дерево
АвторыРудольф Байер, Эдвард Маккрейт (Boeing)
Год1970 (публикация — 1972)
Сложность поиска, вставки, удаленияO(log n)
Ветвлениесотни ключей на узел
Вариант в СУБДB+-дерево — данные только в листьях, листья связаны
Где используетсяPostgreSQL, MySQL InnoDB, SQLite, Oracle, файловые системы (NTFS, Btrfs, XFS, APFS)
АльтернативаLSM-дерево (RocksDB, Cassandra)

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

Вариант B+-дерево — стандартная структура индексов в PostgreSQL, MySQL, SQLite, Oracle и SQL Server, а также основа многих файловых систем.

История

Рудольф Байер и Эдвард Маккрейт разработали B-дерево в 1970 году в исследовательской лаборатории Boeing; статья вышла в 1972 году.[1] Что означает буква «B», авторы так и не уточнили: среди версий — Boeing, Bayer, balanced («сбалансированное») и broad («широкое»). Уже к 1979 году обзор Дугласа Комера назывался «Вездесущее B-дерево» — структура стала стандартом для индексов баз данных и файлов.[2]

Почему не двоичное дерево

Диск и SSD читают данные не байтами, а страницами — блоками по 4–16 КБ. Обращение к новой странице на порядки дороже сравнения в памяти. Двоичное дерево для миллиона ключей имеет глубину около 20 — это 20 случайных чтений с диска на каждый поиск. B-дерево с узлом размером в страницу и 500 ключами на узел вмещает миллион записей в три уровня, причём корень и верхний уровень почти всегда находятся в кэше. Поиск сводится к одному-двум чтениям.

Записей Двоичное дерево (уровней) B-дерево, 500 ключей на узел (уровней)
1 000 10 2
1 000 000 20 3
1 000 000 000 30 4

Устройство

B-дерево порядка m удовлетворяет правилам:

  • в узле хранятся упорядоченные ключи, и между соседними ключами — ссылка на поддерево со значениями из этого промежутка;
  • каждый узел, кроме корня, заполнен как минимум наполовину;
  • все листья находятся на одной глубине — дерево всегда идеально сбалансировано.

Поиск начинается с корня: в узле двоичным поиском находится нужный промежуток, затем переход к соответствующему потомку, и так до листа. Вставка добавляет ключ в лист; если лист переполнен, он расщепляется пополам, а средний ключ поднимается в родителя. Расщепление может дойти до корня — тогда появляется новый корень, и дерево вырастает на уровень. Рост «снизу вверх» и сохраняет баланс. Удаление при недозаполнении узла занимает ключи у соседа или сливает узлы. Все операции выполняются за O(log n) (см. Алгоритм и O-нотация).

B+-дерево

В базах данных почти всегда используется вариант B+-дерево:

  • значения (или ссылки на строки таблицы) хранятся только в листьях, а внутренние узлы содержат лишь ключи-разделители — поэтому они компактнее и ветвление выше;
  • листья связаны в список, так что диапазонный запрос (WHERE created_at BETWEEN ..., ORDER BY) находит начало диапазона и затем просто идёт по листьям.

Этим объясняется, почему B-tree-индекс помогает не только равенству, но и сравнениям, сортировке и поиску по префиксу строки.

В конкретных СУБД

  • PostgreSQL — индекс по умолчанию — B-дерево (реализация по алгоритму Лемана — Яо с поддержкой параллельного доступа); страница 8 КБ; дедупликация одинаковых ключей с версии 13. Строки таблицы хранятся отдельно, в «куче», а индекс ссылается на них.[3]
  • MySQL InnoDB — таблица сама хранится как B+-дерево по первичному ключу (кластерный индекс), страница 16 КБ; вторичные индексы ссылаются на значение первичного ключа. Поэтому случайный UUID в качестве первичного ключа приводит к частым расщеплениям страниц, а последовательные идентификаторы — нет.[5]
  • SQLite — вся база данных — набор B-деревьев в одном файле: таблицы хранятся как B+-деревья по rowid, индексы — как B-деревья.[4]

B-деревья и LSM-деревья

Для нагрузок с очень интенсивной записью используют альтернативу — LSM-дерево (log-structured merge tree): записи сначала накапливаются в памяти, затем сбрасываются на диск отсортированными файлами, которые фоном сливаются.[6]

B+-дерево LSM-дерево
Запись обновление на месте, случайный ввод-вывод последовательная запись, очень быстро
Чтение предсказуемо быстрое может требовать проверки нескольких файлов
Фоновая работа очистка страниц постоянное слияние (compaction)
Примеры PostgreSQL, InnoDB, SQLite RocksDB, Cassandra, ScyllaDB, ClickHouse (MergeTree)

Практические следствия

  • Индексу нужна память: «горячие» верхние уровни должны помещаться в кэш СУБД.
  • Порядок столбцов в составном индексе определяет, какие запросы он ускоряет, — ключи сравниваются слева направо.
  • Частые вставки в середину и удаления фрагментируют страницы; периодическая перестройка (REINDEX) возвращает компактность.

См. также

Источники

  1. R. Bayer, E. McCreight — Organization and Maintenance of Large Ordered Indexes (Acta Informatica, 1972)
  2. D. Comer — The Ubiquitous B-Tree (ACM Computing Surveys, 1979)
  3. PostgreSQL Documentation — B-Tree Indexes
  4. SQLite — Database File Format
  5. MySQL — Clustered and Secondary Indexes (InnoDB)
  6. P. O'Neil et al. — The Log-Structured Merge-Tree (LSM-Tree) (1996)
Категории: