Solutions to homework 4 CHAPTER 13 and
chapter 14:
13.23
We discussed it in class for problem
24.
Answer:
(a) Total track size = 20 *
(512+128) = 12800 bytes = 12.8 Kbytes
Useful capacity of a track = 20 *
512 = 10240 bytes = 10.24 Kbytes
(b) Number of cylinders = number of
tracks = 400
(c) Total cylinder capacity = 15*2*20*(512+128)
= 384000 bytes = 384 Kbytes
Useful cylinder capacity = 15 * 2 *
20 * 512 = 307200 bytes = 307.2 Kbytes
(d) Total capacity of a disk pack =
15 * 2 * 400 * 20 * (512+128)
= 153600000 bytes = 153.6 Mbytes
Useful capacity of a disk pack = 15
* 2 * 400 * 20 * 512 = 122.88 Mbytes
(e) Transfer rate tr= (total track
size in bytes)/(time for one disk revolution in msec)
tr= (12800) / ( (60 * 1000) / (2400)
) = (12800) / (25) = 512 bytes/msec
block transfer time btt = B / tr =
512 / 512 = 1 msec
average rotational delay rd = (time
for one disk revolution in msec) / 2 = 25 / 2
= 12.5 msec
bulk transfer rate btr= tr * (
B/(B+G) ) = 512*(512/640) = 409.6 bytes/msec
(f) average time to locate and
transfer a block = s+rd+btt = 30+12.5+1 = 43.5 msec
(g) time to transfer 20 random
blocks = 20 * (s + rd + btt) = 20 * 43.5 = 870 msec
time to transfer 20 consecutive
blocks using double buffering = s + rd + 20*btt
= 30 + 12.5 + (20*1) = 62.5 msec
(a more accurate estimate of the
latter can be calculated using the bulk transfer
rate as follows: time to transfer 20
consecutive blocks using double buffering
= s+rd+((20*B)/btr) = 30+12.5+
(10240/409.6) = 42.5+ 25 = 67.5 msec)
Either one can be useful in a
specific situation.
13.24
Answer:
(a) R = (30 + 9 + 40 + 9 + 8 + 1 + 4
+ 4 + 4 + 3) + 1 = 113 bytes
(b) bfr = floor(B / R) = floor(512 /
113) = 4 records per block
b = ceiling(r / bfr) = ceiling(20000
/ 4) = 5000 blocks
(c) For linear search we search on
average half the file blocks= 5000/2= 2500 blocks.
i. If the blocks are stored
consecutively, and double buffering is used, the time to read
2500 consecutive blocks
= s+rd+(2500*(B/btr))=
30+12.5+(2500*(512/409.6))
= 3167.5 msec = 3.1675 sec
(a less accurate estimate is =
s+rd+(2500*btt)= 30+12.5+2500*1= 2542.5 msec)
ii. If the blocks are scattered over
the disk, a seek is needed for each block, so the time
is: 2500 * (s + rd + btt) = 2500 *
(30 + 12.5 + 1) = 108750 msec = 108.75 sec
(d) For binary search, the time to
search for a record is estimated as:
ceiling(log 2 b) * (s +rd + btt)
= ceiling(log 2 5000) * (30 + 12.5 +
1) = 13 * 43.5 = 565.5 msec = 0.5655 sec
14.14
Answer:
(a) Record length R = (30 + 9 + 9 +
40 + 9 + 8 + 1 + 4 + 4) + 1 = 115 bytes
(b) Blocking factor bfr = floor(B/R)
= floor(512/115) = 4 records per block
Number of blocks needed for file =
ceiling(r/bfr) = ceiling(30000/4) = 7500
(c)
i. Index record size R i = (V
Index blocking factor bfr i = fo =
floor(B/R i ) = floor(512/15) = 34
ii. Number of first-level index
entries r 1 = number of file blocks b = 7500 entries
Number of first-level index blocks b
1 = ceiling(r 1 /bfr i ) = ceiling(7500/34)
= 221 blocks
iii. We can calculate the number of
levels as follows:
Number of second-level index entries
r 2 = number of first-level blocks b 1
= 221 entries
Number of second-level index blocks
b 2 = ceiling(r 2 /bfr i ) = ceiling(221/34)
= 7 blocks
Number of third-level index entries
r 3 = number of second-level index blocks b 2
= 7 entries
Number of third-level index blocks b
3 = ceiling(r 3 /bfr i ) = ceiling(7/34) = 1
Since the third level has only one
block, it is the top index level.
Hence, the index has x = 3 levels
iv. Total number of blocks for the
index b i = b 1 + b 2 + b 3 = 221 + 7 + 1
= 229 blocks
v. Number of block accesses to search
for a record = x + 1 = 3 + 1 = 4
(d)
i. Index record size R i = (V
Index blocking factor bfr i =
(fan-out) fo = floor(B/R i ) = floor(512/15)
= 34 index records per block
(This has not changed from part (c)
above)
(Here is an alternative solution:
The previous solution assumes that leaf-level index blocks contain
block pointers; it is also possible
to assume that they contain record pointers, in
which case the index record size
would be V
case, the calculations for leaf
nodes in (i) below would then have to use R i = 16
bytes rather than R i = 15 bytes, so
we get:
Index record size R i = (V
Leaf-level ndex blocking factor bfr
i = floor(B/R i ) = floor(512/16)
= 32 index records per block
However, for internal nodes, block
pointers are always used so the fan-out for
internal nodes fo would still be
34.)
ii. Number of first-level index
entries r 1 = number of file records r = 30000
Number of first-level index blocks b
1 = ceiling(r 1 /bfr i ) = ceiling(30000/34)
= 883 blocks
(Alternative solution:
Number of first-level index entries
r 1 = number of file records r = 30000
Number of first-level index blocks b
1 = ceiling(r 1 /bfr i ) = ceiling(30000/32)
= 938 blocks)
iii.
We can calculate the number of
levels as follows:
Number of second-level index entries
r 2 = number of first-level index blocks b 1
= 883 entries
Number of second-level index blocks
b 2 = ceiling(r 2 /bfr i ) = ceiling(883/34)
= 26 blocks
Number of third-level index entries
r 3 = number of second-level index blocks b 2
= 26 entries
Number of third-level index blocks b
3 = ceiling(r 3 /bfr i ) = ceiling(26/34) = 1
Since the third level has only one
block, it is the top index level.
Hence, the index has x = 3 levels
(Alternative solution:
Number of second-level index entries
r 2 = number of first-level index blocks b 1
= 938 entries
Number of second-level index blocks
b 2 = ceiling(r 2 /bfr i ) = ceiling(938/34)
= 28 blocks
Number of third-level index entries
r 3 = number of second-level index blocks b 2
= 28 entries
Number of third-level index blocks b
3 = ceiling(r 3 /bfr i ) = ceiling(28/34) = 1
Since the third level has only one
block, it is the top index level.
Hence, the index has x = 3 levels)
iv. Total number of blocks for the
index b i = b 1 + b 2 + b 3 = 883 + 26 + 1 = 910
(Alternative solution:
Total number of blocks for the index
b i = b 1 + b 2 + b 3 = 938 + 28 + 1 = 987)
v. Number of block accesses to
search for a record = x + 1 = 3 + 1 = 4
(e)
i. Index record size R i = (V
DEPARTMENTCODE + P) = (9 + 6) = 15 bytes
Index blocking factor bfr i =
(fan-out) fo = floor(B/R i ) = floor(512/15)
= 34 index records per block
ii. There are 1000 distinct values
of DEPARTMENTCODE, so the average number of
records for each value is (r/1000) =
(30000/1000) = 30
Since a record pointer size P R = 7
bytes, the number of bytes needed at the level
of indirection for each value of
DEPARTMENTCODE is 7 * 30 =210 bytes, which
fits in one block. Hence, 1000
blocks are needed for the level of indirection.
iii. Number of first-level index
entries r 1
= number of distinct values of
DEPARTMENTCODE = 1000 entries
Number of first-level index blocks b
1 = ceiling(r 1 /bfr i ) = ceiling(1000/34)
= 30 blocks
iv. We can calculate the number of
levels as follows:
Number of second-level index entries
r 2 = number of first-level index blocks b 1
= 30 entries
Number of second-level index blocks
b 2 = ceiling(r 2 /bfr i ) = ceiling(30/34) = 1
Hence, the index has x = 2 levels
v. total number of blocks for the
index b i = b 1 + b 2 + b indirection
= 30 + 1 + 1000 = 1031 blocks
vi. Number of block accesses to
search for and retrieve the block containing the
record pointers at the level of
indirection = x + 1 = 2 + 1 = 3 block accesses
If we assume that the 30 records are
distributed over 30 distinct blocks, we need
an additional 30 block accesses to
retrieve all 30 records. Hence, total block
accesses needed on average to
retrieve all the records with a given value for
DEPARTMENTCODE = x + 1 + 30 = 33
(f)
i. Index record size R i = (V
DEPARTMENTCODE + P) = (9 + 6) = 15 bytes
Index blocking factor bfr i =
(fan-out) fo = floor(B/R i ) = floor(512/15)
= 34 index records per block
ii. Number of first-level index
entries r 1
= number of distinct DEPARTMENTCODE
values= 1000 entries
Number of first-level index blocks b
1 = ceiling(r 1 /bfr i )
= ceiling(1000/34) = 30 blocks
iii. We can calculate the number of
levels as follows:
Number of second-level index entries
r 2 = number of first-level index blocks b 1
= 30 entries
Number of second-level index blocks
b 2 = ceiling(r 2 /bfr i ) = ceiling(30/34) = 1
Since the second level has one
block, it is the top index level.
Hence, the index has x = 2 levels
iv. Total number of blocks for the
index b i = b 1 + b 2 = 30 + 1 = 31 blocks
v. Number of block accesses to
search for the first block in the cluster of blocks
= x + 1 = 2 + 1 = 3
The 30 records are clustered in
ceiling(30/bfr) = ceiling(30/4) = 8 blocks.
Hence, total block accesses needed
on average to retrieve all the records with a given
DEPARTMENTCODE = x + 8 = 2 + 8 = 10
block accesses
(g) i.
For a B + -tree of order p, the
following inequality must be satisfied for each
internal tree node: (p * P) + ((p -
1) * V
(p * 6) + ((p - 1) * 9) < 512,
which gives 15p < 521, so p=34
For leaf nodes, assuming that record
pointers are included in the leaf nodes, the
following inequality must be
satisfied: (p leaf * (V
(p leaf * (9+7)) + 6 < 512, which
gives 16p leaf < 506, so p leaf =31
ii. Assuming that nodes are 69% full
on the average, the average number of key
values in a leaf node is 0.69*p leaf
= 0.69*31 = 21.39.
If we round this up for convenience,
we get 22 key values (and 22 record pointers) per leaf node. By assuming that 69% is an approximiate
Since the
file has 30000 records and hence
30000 values of
nodes (blocks) needed is b 1 =
ceiling(30000/22) = 1364 blocks
iii. We can calculate the number of
levels as follows:
The average fan-out for the internal
nodes (rounded up for convenience) is
fo = ceiling(0.69*p) =
ceiling(0.69*34) = ceiling(23.46) = 24
number of second-level tree blocks b
2 = ceiling(b 1 /fo) = ceiling(1364/24)
= 57 blocks number of third-level
tree blocks b 3 = ceiling(b 2 /fo) = ceiling(57/24)= 3
number of fourth-level tree blocks b
4 = ceiling(b 3 /fo) = ceiling(3/24) = 1
Since the fourth level has only one
block, the tree has x = 4 levels (counting the
leaf level). Note: We could use the
formula:
x =
ceiling(log fo (b 1 )) + 1 = ceiling(log 24 1364) + 1 = 3 + 1 = 4 levels
iv. total number of blocks for the
tree b i = b 1 + b 2 + b 3 + b 4
= 1364 + 57 + 3 + 1 = 1425 blocks
v. number of block accesses to
search for a record = x + 1 = 4 + 1 = 5
14.15
Answer:
A B + -tree of order p=4 implies
that each internal node in the tree (except possibly the
root) should have at least 2 keys (3
pointers) and at most 4 pointers.
For p leaf =3, leaf nodes must have
at least 2 keys and at most 3 keys.