indexing doubt

Question

Comments

what is your doubt.

---

how to approach the question?

---

according to me it should be 713---->667leaf blocks+(42blocks+3blocks+1blocks)non leaf blocks....

---

1631 nodes ?

Answer 1

number of record =50000

record size=100B ; block size=512

512/100(record/block)=5

therefore 50000/5=10000 blocks required

keysize=20B

recordpointer size=block pointer size=12

for leaf node in B+ tree

m(keysize + Recordpointer size)+ block pointer size<=block size

m(20+12)+12<=512

m=15 it means...leaf 1 block can point 15 blocks

therefore 10000/15=667 blocks at leaf level

now For internal node

order* block pointer size +(order-1)*key size<=block size

order*12+ (order-1)*20 <=512B

order=16....it means every block in internal node can have 16 children

therefor 667/16=42 blocks

42/16=3 blocks

3/16=1 block

total 667 + 42 + 3 + 1 = 713 blocks required

Comments

here they ask for index blocks only and blocks should be maximum

so i think leaf node = 10000/8 = 1250

internal node = 1250/8 =157

157/8 = 20

20/8 = 3

3/8 = 1

 

total = 1250 +157+20+3+1= 1431

Answer 2

Option- B ) 1631

order of B+ tree

let p keys can be inserted in one node means order = P+1

P(20+12)+12<=512

P=15

number of blocks to be pointed 

number of record =50000

record size=100B ; block size=512

record in one block = 512/100 => 5

therefore 50000 records will be in 10000 blocks

now for maximum number of index block => number of keys in each node should be minimum 

that is ceil(16/2) -1 = 7 (therefore minimum 8 pointers)

at first level

floor(10000/7)= 1428 blocks at leaf level

at second level

floor(1428/8)= 178

at third level

floor(178/8) = 22

at fourth level 

floor(22/8) = 2

at last level

1 root node for pointing above 2 nodes

so Total number of index block required = 1428 + 178 + 22 + 2 + 1

Ans = 1631

Comments

Note – i humbly request newcomers like me to do not post any solution if you have not mastered the concept yet or you are not sure of your answer. this only cause confusion