CODEWITHSUNDEEP
databaseindexingtheoryb-tree
Chaitanya
Chaitanya

Reputation: 1708

B+ Tree Insertion - Theoretical Question

I have been trying to know how B+ Tree works and been trying to solve the examples.

In one such document listed here, in the Example 1 given on page 8. It describes a B+ tree construction, where 'n' number of search key values per node - is given as 4.

Everything goes according to the rules till the third step, but suddenly in the 4th step you see the root node being split, and other splits coming up. I understood why the node 17,19,21 is split(this is apparently not shown in the text). But I'm surprised why the root is split up. Can anyone clarify this to me or suggest a better example which is quite complicated but with a more distinctive and step-by-step approach.

Upvotes: 0

Views: 1094

Answers (1)

Henk Holterman
Henk Holterman

Reputation: 273179

This is how B-Trees work: Leaf nodes are filled and on overflow they Split, sending 1 keyvalue up. The node above could then also split, all the way up to the root.

The example is a little weak, normally all nodes except the root are at least half-full. But half of 3 is 1, so this is not too obvious.

Upvotes: 1

Related Questions