HW6 Solutions
3.5
- 50 sect./track * 512 byte/sect = 25.6 Kb/track
2000 tracks/surf * 25.6Kb/track = 51.2 Mb/surface
10 surf/disk * 51.2 Mb/surf = 512 Mb/disk
- 2000 cylinders
- 256 is not valid
512, 1024, 2048 are all valid
51200 is not valid, it exceeds one track
- 1min/5400 rev * 60 secs/min = .011 sec/rev
- 25.6Kb/track * 1 track/.011s = 2.3 Mb/sec
3.6
- 1024 byte/block * 1 record/100byte = 10 records/block
- 100000records/file * 1 block/10 records = 10000 blocks/file
1 block/2 sector * 50 sector/track * 2000 tracks/surface = 50,000 blocks/surface, so we need less than 1 surface
- 10 surfaces/disk * 50000blocks/surface * 10 records/block = 5,000,000 records
5. 1 sec/2.3Mb * 10Mb = 4.4 sec
- 10,000blocks(1024 byte/block * 1s/2.3Mb + 10msec + .011sec/2) = 160 secs
4.3
- sequential
- random
- hashed
5.1 (only the changed index nodes are shown)
1. only the second leaf node (from the left) chages: [8*,9*,10*,]
2.
[18,50,,]
¯
¯
[3,8,,] [32,40,,]
¯
¯
[1*,2*,,] [3*,5*,6*,]
This operation requires 5 reads and 5 writes.
5.3
- 50% if we use redistribution
- 100% (manytimes use 80% to give some room for inserts)
- if dataset size and distribution remain fairly static, overflow chains will not be a problem, and we may want to use ISAM for 2 reasons:
- the leaf pages are sorted (making scans easier)
- locking overhead is lower
5.8
- 1000 bytes/page / (40 + 10)bytes for <key,id> * 1page/node = 20 index entries per node.
For bottom level, we need 20,000 records * 1 node/20records = 1000 leaf nodes.
To point to all the leaf nodes, we need 1000 * 1node/20entries = 50 nodes.
To point to the 50 next level nodes, we need 50/20 = 3 nodes.
Finally, need a root node.
- So, we've got 4 levels with 1-3-50-1000 nodes on the 1st - 4th levels respectively.
12.2
- sorted
- hash
- B+ - clustered B+ index allows us to find pointers to the beginning and end records satisfying this condition. We just grab all in between.
- sorted
12.4
- M + M*N = 200 + 200*1000 = 200,200 Ios
- M + N*[M\(B-2)] = 200 + 1000*(200/50) = 4200
- 3*(M+N) = 3*1200 = 3600
- 3*(M+N) = 3*1200 = 3600