Skip to content

Comment on The Ubiquitous B-Tree (1979) [pdf]

Comments

Why does the root have only two children and not d, like every other non-leaf node?

Because when you split the root, it can only have 2 children.

I didn't understand your answer even after rereading about tree operations but I think I found out the actual reason why the root can have less than d children:

it is because of rebalancing after deletion. Underflows can go all the way up to the root so its children can borrow its indices. And when root has only one index (and two children) and another underflow occurs then its children combined with its index can form a new root decreasing the tree height by one.

AboutSource Built by g1lg1l

Hackerly is an independent reader for Hacker News, built on the public HN API. Not affiliated with Y Combinator.