B-деревья: больше, чем я думал, я хочу знать

bдеревьябольшечемядумаляхочузнать

Недавно я прочитал превосходную внутреннюю часть базы данных (Алексей Петров, 2021). Первая половина книги посвящена реализации механизмов хранения базы данных – подсистемы СУБД, которая обрабатывает долгосрочное сохранение данных. Удивительно, но в этом разделе обсуждается реализация и оптимизация различных структур данных B-Tree.

В моем курсе «Структуры данных и алгоритмы» мы покрыл B-Trees, но я не гадал, почему я решил использовать его. Как уже было сказано, B-деревья были, по сути, «лучшими» деревьями двоичного поиска, с некоторыми незначительными изменениями, которые позволили повысить производительность при использовании в приложениях баз данных. Я помню, что мне нужно было запомнить кучу уравнений для определения пропускной способности B-дерева M-степени и смутное понимание поиска / вставки / удаления B-дерева, но не более того. Какая жалость! Это интересные структуры.

Это было частично из-за отсутствия визуализации, а частично из-за отсутствия мотивирующих примеров. О визуализации: большинство визуализаций B-Tree, которые я видел, изображают их более или менее как n-арные деревья, обычно степени 3-5. Это не неправильно , но это неясно, почему вы на самом деле должны использовать B-Tree (например, частично, совместное размещение, возможно, сотен ключей в одном узле).

The Wikipedia article illustration of a B+ Tree

Иллюстрация в статье Википедии дерева B + Источник: Википедия

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

Этот пост не является исчерпывающим руководством по B-деревьям (я бы рекомендовал Database Internals для чего-то, что приближается к этому). ). Скорее, вот как я теперь объясню, почему полезна структура данных, такая как B-Tree:

Дисковые ограничения

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

  • Ограничение: Весь набор данных не помещается в памяти.
    • Эффект: Данные нужно выложить так что обход структуры возможен путем загрузки в память только части структуры.
  • Ограничение: Наименьшая единица хранения, которая может быть прочитана / записана на / с диска, велика по сравнению с доступом в памяти (обычно целая страница по сравнению с одним байтом).
    • Эффект: Вероятно, попытка совмещения данных для максимально возможного совместного доступа.
  • Ограничение: Дисковый ввод-вывод значительно медленнее, чем поиск в памяти.
    • Эффект: Уменьшите количество обращений к диску по мере как можно больше.

Итак, с чего начать? Петров начинает с наглядного примера. Рассмотрим наивный подход, при котором мы храним ключи / значения в двоичном дереве поиска (BST) и сохраняем этот BST на диске:

Если бы мы хотели поддерживать BST на диске, мы столкнулись бы с несколькими проблемами. Одна из проблем – локальность: поскольку элементы добавляются в случайном порядке, нет гарантии, что вновь созданный узел будет записан рядом со своим родительским, а это означает, что указатели дочерних узлов могут охватывать несколько страниц диска.

Поскольку у двоичных деревьев разветвление всего два, высота – это двоичный логарифм количества элементов в дереве, и мы должны выполнить O (log2 N) попыток найти искомый элемент, а затем , выполните такое же количество переносов диска.

Наивный на -disk реализация BST потребует столько же обращений к диску, сколько и сравнений, поскольку нет встроенной концепции локальности.

(п29 – 38, акцент мой)

BST как дисковые структуры терпят неудачу, потому что количество ключевых сравнений равно ro уродливо равно количеству поисков диска.

Обратите внимание, что здесь важны две величины: количество сравнений ключей , а количество запросов к диску . Количество ключевых сравнений, необходимых для нахождения записи, зависит от размера нашего набора данных, поэтому мы мало что можем сделать, чтобы повлиять на это. Однако мы можем повлиять на количество сравнений ключей, разрешенных при каждом поиске по диску . Как? Путем размещения ключей вместе в макете на диске. Что, если бы, скажем, мы сохранили связку ключей, расположенных рядом друг с другом на диске, чтобы за один поиск мы могли выполнить большое количество сравнений ключей? Ага – вот что мы получаем с B-Trees. Другими словами, B-деревья имеют большое количество разветвлений.

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

Страницы с прорезями

