Space utilization of B + tree and B tree

Question

What is the minimum and maximum space utilization of b+ tree and b tree?

Answer 1

B+ tree min space utization=50%

B tree space utilization 66.6%

Comments

Hi Pooja,

 Can you please explain us how to get the exact numbers u have mentioned Please.

In B+ tree, the internal nodes can contained more number of keys and more number of node pointers as only leaf nodes will contain key,data pointer pair. But B-Tree's internal Node contains both key,data Pointer pair along with the node pointer. As size of key,data pointer is more then the size of key, hence more number of keys can be stored in internal node of B+ tree than the Btree with the same node size.

hence Space utilization of B+ tree is more than the B tree.

---

How is it 66.6% for B tree?

Answer 2

Dont know what is your quetion meaning 

What i get which is get minmum utilization and which is get maximum utilization if used.

so Ans is degree of b+ tree of storing record is more so utilization is more.

 degree of b tree of storing record is less than b+ tree  so utilization is less.

Comments

Thank you for replay.

I wanted to know how to calculate minimum and maximum space utilization of both tress.

Answer 3

In B+ trees the value are stored only on leaf nodes 

if we have n nodes then number of values leaf nodes store

minimum -(n/2)ceil and maximum n

in B Tree it is 66.6 %

Comments

How is it 66.6% for B tree?