The Gateway to Computer Science Excellence
0 votes
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 by Active (5k points)
retagged by | 119 views
How to solve such questions?
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?
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.
by (23 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
104,977 users