MADE EASY TEST SERIES

Question

Consider that blocks can hold either 10 records or 99 keys and 100 pointers. Assume that the average B tree node is 70% full, i.e. it will have 69 keys and 70 pointers. The total number of blocks needed for a 10,000 record file if memory is initially empty, the search key is the primary key for the records and the data file is a sequential file, sorted on the search key with 10 records per block with dense index are_______?

Comments

How to solve such questions?

---

1147?

---

Yes..but how did you solve this?Please give the detailed explanation once..

---

its given that we have 10,000 records.

block factor = 10

index factor = 70 ...

#blocks in main file = 10000/10 = 1000 (#records/block factor)

#blocks in level3 index file = ceil(10000/69) = 145 (as its dense index and each record in main file should be related to a pointer)     

#blocks (level 2) = ceil(143/70) = 3

#blocks (level 1) = ceil(3/70) =1

therefore , total blocks for entire system = (1000+145+3+1) =1149 answer

                      

---

In the last level index i.e. the leaf nodes, they dont have any block pointers, they just have <key,record pointer> pairs. So in the leaf level, shouldnt you divide by 69 since there are 69 <key,record pointer> pairs and they should point to the records in the main file?

---

see they have said that each node will have 69records and 70 pointers and each pointer should be pointing to the next record...

keys will be stored in index file but pointers will be linked to each record in main level.

---

But isnt it true that in the leaf level, the block pointers are null and there are simply record pointers along with the keys? So shouldnt the number of pointers to records be 69 rather than 70?

In the question it is just said that a b tree node contains 69 keys and 70 pointers, so here pointers indicate block pointers i guess.. where is it said that each pointer should be pointing to the next record??I am not being able to get this :(

---

yes :p ok now :)

---

Isnt ceil(10000/69)=145?

---

oops yes i didnt saw that  :p

---

So answer should be 1149 right?

---

yes

---

Ok..thanks :)

Answer 1

In the made easy solution they have assumed that last level contains 10000 entry. We know for B tree last level doesn't contain all the entry ( this is true for B plus tree).  Therefore total number of entry in the B tree should be 10000.