Итак пока все хорошо. Однако при более глубоком чтении о B-деревьях фактические подробности о том, как ключи располагаются на диске для максимальной локальности и сжатия ключей, заставили меня еще больше оценить этот подход. Сделав шаг назад, давайте вспомним из «CS common knowledge» некоторые основы постоянного хранилища:

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

Твердотельные накопители (SSD) состоят из набора ячеек памяти, составленных в виде иерархии страниц, блоков и панелей. . У них нет движущихся частей, но каждая ячейка имеет ограниченное количество операций чтения / записи, которые она может выполнить, прежде чем станет навсегда недоступной. Таким образом, существует программное обеспечение уровня устройства и ОС для распределения операций по диску, чтобы продлить срок службы диска. Более того, твердотельные накопители не просто «огромные банки более медленной оперативной памяти», как моя ментальная модель ранее. Скорее:

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

Все это говорит о том, что и жесткие диски, и твердотельные накопители имеют аппаратные ограничения на наименьший блок, который они могут читать / писать. ОС абстрагирует это как «интерфейс блочного устройства». Почему нам нужно об этом заботиться? Любые структуры на диске, которые мы создаем, должны знать количество блоков (также называемых страницами), которые они изменяют. Изменение 2021 байтов в 2019 разные блоки будут намного медленнее, чем изменение 2019 байтов в одном блоке. То же верно и для операций чтения. Таким образом, мы хотим, чтобы логическая компоновка нашей структуры данных хорошо вписывалась в абстракцию блочного устройства. узел дерева получает страницу на диске. Мы можем настроить параметры дерева (в первую очередь, количество ключей на узел), чтобы удобно зафиксировать узел на странице диска.

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

Страницы со слотами состоят из трех компонентов: заголовка (содержащего метаданные о странице), ячеек («слоты» переменного размера для данных, быть сохранены в) и указатели смещения (массив указателей на эти ячейки).

Slotted Page Layout

Разметка страницы с прорезями

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

Это означает что вы также можете освобождать и повторно использовать ячейки при удалении / вставке данных. Slotted Page Layout SQLite , например, управляет этим с помощью freelist . 1

Поиск в B-дереве

Я хотел бы обсудить еще пару оптимизаций, но перед этим будет полезно обсудить, как B-деревья выполняют поиск. Алгоритм поиска в B-дереве довольно прост. Обычно это описывается примерно так:

  1. Начать с корневого узла.
  2. Посмотрите на разделительные ключи в текущий узел, чтобы найти дочерний узел, который логически будет содержать искомый ключ поиска.
  3. Рекурсивно перемещайтесь по дереву, используя логику из шага 2.
  4. Если вы нажмете на листовой узел, содержащий искомый ключ, все готово. Если вы обнаружите, что листовой узел не существует для ключа поиска (например, нет листа для диапазона, который вы ищете) или листовой узел не содержит желаемый ключ, сообщите, что ключ не существует, и вы готово.

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

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

Усечение ключа разделителя

Воспользовавшись изложенным выше соображением, мы можем решить использовать «лучшие» партии. ключи для повышения эффективности хранения B-Tree:

Мы можем сэкономить место на страницах, не сохраняя ключ целиком, а сокращая его. В частности, на страницах внутри дерева ключи должны предоставлять достаточно информации только для того, чтобы действовать как границы между диапазонами ключей. Упаковка большего количества ключей на страницу позволяет дереву иметь более высокий коэффициент ветвления и, следовательно, меньше уровней. ( Разработка приложений с интенсивным использованием данных , Мартин Клеппманн)

Чтобы проиллюстрировать это, предположим, что вы пытаетесь сохранить следующие ключи:

 0xAAAAAA 0xBBBBBB 0xCCCCCC 0xDDDDDD 0xEEEEEE 0xFFFFFF  

… и наш алгоритм вставки решил сохранить их в двух узлах дерева:

 # Узел 1 0xAAAAAA 0xBBBBBB 0xCCCCCC # Узел 2 0xDDDDDD 0xEEEEEE 0xFFFFFF   

Что должен родитель Node 1 и Узел 2 использовать в качестве разделительного ключа между ними? Наивная реализация будет использовать

 0xDDDDDD .  Все, что меньше 

0xDDDDDD находится в Узле 1, все больше или равно

