B-дерево

Положим первые 100 000 слов «Войны и мира» в индекс, как это сделала бы база данных: ключ — слово и его место в тексте, на странице — до 128 ключей. Получится дерево из трёх этажей: корень, 16 страниц под ним и 1251 лист. Чтобы найти любой из ста тысяч ключей, нужно прочитать три страницы. Обычное двоичное дерево поиска на тех же ключах, вставленных в том же порядке, вырастает в высоту 4800: у союза «и» 4785 вхождений, их ключи приходят по возрастанию позиций и выстраиваются в цепочку. Ниже каждая страница индекса нарисована полоской, высота которой — насколько страница заполнена.

Высота не меняется, что бы вы ни делали с порядком: три этажа и вразброс, и по алфавиту. Меняется заполнение. В порядке текста листья заполнены на 62,5 %, вразброс — на 69,4 %, по алфавиту — ровно наполовину: 1562 листа вместо 782. А если переключить деление на «у правого края», алфавитный порядок даёт листья, заполненные на 99,9 %. Почему так, разберём ниже; сначала — зачем дереву страницы.

Идея

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

Это дерево поиска, у которого в узле не один ключ, а много: внутри страницы искать нужно двоичным поиском или просмотром, но эта работа идёт в памяти и почти ничего не стоит по сравнению с чтением страницы. Как Рудольф Байер и Эдвард Маккрейт придумали его в Boeing, почему никто не знает, что значит B, и как B-деревья устроены внутри SQLite, рассказано в главе курса об индексах; там же есть сцена, где можно менять ширину узла и смотреть, сколько этажей нужно. Здесь — почему лучше нельзя, сколько места пропадает и что с этим делают базы данных.

Почему меньше страниц прочитать нельзя

Когда данные лежат на диске, время поиска определяет не число сравнений, а число прочитанных блоков: одно чтение стоит как миллионы сравнений в памяти. Так и считают в модели внешней памяти: блок из B ключей читается за одну операцию, а всё, что делается с ним в памяти, бесплатно.

B-дерево к этой границе вплотную. Пусть страница вмещает до 127 ключей и 128 детей, а заполнена не меньше чем на 63 ключа и 64 ребёнка — так устроено B-дерево с минимальной степенью 64. Полное дерево из L этажей вмещает 128^L − 1 ключей: три этажа — до двух миллионов, четыре — до 268 миллионов. Самое разреженное — 2 · 64^L−1 − 1. Для миллиарда ключей обе оценки дают одно и то же: в любом таком B-дереве ровно пять этажей, а по теореме меньше пяти чтений не бывает. Двоичному дереву поиска даже идеальной формы понадобилось бы 30 этажей — тридцать страниц на поиск, если каждый узел лежит на своей.

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

Вставка: страница делится, дерево растёт вверх

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

Отсюда и гарантия по памяти. Лист, который поделили пополам, оставляет каждой половине не меньше половины ключей, и, пока ключи только добавляются, ни одна страница, кроме корня, не бывает заполнена меньше чем наполовину. При удалении страницу, где ключей стало меньше половины, пополняют ключом у соседки или сливают с ней — и гарантия сохраняется.

Сколько места пустует

Половина — нижняя граница. Сколько получается на деле, зависит от порядка ключей, и это видно в сцене.

Случайный порядок. Эндрю Яо в 1978 году показал, что при случайных вставках страницы B-дерева с большими страницами заполнены в среднем на ln 2 ≈ 69 %. Только что поделившаяся страница заполнена наполовину, полная — целиком, и страницы всё время проходят этот цикл. На перемешанных ключах романа выходит 69,4 %.

Порядок текста. 62,5 % — меньше случайного. Ключ — пара «слово, место», а места каждого слова приходят по возрастанию: внутри своего участка индекса каждое частое слово дописывается в конец, как при вставке по порядку. Настоящие данные снова оказываются между теорией и худшим случаем.

По возрастанию. Так приходят автоинкрементные номера строк, отметки времени, номера заказов. Каждый новый ключ больше всех, попадает в самый правый лист, и при делении левая половина больше никогда не получит ни одного ключа: все листья, кроме последнего, навсегда остаются заполнены наполовину. Индекс занимает вдвое больше места, чем нужно, и поиск по нему читает вдвое больше страниц.

