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

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

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

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


person Chaitanya    schedule 05.12.2010    source источник
comment
Предлагаемая литература: infolab.stanford.edu/~hector/cs245/Notes04.ppt (начиная со слайда 91 и далее; я сам научился этому с помощью этих слайдов, но когда я сейчас смотрю на них, они не очень понятны)   -  person Meinersbur    schedule 06.12.2010


Ответы (1)


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

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

person Henk Holterman    schedule 05.12.2010
comment
это было указано как ciel (n-1/2). Это будет 2? Можете ли вы привести какой-либо лучший ресурс? - person Chaitanya; 06.12.2010
comment
Да, вы правы, разделение на нелистовом узле будет ceil(n/2)-1, а на ведущем узле - ciel(n-1/2) - person Chaitanya; 06.12.2010
comment
Извините за вопрос, так как это довольно легко решить. Я невнимательно читал правила. Спасибо еще раз, я понял, что я ошибся. Корень разделен из-за разделения, исходящего от дочернего узла (17,19,21), ожидающего записи 20, когда это разделение происходит, возникает новый узел с 20 в качестве родительского, но в соответствии с правилом b-дерева все листья узлы должны быть на одной высоте. Таким образом, вы разделяете корневой узел, чтобы разместить дополнительный уровень, созданный ключом 20. Еще раз спасибо. - person Chaitanya; 06.12.2010