search
Log In
0 votes
461 views
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_______?
in Databases
retagged by
461 views
0
How to solve such questions?
0
1147?
0
Yes..but how did you solve this?Please give the detailed explanation once..
0

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

                      

0
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?
0
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.
0
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 :(
0
yes :p ok now :)
0
Isnt ceil(10000/69)=145?
0
oops yes i didnt saw that  :p
0
So answer should be 1149 right?
0
yes
0
Ok..thanks :)

1 Answer

1 vote
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.

Related questions

2 votes
1 answer
1
390 views
$P_{1}:$ {$<M>|M $ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>|M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________
asked Apr 30, 2019 in Theory of Computation srestha 390 views
0 votes
1 answer
2
307 views
How many number of $DFA$ states(minimal DFA) required which accepts the language $L=\left \{ a^{n}:n=\text{3 or n>= 2m for all m>= 1} \right \}$ ___________ Answer will be $3$ or $6?$
asked Apr 23, 2019 in Theory of Computation srestha 307 views
0 votes
3 answers
3
2k views
Consider $\left \langle M \right \rangle$ be the encoding of a turing machine as a string over alphabet $\Sigma =\left \{ 0,1 \right \}$. Consider $D=${$\left \langle M \right \rangle$ $M$ ... Recursive $(B)$ Non-Recursive $(C)$ Recursively enumerable $(D)$ Not Recursively enumerable My question is Is it not a Halting Problem they are asking for?
asked Apr 13, 2019 in Theory of Computation srestha 2k views
3 votes
1 answer
4
...