Структуры данных: B-дерево (B-tree)

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

То, за что означает B, никогда не было установлено.

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

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

Обзор

В B-деревьях внутренние (неконечные) узлы могут иметь переменное число дочерних узлов в некотором предопределенном диапазоне. Когда данные вставляются или удаляются из узла, его количество дочерних узлов изменяется. Чтобы поддерживать предварительно определенный диапазон, внутренние узлы могут быть соединены или разделены. Поскольку диапазон дочерних узлов разрешен, B-деревья не нуждаются в перебалансировке так часто, как другие самобалансирующиеся деревья поиска, но могут тратить некоторое пространство, так как узлы не полностью заполнены. Нижняя и верхняя границы количества дочерних узлов обычно фиксируются для конкретной реализации. Например, в 2-3 B-дереве (часто просто называемом 2-3-деревом (2-3 tree)) каждый внутренний узел может иметь только 2 или 3 дочерних узла.

Каждый внутренний узел B-дерева содержит несколько ключей. Ключи действуют как значения разделения, которые разделяют его поддеревья. Например, если внутренний узел имеет 3 дочерних узла (или поддерева), то он должен иметь 2 ключа: a1 и a2. Все значения в крайнем левом поддереве будут меньше, чем a1, все значения в среднем поддереве будут между a1 и a2, а все значения в крайнем правом поддереве будут больше, чем a2.

Обычно количество ключей выбирается в зависимости от d до 2d, где d - минимальное количество ключей, а d + 1 - минимальная степень или коэффициент ветвления дерева. На практике ключи занимают больше места в узле. Коэффициент 2 гарантирует, что узлы могут быть разделены или объединены. Если внутренний узел имеет ключи 2d, то добавление ключа к этому узлу может быть выполнено путем разбиения гипотетического узла ключа 2d + 1 на два узла ключа d и перемещение ключа, который был бы посередине, к родительскому узлу. Каждый разделенный узел имеет необходимое минимальное количество ключей. Аналогично, если каждый внутренний узел и его сосед имеют ключи d, то ключ может быть удален из внутреннего узла путем объединения его со своим соседом. Удаление ключа приведет к тому, что у внутреннего узла будут ключи d-1; присоединение к соседу добавит d ключей плюс еще один ключ, полученный от родительского соседа. В результате получается полностью полный узел 2d ключей.

Число ветвей (или дочерних узлов) от узла будет на один больше, чем количество ключей, хранящихся в узле. В 2-3 B-деревьях внутренние узлы будут хранить либо один ключ (с двумя дочерними узлами), либо два ключа (с тремя дочерними узлами). Иногда B-дерево описывается параметрами (d + 1) - (2d + 1) или просто с наивысшим порядком ветвления, (2d + 1).

B-дерево сохраняется сбалансированным после вставки путем разбиения потенциального переполненного узла из 2d + 1 ключей на два дочерних элемента d-ключа и вставки ключа среднего значения в родитель. Глубина увеличивается только при разделении корня, сохраняя равновесие. Аналогично, B-дерево сохраняется сбалансированным после удаления за счет слияния или перераспределения ключей между братьями и сестрами, чтобы поддерживать минимум d-ключа для некорневых узлов. Слияние уменьшает количество ключей в родительском объекте, потенциально вынуждая его объединять или перераспределять ключи со своими братьями и сестрами и так далее. Единственное изменение в глубине происходит, когда корень имеет двух дочерних элементов, ключей d и (переходно) d-1, в этом случае два родных брата и родительский элемент объединяются, уменьшая глубину одним.

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

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

Варианты

Термин B-дерево может относиться к конкретному дизайну или может относиться к общему классу конструкций. В узком смысле B-дерево хранит ключи в своих внутренних узлах, но нет необходимости хранить эти ключи в записях на листьях. Общий класс включает в себя такие вариации, как B+ дерево и B* дерево.

В B+ дереве копии ключей хранятся во внутренних узлах; ключи и записи хранятся в листьях; кроме того, конечный узел может включать указатель на следующий конечный узел для ускорения последовательного доступа.

B* дерево балансирует больше соседних внутренних узлов, чтобы внутренние узлы были более плотно упакованы. Этот вариант гарантирует, что некорневые узлы заполнены как минимум на 2/3 вместо 1/2 (Knuth 1998). Поскольку наиболее дорогостоящей частью операции вставки узла в B-дерево является разделение узла, B* деревья создаются для того, чтобы отложить операцию разделения как можно дольше. Чтобы достичь этого, вместо немедленного разделения узла при его заполнении, его ключи используются совместно с узлом рядом с ним. Эта операция разлива дешевле, чем разделение, потому что она требует только перемещения ключей между существующими узлами, а не выделения памяти для нового. Для вставки сначала проверяется, есть ли в узле некоторое свободное пространство, и если так, новый ключ просто вставляется в узел. Однако, если узел заполнен (он имеет m - 1 ключей, где m - это порядок дерева в качестве максимального количества указателей на поддеревья из одного узла), необходимо проверить, существует ли правый брат и есть ли свободное пространство , Если у правого родного брата есть ключи j < m - 1, то ключи перераспределяются между двумя родственными узлами как можно более равномерно. Для этого m - 1 ключ от текущего узла, новый вставленный ключ, один ключ от родительского узла и j ключей от узла-брата рассматриваются как упорядоченный массив из m + j + 1 ключей. Массив делится пополам, так что нижние ключи (m + j + 1)/2 остаются в текущем узле, следующий (средний) ключ вставляется в родительский элемент, а остальные переходят к правому брату. (Вновь вставленный ключ может оказаться в любом из трех мест.) Ситуация, когда правый брат заполнен, а левый - нет, является аналогом. Когда оба родственных узла заполнены, два узла (текущий узел и родной) разделяются на три, и еще один ключ перемещается вверх по дереву к родительскому узлу. Если родитель заполнен, то операция разлива/разделения распространяется на корневой узел. Однако удаление узлов несколько сложнее, чем вставка.

B-деревья можно превратить в порядковые статистические деревья (order statistic trees), чтобы обеспечить быстрый поиск N-й записи в ключевом порядке или подсчет количества записей между любыми двумя записями, а также различные другие связанные операции.

Этимология

Рудольф Байер и Эд МакКрейт изобрели B-дерево, работая в исследовательской лаборатории Boeing (Bayer & McCreight 1972), но не объяснили, что означает B: Боинг, сбалансированный, широкий, пушистый и Байер (Boeing, balanced, broad, bushy, Bayer). МакКрайт сказал, что "чем больше вы думаете о значении B в B-деревьях, тем лучше вы понимаете B-деревья".

Поиск по этому блогу

Alex tools