Является ли B-Tree порядка 2 полным двоичным деревом?

Question

Когда я сделал поиск по вышеуказанному вопросу, я получил ответ Yes.

Определение для полного двоичного дерева выглядит следующим образом:

Полное бинарное дерево (иногда собственно бинарное дерево или 2-дерево) представляет собой дерево, в котором каждый узел, кроме листьев имеет двоих детей.

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

Например:

Вставьте 10,17,45 в в-дерево порядка 2

структура, которую мы получаем

10 
    17 
     45 

, который не является полным двоичным деревом.

Так почему это сказано, что B-Tree порядка 2 - полное двоичное дерево?

Answer 1

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

Как бы то ни было, для любого типа B-дерева количество указателей в узле определяется количеством ключей в этом узле. Если число ключей равно k, число указателей равно k + 1, период. Нет выбора в отношении количества указателей, поскольку могут быть и в других видах деревьев. Либо все указатели в узле равны nil (корень в одноуровневом «дереве», листе), либо все действительны, между ними нет никакой смеси.

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

Установка ключей 10, 17 и 45 в пустой B-дерева минимально возможного порядка будет идти, как это:

[] 

[10] 

[10 17] 

    [17] 
[10] [45] 

Конечный результат действительно случается, чтобы выглядеть как сбалансированное бинарное дерево.

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

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