Как сделать вставку B-Tree

Question

Я пытаюсь вставить 3 значения в это B-дерево, 60, 61 и 62. Я понимаю, как вставить значения, когда узел заполнен и у него пустой родительский элемент, но что, если родительский элемент заполнен?

Например, когда я вставлю 60 и 61, этот узел будет заполнен. Я не могу расширить родительский или родительский родитель (потому что они заполнены). Так я могу изменить значения родительского? Я предоставил изображение B-дерева до и после вставки.

Попытка вставить 60, 61, 62: Обратите внимание, что я изменил 66 в корне на 62 и добавил 62 к узлу <72. Это правильный способ сделать это? </p>

Answer 1

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