File Indexing

Question

Which tree has more number of levels for 'n' nodes - B tree or B+ tree? What's the reason behind it?

Comments

Parimal Paritosh

This isn't allowed but for such cases since the 8 leaf nodes are occupied to full extent and only one key is left out (for which overall 9 nodes are needed) we can imagine like the 57 key values get rearranged in some order within these 9 nodes so as to maintain the min. key condition.

I have encountered such problem and i assumed it in this way though i haven't tried drawing any tree and check.

But if you insert it in sorted order i don't think this division will work..I mean the leaf nodes except the rightmost one get almost half occupied..So it might take up more than 9 nodes in such case as the keys are not compactly fitted i.e. what we are doing here is ceil(57/7)=9 means within 9 nodes all 57 will get fitted which means roughly 6 keys per node (57keys/(9nodes)) considering the rearrangement. 6 keys per node means almost fully occupied but if you try inserting in the sorted order then the leaves(except the rightmost one) get occupied by half it's capacity i.e (3 or 4).

I just drew the tree and checked it..If my inference is wrong do correct it ..

---

@MiNiPanda

Thanks Bro.... i understood your explanation... i don't know how i said based on repeating keys only, i realize my mistake, another simple way to say it

 

Comparing Leaf nodes :-

B tree :- (p-1) . (keys + Record pointer) + (p) (Block pointer)

B+ tree :- (p-1) (keys+Record Pointer) + (1) (Block pointer)

∴ B+ tree can accommodate more no.of keys than B tree ===> More levels in B tree

 

Comparing Internal Nodes :-

B tree takes the size :- (p-1) . (keys + Record pointer) + (p) (Block pointer)

B+ tree takes the size :- (p-1) (keys) + (p) (Block pointer)

Note that one key is repeated in B+ tree but it much smaller than the size of ( (p-1).Record Pointer ) of B tree

∴ B+ tree can accommodate more no.of keys than B tree ===> More levels in B tree

 

By these two points we an say B tree has more no.of levels compare to B+ tree to accommodate n keys.

---

yes ..