B + Вставка дерева - теоретический вопрос

Question

Я пытался узнать, как работает B + Tree и пытается решить примеры.

В одном таком документе перечислены here, в примере 1, представленном на странице 8. Он описывает B + дерево конструкцию, где «п» количество поисковых ключевых значений на узел - задаются как 4.

Все идет по правилам до третьего шага, но внезапно на 4-м шаге вы видите, что корневой узел разделяется, а другие расщепления приближаются. Я понял, почему узел 17,19,21 разбит (это, по-видимому, не показано в тексте). Но я удивлен, почему корень разделен. Может ли кто-нибудь прояснить это мне или предложить лучший пример, который довольно сложный, но с более отличительным и пошаговым подходом.

Answer 1

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

Пример немного слабый, обычно все узлы, кроме корня, по меньшей мере наполовину полны. Но половина из 3 равна 1, так что это не слишком очевидно.