Почему B-деревья быстрые?

B-дерево — это структура, помогающая выполнять поиск в больших объёмах данных. Она была изобретена более сорока лет назад, однако по-прежнему используется в большинстве современных баз данных. Хотя существуют и более новые структуры индексов, например, LSM-деревья, B-дерево пока никто не победил в обработке большинства запросов баз данных.

После прочтения этого поста вы будете знать, как B-дерево упорядочивает данные и выполняет поисковые запросы.

Происхождение

Чтобы понять B-дерево, давайте сначала рассмотрим двоичное дерево поиска (Binary Search Tree, BST).

Постойте, разве это не одно и то же?

Тогда что означает «B»?

Согласно Википедии, изобретатель B-дерева Эдвард Маккрейт однажды сказал:

«Чем больше вы думаете о том, что означает буква B в понятии "B-дерево", тем лучше вы понимаете B-деревья».

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

Большее число всегда справа, а меньшее — слева. С добавлением новых чисел это становится очевиднее.

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

12, переходим к правому узлу. 14 > 15, переходим к левому узлу" width="690" height="346"/>

Оборудование

Теоретически, использование двоичного дерева поиска для выполнения запросов вполне работает. Его временная сложность (при поиске) равна O(logn), как и у B-дерева. Однако на практике эта структура данных должна работать на реальном оборудовании, а индекс нужно хранить где-то на машине.

Данные в компьютере могут храниться в трёх местах:

• Кэши CPU

• ОЗУ (память)

• Диск (накопитель)

Кэш полностью управляется CPU. Однако он относительно мал, обычно лишь несколько мегабайтов. Индекс может содержать гигабайты данных, так что не поместится туда.

Базы данных широко используют память (ОЗУ). Это имеет огромные преимущества:

• гарантирует быстрый произвольный доступ (подробнее об этом в следующем разделе)

• её размер может быть довольно большим (например, облачный сервис AWS RDS предоставляет инстансы с несколькими терабайтами доступной памяти).

Какие же есть недостатки у такого подхода? При отключении питания данные теряются. Кроме того, по сравнению с диском это гораздо более дорогое хранилище.

Наконец, недостатки памяти — это преимущества дисков. Они дёшевы, а данные сохраняются на них даже при отключении питания. Однако бесплатный сыр только в мышеловке! Проблема в том, что нужно быть аккуратными с произвольным и последовательным доступом. Считывание с диска — быстрая операция, но только при соблюдении определённых условий! Попытаюсь объяснить их простым языком.

Произвольный и последовательный доступ

Память можно визуализировать как линию из ящиков для значений, где каждый ящик пронумерован.

Предположим, что мы хотим считать данные из ящиков 1, 4 и 6. Для этого требуется произвольный доступ:

Теперь сравним это со считыванием из ящиков 3, 4 и 5. Это действие можно выполнить последовательно:

Разницу между произвольным переходом (random jump) и последовательным считыванием (sequential read) можно объяснить на примере жёсткого диска. Он состоит из головки и диска.

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

Исследования различий в скорости между произвольным и последовательным доступом приведены в статье Адама Джейкобса «The Pathologies of Big Data», опубликованной в Acm Queue. В статье раскрываются поражающие факты:

• Последовательный доступ в HDD может быть в сотни тысяч раз быстрее, чем произвольный.

• Последовательное считывание с диска может быть быстрее. чем произвольное считывание из памяти.

Но кто вообще сегодня пользуется HDD? Как насчёт SSD? Это исследование показывает, что полностью последовательное чтение с HDD может быть быстрее, чем с SSD. Однако стоит учесть, что исследование проведено в 2009 году, а SSD за последнее десятилетие сильно усовершенствовались, поэтому эти результаты, скорее всего, устарели.

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

Оптимизация дерева под последовательный доступ

Двоичное дерево поиска можно представить в памяти так же, как и кучу:

• позиция родительского узла — это i

• позиция левого узла — это 2i

• позиция правого узла — это 2i+1

Вот как эти позиции вычисляются в нашем примере (родительский узел начинается с 1):

Узлы выстраиваются в памяти cогласно вычисленным позициям:

Помните визуализацию запроса, показанную несколькими разделами ранее?

Вот, как это работает на уровне памяти:

