Разница между B-деревьями и 2-3-4 деревьями

Question

В чем разница между B-деревьями и 2-3-4 деревьями? Также как вы можете найти максимальную и минимальную высоту каждого из них? Благодаря

Answer 1

... Ссылка на Wikipediaи цитата:

«2-3 -4 деревья - B-деревья порядка 4. "

A 2-3-4являетсяB-tree.
Это называется 2-3-4 дерева, потому что число детей для не-листового, не корневого узла равно 2,3 или 4.
Если бы это было 6, его можно было бы назвать 3-4- 5-6 деревьев, или 3-6 деревьев для краткости.
Поскольку минимальное количество детей составляет половину от максимума, можно просто пропустить первое и поговорить о B-дереве порядка m.
Порядок B-дерева определяется как максимальное количество детей, которое может иметь узел.
В дереве 2-3-4, как мы видели, максимум 4.

Это худшая и лучшая высота дается general formula for B-trees.
Лучший случай: журнал _m n. (все узлы заполнены)
Худший случай: журнал _m/2 n. (все узлы полупустые)
Где

• м является порядок дерева - максимальное число детей, узел может иметь, в данном случае, 4 - и
• п является количество записей в дереве

«B дерево может иметь порядок любого числа» - да, но для конкретного подкласса B-Тре вы исправляете это число заранее. Это все равно, что говорить о бабочках вообще и говорить о Monarch butterfly. B-деревья - это класс структур данных, так же, как бабочки - класс насекомых. Monarch butterflies являются подклассом бабочек, так же как 2-3-4 дерева являются подклассом B-деревьев.

Answer 2

Я не могу сделать лучше, чем просто добавить ссылку на Википедию: http://en.wikipedia.org/wiki/2-3-4_tree

Answer 3

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