14.Разновидности В-дерева
 

В⁺-дерево. Рассмотренная структура В-дерева предполагает, что в узлах дерева находятся полные (истинные) значения ключей. Связанные с ключом данные мо-гут находиться в том же узле, что и сам ключ, или же в другом месте. В последнем случае в узле для каждого ключа необходимо иметь указатель на данные. Тогда для обработки данных придется считывать блок с данными.

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

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

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

Таким образом, В⁺-деревья во многом превосходят B - деревья, а уступают В-деревьям в том, что требуют несколько больше памяти для представления (ключи-разделители и ключи в листьях).

В^* -дерево. Отличается от В-дерева более высоким коэффициентом заполнения. Если в В-дереве каждый узел должен быть заполнен не менее чем наполовину, то для В^*-дерева требуется, чтобы каждый узел был заполнен элементами не менее чем на 2/3. Алгоритмы вставки и удаления элементов сложнее чем в В-дереве.

(2—3)-дерево. В-дерево порядка 1 носит название (2-3 дерева (двоичного В-дерева), так как каждый узел в таком дереве может иметь 2 или 3 потомка. Это дерево иногда применяется при работе в основной памяти, применение его для работы на ВЗУ нерационально.