При выполнении запроса необходимо посетить адреса памяти 1, 3 и 6. Посещение трёх узлов не вызывает проблем; однако при сохранении большего количества данных дерево становится выше. Для хранения более миллиона значений требуется дерево высотой не менее 20. Это значит, что необходимо считывать 20 значений из разных мест памяти. Это создаёт совершенно произвольный доступ!

Страницы

Когда дерево растёт в высоту, произвольный доступ вызывает всё большие и большие задержки. Уменьшить эту проблему можно простым способом: выращивать дерево больше в ширину, чем в высоту. Это можно реализовать упаковкой в один узел нескольких значений.

Это даёт нам следующие преимущества:

• дерево становится ниже (два уровня вместо трёх)

• в нём по-прежнему есть много места для новых значений без необходимости дальнейшего разрастания

Выполняемый с таким индексом запрос выглядит так:

Стоит отметить. что при каждом посещении узла нам нужно загрузить все его значения. В этом примере для достижения нужного узла нам нужно загрузить четыре значения (или шесть, если дерево полное). Ниже представлена визуализация этого дерева в памяти:

По сравнению с предыдущим примером (где дерево растёт в высоту) этот поиск должен быть быстрее. Произвольный доступ нужен нам лишь дважды (переход к ячейкам 0 и 9), после чего остальные значения считываются последовательно.

С ростом базы данных такое решение работает всё лучше. Если нужно хранить миллион значений, то вам понадобится:

• Двоичное дерево поиска высотой 20 уровней

ИЛИ

• Дерево с узлами из трёх значений высотой 10 уровней

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

А как это соотносится с реальностью? Размер страницы Postgres составляет 8 кБ. Допустим, 20% — это метаданные, так что остаётся 6 кБ. Половина страницы требуется для хранения указателей на дочерние узлы этого узла, то есть на значения остаётся 3 кБ. Размер BIGINT составляет 8 байтов, так что на одной странице можно хранить примерно 375 значений.

Допустим, какие-то очень большие таблицы базы данных содержат миллиард значений; сколько уровней в дереве Postgres потребуется для их хранения? Согласно представленным выше расчётам, если мы создадим дерево, способное хранить в одном узле 375 значений, то оно может хранить миллиард значений в дереве, имеющем всего четыре уровня. В двоичном дереве поиска для такого объёма данных потребовалось бы 30 уровней.

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

Балансировка

В базах данных есть два вида операций: чтение и запись. В предыдущем разделе мы рассмотрели задачу чтения данных из B-дерева. Однако чтение тоже очень важно. При записи данных в базу данных B-дерево нужно постоянно дополнять новыми значениями.

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

Когда дерево имеет разную глубину в разных узлах, оно называется несбалансированным. По сути, существует два способа возврата такого дерева в сбалансированное состояние:

1. Перестройка его с самого начала простым добавлением значений в нужном порядке.

2. Обеспечение его постоянной балансировки при добавлении новых значений.

В B-дереве реализован второй вариант. Функция, постоянно балансирующая дерево, называется самобалансировкой.

Самобалансировка на примере

Создавать B-дерево можно с одного узла, а затем добавлять новые значения, пока в нём не кончится место.

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

Интересная ситуация возникает, когда более высокой страницы нет. В таком случае нужно сгенерировать новую (и она становится новой корневой страницей!).

Наконец, в дереве есть свободное место, поэтому можно вставить значение 14.

Следуя этому алгоритму, мы можем постоянно добавлять в B-дерево новые значения, и оно постоянно будет оставаться сбалансированным!

На этом этапе у вас могут возникнуть обоснованные опасения, что в дереве есть много свободного места, которое никак не удастся заполнить. Например, значения 14, 15 и 16 находятся на разных страницах, поэтому на этих страницах постоянно будет лишь одно значение и два пустых места.

Эта проблема вызвана выбором точки разбиения. В примере мы всегда выполняем разбиение посередине. Но при каждом разбиении мы можем выбирать любое нужное нам место разбиения.

В Postgres есть алгоритм, выполняемый при каждом разбиении! Его реализацию можно найти в функции _bt_findsplitloc() исходного кода Postgres. Задача алгоритма — оставлять минимальное количество свободного места.

Подведём итог

Из этой статьи мы узнали, как работает B-дерево. В конечном итоге, его можно описать как двоичное дерево поиска с двумя изменениями:

• каждый узел может содержать несколько значений

• после вставки нового значения выполняется алгоритм самобалансировки.

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