B-tree/B+tree

Question

1)Consider a B+ Tree of  order 4 and height 3, then find
a)The maximum number of records stored are ...........
b)The maximum number of keys ...........
c)The minimum number of records stored are ............    
d)The minimum number of keys ............

---

2) Find the following with degree 3 and height 3 in B- tree 
Minimum and maximum number of keys ?

---

3) Find the following with order 3 and height 3 in B-tree 
Minimum and maximum number of keys ?

Please provide detailed explanation 

Answer 1

1) B+ Tree of order 4 and height 3

P->Order of the B-Tree

(R-Record/Actual data ,TP- Tree Pointer/Block Pointer/Pointer to other node)

(Assuming Root is Hieght 0)

1)a)b)Maximum: In Root &  Internal Node-> TP=P and R = (P-1) , Leaf-> R = (P-1)

Height 0(Root);       1Node         3R                     4TP

Hieght 1:                4Nodes       4*3=12R            4*4=16TP

Height 2:                16Nodes     16*3=48R          16*4=64TP

Height 3:                64Nodes      64*3=192R         (Leaves don't contain Tree pointer)

---

1)c)d)Minimum: In Root-> TP=2, R=1, Internal Node-> TP= P/2(Ciel), R=P/2(Ciel)-1 , Leaf->R=P/2(Ciel)-1 

Height 0(Root);       1Node         1R                     2TP

Hieght 1:                2Nodes       2*1=2R             2*2=4TP

Height 2:                4Nodes       4*1=4R             4*2=8TP

Height 3:                8Nodes       8*1=8R           (Leaves don't contain Tree pointer)

---

3) Order 3 and height 3 in B-tree

(DP-Data pointer/Pointer to actual data, DP also = No.of Records in B-tree can hold, TP- Tree Pointer/Block pointer/Pointer to other node)

(Assuming Root is Hieght 0)

Maximum: In Root-> TP=P,  DP=(P-1), Internal Node-> TP=P ,DP= (P-1) , Leaf->DP=(P-1)

Height 0(Root);       1Node         2DP                3TP

Hieght 1:                3Nodes       3*2=6DP         3*3=9TP

Height 2:                9Nodes       9*2=18DP       9*3=27TP

Height 3:                27Nodes     27*2=54DP     (Leaves don't contain Tree pointer)

---

Minimum: In Root-> TP=2,  DP=1, Internal Node-> TP= P/2(Ciel), DP=P/2(Ciel)-1  , Leaf->DP=P/2(Ciel)-1 

Height 0(Root);       1Node         1DP                2TP

Hieght 1:                2Nodes       2*1=2DP         2*2=4TP

Height 2:                4Nodes       4*1=4DP         4*2=8TP

Height 3:                8Nodes       8*1=8DP         (Leaves don't contain Tree pointer)

---

Comments

@Mohit Chawla I just have shown how in each level it is calculated.
In case of B-Trees we can add all the records of all the levels(Since records will also be stored in intermediate level) but in case of B+ trees we just we just need to take the value of records in leaves(Since records will be stored only in leaves)
@cse7 Haha Computational error,corrected it.Thnx

---

yup.. I agree, i was talking about keys prajwal.

---

I Didn't get your question...