0xDDDDDD находится в узле 2. Однако обратите внимание, что там это большой разрыв между
 0xCCCCCC  а также 
 0xDDDDDD .  Мы можем использовать  намного  разделитель с меньшей степенью детализации и при этом поддерживать правильный раздел.  Например, если мы сохраняем префикс «ключ» 
 0xD  как разделитель, он сообщает нам столько же информации, что и меньше байтов, необходимых для хранения. 

Напомним, что длина ключа может быть (фактически) неограниченной, поэтому этот метод может сэкономить значительное пространство в патологических случаях. Это снова провал визуализации: на большинстве диаграмм (для простоты) показаны маленькие клавиши - выбор отдельных цифр или символов. Однако в реальной системе базы данных ключи могут быть нетривиально большими - SQLite по умолчанию имеет максимальный размер ключа 1 МБ.

3

Страницы переполнения

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

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

Таким образом, может быть более эффективным разделение ключа - сохранение префикса на исходной странице и переполнение остальных на страницу переполнения:

  # Очень длинный ключ: AAABBBCCCDDDEEEFFFGGGHHH |  Хранится на главной странице |  Сохранено на странице переполнения |  -------------------------------------------------- - |  AAABBBCC |  CDDDEEEFFFGGGHHH |    

Сюда, если мы проверка наличия ключа или выполнение запроса диапазона, существует более высокая вероятность того, что нам не потребуется обращаться к странице переполнения - поскольку во многих случаях префикса ключа достаточно чтобы ответить на запрос.

Родственные указатели

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

Некоторые реализации хранить прямые и обратные ссылки, указывающие на левую и правую родственные страницы. Эти ссылки помогают найти соседние узлы, не возвращаясь к родительскому. ( Внутреннее устройство базы данных , pg 1000)

Эти одноуровневые указатели делают запросы диапазона более производительными:

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

Во-первых: для каждого уровня одноуровневые узлы всегда имеют неперекрывающиеся, строго увеличивающиеся диапазоны ключей. Это означает, что переход к правому брату узла гарантированно (на этом уровне) содержит логически «следующий» фрагмент ключевого пространства. Во-вторых: в более глубоких деревьях наличие указателей-братьев может означать предотвращение потенциально большого количества «обратного обхода» резервных копий родительских узлов.

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

Визуальное подтверждение свойства диапазона ключей для per -уровневые братья и сестры

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

Visual proof for key range property of per-level siblings Варианты B-дерева

Наконец: помимо B⁺-деревьев, которые в первую очередь я обсуждал, существуют варианты и оптимизации для B-деревьев, которые могут обеспечить оптимизацию при определенных обстоятельствах. : «Ленивые би-деревья» вроде

WiredTiger и Лениво-адаптивное дерево может повысить производительность за счет буферизации записи. FD-Trees структурируют данные B-Tree способом, более удобным для физических характеристик SSD. Bw-Trees (забавно, «деревья модных словечек») обеспечивают дальнейшую оптимизацию для высокого параллелизма и доступа к дереву в памяти.

Заключение

Если что-то из этого показалось вам интересным, я снова настоятельно рекомендую прочитать Внутреннее устройство базы данных . Я думаю, что самый большой вывод, который я сделал, заключается в том, что существует значительная разница между структурой данных как абстрактным математическим понятием («B⁺-дерево») и конкретными реализациями («формат базы данных SQLite»). Оптимизация конкретных реализаций не улучшит характеристики BigO структуры данных, но будет иметь значительные «реальные» последствия для производительности и удобства использования базы данных.

Кроме того, все это лишь начало более продолжительного обсуждения более тонкой оптимизации конкретных систем хранения. Как я узнал копаясь в Raft , дьявол кроется в деталях. «Требуется дополнительная бухгалтерия» - готовое приглашение к сводящим с ума ошибкам и нетривиальной сложности.

В заключение: поскольку я жаловался на визуализацию деревьев, я это сделал найти диаграмму B-Tree, которая, как мне кажется, дает лучшее представление о древовидной структуре на практике. Это из работы Мартина Клеппмана Разработка приложений с интенсивным использованием данных :

Разработка приложений с интенсивным использованием данных , рисунок 3.6

Крышка: Unsplash

Leave a comment

Your email address will not be published. Required fields are marked *

18 + six =