B-дерево: описание

января 08, 2020

Литература о B-деревьях неоднородна по своей терминологии (Folk & Zoellick 1992).

Bayer&McCreight (1972), Comer (1979) и другие определяют порядок B-дерева как минимальное количество ключей в некорневом узле. Фолк и Зеллик (1992) указывают, что терминология неоднозначна, поскольку максимальное количество ключей не ясно. B-дерево порядка 3 может содержать максимум 6 ключей или максимум 7 ключей. Кнут (1998) избегает этой проблемы, определяя порядок как максимальное число дочерних элементов (что на один больше, чем максимальное количество ключей).

Термин "лист"(leaf) также противоречив. Bayer & McCreight (1972) рассматривали уровень листа как самый низкий уровень ключей, но Кнут считал уровень листа на один уровень ниже самых низких ключей (Folk & Zoellick 1992). Есть много возможных вариантов реализации. В некоторых проектах листья могут содержать всю запись данных; в других реализациях листья могут содержать только указатели на запись данных. Эти выборы не являются фундаментальными для идеи B-дерева.

Для простоты большинство авторов предполагают, что в узле есть фиксированное количество ключей. Основное предположение - фиксированный размер ключа и фиксированный размер узла. На практике могут использоваться ключи переменной длины (Folk & Zoellick 1992).

Определение

Согласно определению Кнута, B-дерево порядка m является деревом, которое удовлетворяет следующим свойствам:

Каждый узел имеет не более m детей.
Каждый неконечный узел (кроме корневого) имеет как минимум m/2 дочерних узлов.
Корень имеет по крайней мере два дочерних элемента, если это не листовой узел.
Нелистовый узел с k дочерними элементами содержит k - 1 ключ.
Все листья появляются на одном уровне и не несут никакой информации.

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

Внутренние узлы

Внутренние узлы - это все узлы, кроме листовых узлов и корневого узла. Они обычно представлены в виде упорядоченного набора элементов и дочерних указателей. Каждый внутренний узел содержит максимум U дочерних элементов и минимум L дочерних элементов. Таким образом, количество элементов всегда на 1 меньше количества дочерних указателей (количество элементов находится между L-1 и U-1). U должно быть либо 2L, либо 2L-1; поэтому каждый внутренний узел заполнен как минимум наполовину. Взаимосвязь между U и L подразумевает, что два наполовину полных узла могут быть объединены, чтобы сделать легальный узел, и один полный узел может быть разделен на два легальных узла (если есть место, чтобы вставить один элемент в родительский узел). Эти свойства позволяют удалять и вставлять новые значения в B-дерево и корректировать дерево для сохранения свойств B-дерева.

Корневой узел

Количество дочерних узлов корневого узла имеет тот же верхний предел, что и внутренние узлы, но не имеет нижнего предела. Например, когда во всем дереве меньше L-1 элементов, корень будет единственным узлом в дереве без дочерних элементов вообще.

Листовые узлы

В терминологии Кнута листовые узлы не несут никакой информации. Внутренние узлы, которые находятся на один уровень выше листьев, это то, что другие авторы назвали бы "листьями": в этих узлах хранятся только ключи (не более m-1 и не менее m/2-1, если они не являются корневыми) и указатели на узлы, не содержащие никакой информации.

B-дерево глубины n + 1 может содержать в U раз больше элементов, чем B-дерево глубины n, но стоимость операций поиска, вставки и удаления возрастает с глубиной дерева. Как и с любым сбалансированным деревом, стоимость растет гораздо медленнее, чем количество элементов.

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

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

Alex tools