Двадцать номеров заказов при делении пополам занимают девять листьев, заполненных на 56 %: каждый лист, кроме последнего, получил два номера и больше не получит ни одного. Базы данных этот случай распознают. SQLite, когда новый ключ становится самым большим в таблице, не делит переполненный лист, а заводит справа новую страницу и кладёт в неё один новый ключ — в исходнике сказано, что правый край дерева остаётся немного несбалансированным, но скоро заполнится следующими вставками. PostgreSQL при делении самой правой страницы оставляет левую заполненной на долю fillfactor — для листьев B-дерева по умолчанию это 90 % — и тем же правилом заполняет страницы, когда индекс строится заново из готовой таблицы. Переключите в первой сцене деление на «у правого края»: алфавитный порядок даёт 782 листа, заполненных на 99,9 %, вдвое меньше, чем при делении пополам.

B+ и диапазоны: листья — связный список

В B+-дереве листья связаны ссылками в порядке ключей — это связный список страниц. Диапазонный запрос — «все ключи от a до b» — спускается от корня к первому ключу диапазона и дальше идёт вдоль листьев, не поднимаясь наверх. Все 607 упоминаний слова «князь» в первых 100 000 словах романа индекс с полными листьями отдаёт за семь страниц: три на спуск и четыре листа подряд. Впишите в сцене любое слово — видно и спуск, и пробег по листьям.

Так же устроен обратный индекс поисковика: для каждого слова — упорядоченный список мест, где оно встречается.

Код

B+-дерево с двумя правилами деления, поиском диапазона по связанным листьям и счётчиком делений. Сначала маленький пример — первые двадцать разных слов романа, страница на четыре ключа, — потом индекс по первым 100 000 словам со страницами на 128 ключей, четыре порядка вставки. Числа в таблице совпадают со сценой.

order, split             height    pages per level leaves full  splits
text, half                    3          1-16-1251       62.5%   1,250
shuffled, half                3          1-16-1125       69.4%   1,124
alphabetical, half            3          1-24-1562       50.0%   1,561
alphabetical, edge            3           1-12-782       99.9%     781
князь: 607 keys, 7 pages read (3 down, the rest along the leaves)

Последнюю строку печатает последнее построенное дерево — с полными листьями. В Go ключ «слово и место» записан строкой: слово, нулевой байт и номер с ведущими нулями. Такие строки сравниваются так же, как пары, а нулевой байт меньше любой буквы, поэтому «кот» идёт раньше «кота».

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

На тысяче ключей в Go двоичное дерево даже быстрее: оно целиком в кэше, а у B-дерева больше работы на странице. На миллионе B-дерево больше чем вчетверо быстрее двоичного и почти догоняет отсортированный массив, который можно считать B-деревом с одной огромной страницей. В Python B-дерево выигрывает с самого начала: поиск внутри страницы делает bisect, написанный на C, а двоичное дерево платит интерпретатору за каждый этаж.

Сколько это стоит

Память — O(n) с запасом: каждая страница заполнена не меньше чем наполовину, при случайной вставке — около 69 %. Вставка в середину страницы сдвигает до B ключей, но это работа в памяти над одним блоком, и по сравнению с его чтением она бесплатна.

Где работает

Почти везде, где упорядоченные данные лежат на диске. SQLite хранит в B-деревьях и таблицы, и индексы; B-дерево — тип индекса по умолчанию в PostgreSQL, на B-деревьях построены и индексы MySQL. Файловая система Btrfs называется так по B-дереву, на котором она держится. В памяти — BTreeMap в Rust. Если записей гораздо больше, чем чтений, вместо того чтобы править страницы на месте, новые ключи копят в памяти и сбрасывают на диск отсортированными пачками — так устроено LSM-дерево, а пачки потом сливает внешняя сортировка.

История

Байер и Маккрейт описали B-дерево в отчёте исследовательских лабораторий Boeing в 1970 году, а в 1972-м статья вышла в первом томе журнала Acta Informatica. В 1979 году Дуглас Комер назвал обзор о них «Вездесущее B-дерево»; главным вариантом в нём разобрано B+-дерево, и это одно из первых мест, где встречается такое название. Среднее заполнение ln 2 для случайных вставок получил Эндрю Яо в 1978 году — для этого он придумал новый метод анализа деревьев, который потом применяли и к другим структурам. История самих Байера и Маккрейта — в главе курса.

Задачи

В первой задаче нужно сосчитать, сколько страниц займёт индекс, если вставлять в него ключи по одному, — и заметить, что для этого не нужны верхние этажи. Тесты — слова «Войны и мира» и время землетрясений из каталога USGS. Во второй — сколько этажей может быть у B-дерева с n ключами, и подвох в том, что логарифмы в плавающей точке на границах ошибаются.